// Copyright 2011 The Chromium Authors // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. /* eslint-disable @devtools/prefer-private-class-members */ import * as i18n from '../../core/i18n/i18n.js'; import type * as PlatformApi from '../../core/platform/api/api.js'; import * as Platform from '../../core/platform/platform.js'; import * as HeapSnapshotModel from '../../models/heap_snapshot/heap_snapshot.js'; import {AllocationProfile} from './AllocationProfile.js'; import type {HeapSnapshotWorkerDispatcher} from './HeapSnapshotWorkerDispatcher.js'; export interface HeapSnapshotItem { itemIndex(): number; serialize(): Object; } export class HeapSnapshotEdge implements HeapSnapshotItem { snapshot: HeapSnapshot; protected readonly edges: Platform.TypedArrayUtilities.BigUint32Array; edgeIndex: number; constructor(snapshot: HeapSnapshot, edgeIndex?: number) { this.snapshot = snapshot; this.edges = snapshot.containmentEdges; this.edgeIndex = edgeIndex || 0; } clone(): HeapSnapshotEdge { return new HeapSnapshotEdge(this.snapshot, this.edgeIndex); } hasStringName(): boolean { throw new Error('Not implemented'); } name(): string { throw new Error('Not implemented'); } node(): HeapSnapshotNode { return this.snapshot.createNode(this.nodeIndex()); } nodeIndex(): number { if (typeof this.snapshot.edgeToNodeOffset === 'undefined') { throw new Error('edgeToNodeOffset is undefined'); } return this.edges.getValue(this.edgeIndex + this.snapshot.edgeToNodeOffset); } toString(): string { return 'HeapSnapshotEdge: ' + this.name(); } type(): string { return this.snapshot.edgeTypes[this.rawType()]; } itemIndex(): number { return this.edgeIndex; } serialize(): HeapSnapshotModel.HeapSnapshotModel.Edge { return new HeapSnapshotModel.HeapSnapshotModel.Edge( this.name(), this.node().serialize(), this.type(), this.edgeIndex); } rawType(): number { if (typeof this.snapshot.edgeTypeOffset === 'undefined') { throw new Error('edgeTypeOffset is undefined'); } return this.edges.getValue(this.edgeIndex + this.snapshot.edgeTypeOffset); } isInternal(): boolean { throw new Error('Not implemented'); } isInvisible(): boolean { throw new Error('Not implemented'); } isWeak(): boolean { throw new Error('Not implemented'); } getValueForSorting(_fieldName: string): number { throw new Error('Not implemented'); } nameIndex(): number { throw new Error('Not implemented'); } } export interface HeapSnapshotItemIterator { hasNext(): boolean; item(): HeapSnapshotItem; next(): void; } export interface HeapSnapshotItemIndexProvider { itemForIndex(newIndex: number): HeapSnapshotItem; } export class HeapSnapshotNodeIndexProvider implements HeapSnapshotItemIndexProvider { #node: HeapSnapshotNode; constructor(snapshot: HeapSnapshot) { this.#node = snapshot.createNode(); } itemForIndex(index: number): HeapSnapshotNode { this.#node.nodeIndex = index; return this.#node; } } export class HeapSnapshotEdgeIndexProvider implements HeapSnapshotItemIndexProvider { #edge: JSHeapSnapshotEdge; constructor(snapshot: HeapSnapshot) { this.#edge = snapshot.createEdge(0); } itemForIndex(index: number): HeapSnapshotEdge { this.#edge.edgeIndex = index; return this.#edge; } } export class HeapSnapshotRetainerEdgeIndexProvider implements HeapSnapshotItemIndexProvider { readonly #retainerEdge: JSHeapSnapshotRetainerEdge; constructor(snapshot: HeapSnapshot) { this.#retainerEdge = snapshot.createRetainingEdge(0); } itemForIndex(index: number): HeapSnapshotRetainerEdge { this.#retainerEdge.setRetainerIndex(index); return this.#retainerEdge; } } export class HeapSnapshotEdgeIterator implements HeapSnapshotItemIterator { readonly #sourceNode: HeapSnapshotNode; edge: JSHeapSnapshotEdge; constructor(node: HeapSnapshotNode) { this.#sourceNode = node; this.edge = node.snapshot.createEdge(node.edgeIndexesStart()); } hasNext(): boolean { return this.edge.edgeIndex < this.#sourceNode.edgeIndexesEnd(); } item(): HeapSnapshotEdge { return this.edge; } next(): void { if (typeof this.edge.snapshot.edgeFieldsCount === 'undefined') { throw new Error('edgeFieldsCount is undefined'); } this.edge.edgeIndex += this.edge.snapshot.edgeFieldsCount; } } export class HeapSnapshotRetainerEdge implements HeapSnapshotItem { protected snapshot: HeapSnapshot; #retainerIndex!: number; #globalEdgeIndex!: number; #retainingNodeIndex?: number; #edgeInstance?: JSHeapSnapshotEdge|null; #nodeInstance?: HeapSnapshotNode|null; constructor(snapshot: HeapSnapshot, retainerIndex: number) { this.snapshot = snapshot; this.setRetainerIndex(retainerIndex); } clone(): HeapSnapshotRetainerEdge { return new HeapSnapshotRetainerEdge(this.snapshot, this.retainerIndex()); } hasStringName(): boolean { return this.edge().hasStringName(); } name(): string { return this.edge().name(); } nameIndex(): number { return this.edge().nameIndex(); } node(): HeapSnapshotNode { return this.#node(); } nodeIndex(): number { if (typeof this.#retainingNodeIndex === 'undefined') { throw new Error('retainingNodeIndex is undefined'); } return this.#retainingNodeIndex; } retainerIndex(): number { return this.#retainerIndex; } setRetainerIndex(retainerIndex: number): void { if (retainerIndex === this.#retainerIndex) { return; } if (!this.snapshot.retainingEdges || !this.snapshot.retainingNodes) { throw new Error('Snapshot does not contain retaining edges or retaining nodes'); } this.#retainerIndex = retainerIndex; this.#globalEdgeIndex = this.snapshot.retainingEdges[retainerIndex]; this.#retainingNodeIndex = this.snapshot.retainingNodes[retainerIndex]; this.#edgeInstance = null; this.#nodeInstance = null; } set edgeIndex(edgeIndex: number) { this.setRetainerIndex(edgeIndex); } #node(): HeapSnapshotNode { if (!this.#nodeInstance) { this.#nodeInstance = this.snapshot.createNode(this.#retainingNodeIndex); } return this.#nodeInstance; } protected edge(): JSHeapSnapshotEdge { if (!this.#edgeInstance) { this.#edgeInstance = this.snapshot.createEdge(this.#globalEdgeIndex); } return this.#edgeInstance; } toString(): string { return this.edge().toString(); } itemIndex(): number { return this.#retainerIndex; } serialize(): HeapSnapshotModel.HeapSnapshotModel.Edge { const node = this.node(); const serializedNode = node.serialize(); serializedNode.distance = this.#distance(); serializedNode.ignored = this.snapshot.isNodeIgnoredInRetainersView(node.nodeIndex); return new HeapSnapshotModel.HeapSnapshotModel.Edge( this.name(), serializedNode, this.type(), this.#globalEdgeIndex); } type(): string { return this.edge().type(); } isInternal(): boolean { return this.edge().isInternal(); } getValueForSorting(fieldName: string): number { if (fieldName === '!edgeDistance') { return this.#distance(); } throw new Error('Invalid field name'); } #distance(): number { if (this.snapshot.isEdgeIgnoredInRetainersView(this.#globalEdgeIndex)) { return HeapSnapshotModel.HeapSnapshotModel.baseUnreachableDistance; } return this.node().distanceForRetainersView(); } } export class HeapSnapshotRetainerEdgeIterator implements HeapSnapshotItemIterator { readonly #retainersEnd: number; retainer: JSHeapSnapshotRetainerEdge; constructor(retainedNode: HeapSnapshotNode) { const snapshot = retainedNode.snapshot; const retainedNodeOrdinal = retainedNode.ordinal(); if (!snapshot.firstRetainerIndex) { throw new Error('Snapshot does not contain firstRetainerIndex'); } const retainerIndex = snapshot.firstRetainerIndex[retainedNodeOrdinal]; this.#retainersEnd = snapshot.firstRetainerIndex[retainedNodeOrdinal + 1]; this.retainer = snapshot.createRetainingEdge(retainerIndex); } hasNext(): boolean { return this.retainer.retainerIndex() < this.#retainersEnd; } item(): HeapSnapshotRetainerEdge { return this.retainer; } next(): void { this.retainer.setRetainerIndex(this.retainer.retainerIndex() + 1); } } export class HeapSnapshotNode implements HeapSnapshotItem { snapshot: HeapSnapshot; nodeIndex: number; constructor(snapshot: HeapSnapshot, nodeIndex?: number) { this.snapshot = snapshot; this.nodeIndex = nodeIndex || 0; } distance(): number { return this.snapshot.nodeDistances[this.nodeIndex / this.snapshot.nodeFieldCount]; } distanceForRetainersView(): number { return this.snapshot.getDistanceForRetainersView(this.nodeIndex); } className(): string { return this.snapshot.strings[this.classIndex()]; } classIndex(): number { return this.#detachednessAndClassIndex() >>> SHIFT_FOR_CLASS_INDEX; } // Returns a key which can uniquely describe both the class name for this node // and its Location, if relevant. These keys are meant to be cheap to produce, // so that building aggregates is fast. These keys are NOT the same as the // keys exposed to the frontend by functions such as aggregatesWithFilter and // aggregatesForDiff. classKeyInternal(): string|number { // It is common for multiple JavaScript constructors to have the same // name, so the class key includes the location if available for nodes of // type 'object'. // // JavaScript Functions (node type 'closure') also have locations, but it // would not be helpful to split them into categories by location because // many of those categories would have only one instance. if (this.rawType() !== this.snapshot.nodeObjectType) { return this.classIndex(); } const location = this.snapshot.getLocation(this.nodeIndex); return location ? `${location.scriptId},${location.lineNumber},${location.columnNumber},${this.className()}` : this.classIndex(); } setClassIndex(index: number): void { let value = this.#detachednessAndClassIndex(); value &= BITMASK_FOR_DOM_LINK_STATE; // Clear previous class index. value |= (index << SHIFT_FOR_CLASS_INDEX); // Set new class index. this.#setDetachednessAndClassIndex(value); if (this.classIndex() !== index) { throw new Error('String index overflow'); } } dominatorIndex(): number { const nodeFieldCount = this.snapshot.nodeFieldCount; return this.snapshot.dominatorsTree[this.nodeIndex / this.snapshot.nodeFieldCount] * nodeFieldCount; } edges(): HeapSnapshotEdgeIterator { return new HeapSnapshotEdgeIterator(this); } edgesCount(): number { return (this.edgeIndexesEnd() - this.edgeIndexesStart()) / this.snapshot.edgeFieldsCount; } id(): number { throw new Error('Not implemented'); } rawName(): string { return this.snapshot.strings[this.rawNameIndex()]; } isRoot(): boolean { return this.nodeIndex === this.snapshot.rootNodeIndex; } isUserRoot(): boolean { throw new Error('Not implemented'); } isHidden(): boolean { throw new Error('Not implemented'); } isArray(): boolean { throw new Error('Not implemented'); } isSynthetic(): boolean { throw new Error('Not implemented'); } isDocumentDOMTreesRoot(): boolean { throw new Error('Not implemented'); } name(): string { return this.rawName(); } retainedSize(): number { return this.snapshot.retainedSizes[this.ordinal()]; } retainers(): HeapSnapshotRetainerEdgeIterator { return new HeapSnapshotRetainerEdgeIterator(this); } retainersCount(): number { const snapshot = this.snapshot; const ordinal = this.ordinal(); return snapshot.firstRetainerIndex[ordinal + 1] - snapshot.firstRetainerIndex[ordinal]; } selfSize(): number { const snapshot = this.snapshot; return snapshot.nodes.getValue(this.nodeIndex + snapshot.nodeSelfSizeOffset); } type(): string { return this.snapshot.nodeTypes[this.rawType()]; } traceNodeId(): number { const snapshot = this.snapshot; return snapshot.nodes.getValue(this.nodeIndex + snapshot.nodeTraceNodeIdOffset); } itemIndex(): number { return this.nodeIndex; } serialize(): HeapSnapshotModel.HeapSnapshotModel.Node { return new HeapSnapshotModel.HeapSnapshotModel.Node( this.id(), this.name(), this.distance(), this.nodeIndex, this.retainedSize(), this.selfSize(), this.type()); } rawNameIndex(): number { const snapshot = this.snapshot; return snapshot.nodes.getValue(this.nodeIndex + snapshot.nodeNameOffset); } edgeIndexesStart(): number { return this.snapshot.firstEdgeIndexes[this.ordinal()]; } edgeIndexesEnd(): number { return this.snapshot.firstEdgeIndexes[this.ordinal() + 1]; } ordinal(): number { return this.nodeIndex / this.snapshot.nodeFieldCount; } nextNodeIndex(): number { return this.nodeIndex + this.snapshot.nodeFieldCount; } rawType(): number { const snapshot = this.snapshot; return snapshot.nodes.getValue(this.nodeIndex + snapshot.nodeTypeOffset); } isFlatConsString(): boolean { if (this.rawType() !== this.snapshot.nodeConsStringType) { return false; } for (let iter = this.edges(); iter.hasNext(); iter.next()) { const edge = iter.edge; if (!edge.isInternal()) { continue; } const edgeName = edge.name(); if ((edgeName === 'first' || edgeName === 'second') && edge.node().name() === '') { return true; } } return false; } #detachednessAndClassIndex(): number { const {snapshot, nodeIndex} = this; const nodeDetachednessAndClassIndexOffset = snapshot.nodeDetachednessAndClassIndexOffset; return nodeDetachednessAndClassIndexOffset !== -1 ? snapshot.nodes.getValue(nodeIndex + nodeDetachednessAndClassIndexOffset) : (snapshot.detachednessAndClassIndexArray as Uint32Array)[nodeIndex / snapshot.nodeFieldCount]; } #setDetachednessAndClassIndex(value: number): void { const {snapshot, nodeIndex} = this; const nodeDetachednessAndClassIndexOffset = snapshot.nodeDetachednessAndClassIndexOffset; if (nodeDetachednessAndClassIndexOffset !== -1) { snapshot.nodes.setValue(nodeIndex + nodeDetachednessAndClassIndexOffset, value); } else { (snapshot.detachednessAndClassIndexArray as Uint32Array)[nodeIndex / snapshot.nodeFieldCount] = value; } } detachedness(): DOMLinkState { return this.#detachednessAndClassIndex() & BITMASK_FOR_DOM_LINK_STATE; } setDetachedness(detachedness: DOMLinkState): void { let value = this.#detachednessAndClassIndex(); value &= ~BITMASK_FOR_DOM_LINK_STATE; // Clear the old bits. value |= detachedness; // Set the new bits. this.#setDetachednessAndClassIndex(value); } } export class HeapSnapshotNodeIterator implements HeapSnapshotItemIterator { node: HeapSnapshotNode; readonly #nodesLength: number; constructor(node: HeapSnapshotNode) { this.node = node; this.#nodesLength = node.snapshot.nodes.length; } hasNext(): boolean { return this.node.nodeIndex < this.#nodesLength; } item(): HeapSnapshotNode { return this.node; } next(): void { this.node.nodeIndex = this.node.nextNodeIndex(); } } export class HeapSnapshotIndexRangeIterator implements HeapSnapshotItemIterator { readonly #itemProvider: HeapSnapshotItemIndexProvider; readonly #indexes: number[]|Uint32Array; #position: number; constructor(itemProvider: HeapSnapshotItemIndexProvider, indexes: number[]|Uint32Array) { this.#itemProvider = itemProvider; this.#indexes = indexes; this.#position = 0; } hasNext(): boolean { return this.#position < this.#indexes.length; } item(): HeapSnapshotItem { const index = this.#indexes[this.#position]; return this.#itemProvider.itemForIndex(index); } next(): void { ++this.#position; } } export class HeapSnapshotFilteredIterator implements HeapSnapshotItemIterator { #iterator: HeapSnapshotItemIterator; #filter: ((arg0: HeapSnapshotItem) => boolean)|undefined; constructor(iterator: HeapSnapshotItemIterator, filter?: ((arg0: HeapSnapshotItem) => boolean)) { this.#iterator = iterator; this.#filter = filter; this.skipFilteredItems(); } hasNext(): boolean { return this.#iterator.hasNext(); } item(): HeapSnapshotItem { return this.#iterator.item(); } next(): void { this.#iterator.next(); this.skipFilteredItems(); } private skipFilteredItems(): void { while (this.#iterator.hasNext() && this.#filter && !this.#filter(this.#iterator.item())) { this.#iterator.next(); } } } export class HeapSnapshotProgress { readonly #dispatcher: HeapSnapshotWorkerDispatcher|undefined; constructor(dispatcher?: HeapSnapshotWorkerDispatcher) { this.#dispatcher = dispatcher; } updateStatus(status: string): void { this.sendUpdateEvent(i18n.i18n.serializeUIString(status)); } updateProgress(title: string, value: number, total: number): void { const percentValue = ((total ? (value / total) : 0) * 100).toFixed(0); this.sendUpdateEvent(i18n.i18n.serializeUIString(title, {PH1: percentValue})); } reportProblem(error: string): void { // May be undefined in tests. if (this.#dispatcher) { this.#dispatcher.sendEvent(HeapSnapshotModel.HeapSnapshotModel.HeapSnapshotProgressEvent.BrokenSnapshot, error); } } private sendUpdateEvent(serializedText: string): void { // May be undefined in tests. if (this.#dispatcher) { this.#dispatcher.sendEvent(HeapSnapshotModel.HeapSnapshotModel.HeapSnapshotProgressEvent.Update, serializedText); } } } /** * An "interface" to be used when classifying plain JS objects in the snapshot. * An object matches the interface if it contains every listed property (even * if it also contains extra properties). **/ interface InterfaceDefinition { name: string; properties: string[]; } type HeapSnapshotProblemReport = Array; function appendToProblemReport(report: HeapSnapshotProblemReport, messageOrNodeIndex: string|number): void { if (report.length > 100) { return; } report.push(messageOrNodeIndex); } function formatProblemReport(snapshot: HeapSnapshot, report: HeapSnapshotProblemReport): string { const node = snapshot.rootNode(); return report .map(messageOrNodeIndex => { if (typeof messageOrNodeIndex === 'string') { return messageOrNodeIndex; } node.nodeIndex = messageOrNodeIndex; return `${node.name()} @${node.id()}`; }) .join('\n '); } function reportProblemToPrimaryWorker( problemReport: HeapSnapshotProblemReport, port: PlatformApi.HostRuntime.WorkerMessagePort): void { port.postMessage({problemReport}); } export interface Profile { /* eslint-disable @typescript-eslint/naming-convention */ root_index: number; nodes: Platform.TypedArrayUtilities.BigUint32Array; edges: Platform.TypedArrayUtilities.BigUint32Array; snapshot: HeapSnapshotHeader; samples: number[]; strings: string[]; locations: number[]; trace_function_infos: Uint32Array; trace_tree: Object; /* eslint-enable @typescript-eslint/naming-convention */ } export type LiveObjects = Record; /** The first batch of data sent from the primary worker to the secondary. **/ interface SecondaryInitArgumentsStep1 { // For each edge ordinal, this array contains the ordinal of the pointed-to node. edgeToNodeOrdinals: Uint32Array; // A copy of HeapSnapshot.firstEdgeIndexes. For each node ordinal, this array // contains the edge index of the first outgoing edge. firstEdgeIndexes: Uint32Array; nodeCount: number; edgeFieldsCount: number; nodeFieldCount: number; } /** The second batch of data sent from the primary worker to the secondary. **/ interface SecondaryInitArgumentsStep2 { rootNodeOrdinal: number; // An array with one bit per edge, where each bit indicates whether the edge // should be used when computing dominators. essentialEdgesBuffer: ArrayBuffer; } /** The third batch of data sent from the primary worker to the secondary. **/ interface SecondaryInitArgumentsStep3 { // For each node ordinal, this array contains the node's shallow size. nodeSelfSizes: Uint32Array; } type ArgumentsToBuildRetainers = SecondaryInitArgumentsStep1; interface Retainers { // For each node ordinal, this array contains the index of the first retaining edge // in the retainingEdges and retainingNodes arrays. firstRetainerIndex: Uint32Array; // For each retaining edge, this array contains the "from" node's index. retainingNodes: Uint32Array; // For each retaining edge, this array contains the index in containmentEdges // where you can find other info about the edge, such as its type and name. retainingEdges: Uint32Array; } interface ArgumentsToComputeDominatorsAndRetainedSizes extends SecondaryInitArgumentsStep1, Retainers, SecondaryInitArgumentsStep2 { // For each edge ordinal, this bit vector contains whether the edge // should be used when computing dominators. essentialEdges: Platform.TypedArrayUtilities.BitVector; // A message port for reporting problems to the primary worker. port: PlatformApi.HostRuntime.WorkerMessagePort; // For each node ordinal, this array will contain the node's shallow size. nodeSelfSizesPromise: Promise; } interface DominatorsAndRetainedSizes { // For each node ordinal, this array contains the ordinal of its immediate dominating node. dominatorsTree: Uint32Array; // For each node ordinal, this array contains the size of the subgraph it dominates, including its own size. retainedSizes: Float64Array; } interface ArgumentsToBuildDominatedNodes extends ArgumentsToComputeDominatorsAndRetainedSizes, DominatorsAndRetainedSizes {} interface DominatedNodes { // For each node ordinal, the index of its first child node in dominatedNodes. // Together with dominatedNodes, this allows traversing down the dominators tree, // whereas dominatorsTree allows upward traversal. firstDominatedNodeIndex: Uint32Array; // Node indexes of child nodes in the dominator tree. dominatedNodes: Uint32Array; } /** The data transferred from the secondary worker to the primary. **/ interface ResultsFromSecondWorker extends Retainers, DominatorsAndRetainedSizes, DominatedNodes {} /** * Initialization work is split into two threads. This class is the entry point * for work done by the second thread. **/ export class SecondaryInitManager { argsStep1: Promise; argsStep2: Promise; argsStep3: Promise; constructor(port: PlatformApi.HostRuntime.WorkerMessagePort) { const {promise: argsStep1, resolve: resolveArgsStep1} = Promise.withResolvers(); this.argsStep1 = argsStep1; const {promise: argsStep2, resolve: resolveArgsStep2} = Promise.withResolvers(); this.argsStep2 = argsStep2; const {promise: argsStep3, resolve: resolveArgsStep3} = Promise.withResolvers(); this.argsStep3 = argsStep3; const listener = (e: unknown): void => { const data = (e as PlatformApi.HostRuntime.WorkerMessageEvent).data; switch (data.step) { case 1: resolveArgsStep1(data.args); break; case 2: resolveArgsStep2(data.args); break; case 3: resolveArgsStep3(data.args); port.removeEventListener('message', listener); break; } }; port.addEventListener('message', listener); port.start(); void this.initialize(port); } private async getNodeSelfSizes(): Promise { return (await this.argsStep3).nodeSelfSizes; } private async initialize(port: PlatformApi.HostRuntime.WorkerMessagePort): Promise { try { const argsStep1 = await this.argsStep1; const retainers = HeapSnapshot.buildRetainers(argsStep1); const argsStep2 = await this.argsStep2; const args = { ...argsStep2, ...argsStep1, ...retainers, essentialEdges: Platform.TypedArrayUtilities.createBitVector(argsStep2.essentialEdgesBuffer), port, nodeSelfSizesPromise: this.getNodeSelfSizes() }; const dominatorsAndRetainedSizes = await HeapSnapshot.calculateDominatorsAndRetainedSizes(args); const dominatedNodesOutputs = HeapSnapshot.buildDominatedNodes({...args, ...dominatorsAndRetainedSizes}); const resultsFromSecondWorker: ResultsFromSecondWorker = { ...retainers, ...dominatorsAndRetainedSizes, ...dominatedNodesOutputs, }; port.postMessage({resultsFromSecondWorker}, [ // DominatorsAndRetainedSizes resultsFromSecondWorker.dominatorsTree.buffer, resultsFromSecondWorker.retainedSizes.buffer, // Retainers resultsFromSecondWorker.firstRetainerIndex.buffer, resultsFromSecondWorker.retainingNodes.buffer, resultsFromSecondWorker.retainingEdges.buffer, // DominatedNodes resultsFromSecondWorker.firstDominatedNodeIndex.buffer, resultsFromSecondWorker.dominatedNodes.buffer, ]); } catch (e) { port.postMessage({error: e + '\n' + e?.stack}); } } } /** * DOM node link state. */ const enum DOMLinkState { UNKNOWN = 0, ATTACHED = 1, DETACHED = 2, } const BITMASK_FOR_DOM_LINK_STATE = 3; // The class index is stored in the upper 30 bits of the detachedness field. const SHIFT_FOR_CLASS_INDEX = 2; // After this many properties, inferInterfaceDefinitions can stop adding more // properties to an interface definition if the name is getting too long. const MIN_INTERFACE_PROPERTY_COUNT = 1; // The maximum length of an interface name produced by inferInterfaceDefinitions. // This limit can be exceeded if the first MIN_INTERFACE_PROPERTY_COUNT property // names are long. const MAX_INTERFACE_NAME_LENGTH = 120; // Each interface definition produced by inferInterfaceDefinitions will match at // least this many objects. There's no point in defining interfaces which match // only a single object. const MIN_OBJECT_COUNT_PER_INTERFACE = 2; // Each interface definition produced by inferInterfaceDefinitions should // match at least 1 out of 1000 Objects in the heap. Otherwise, we end up with a // long tail of unpopular interfaces that don't help analysis. const MIN_OBJECT_PROPORTION_PER_INTERFACE = 1000; export abstract class HeapSnapshot { nodes: Platform.TypedArrayUtilities.BigUint32Array; containmentEdges: Platform.TypedArrayUtilities.BigUint32Array; readonly #metaNode: HeapSnapshotMetaInfo; readonly #rawSamples: number[]; #samples: HeapSnapshotModel.HeapSnapshotModel.Samples|null = null; strings: string[]; readonly #locations: number[]; readonly #progress: HeapSnapshotProgress; readonly #noDistance = -5; rootNodeIndexInternal = 0; #snapshotDiffs: Record> = {}; #aggregatesForDiff?: { interfaceDefinitions: string, aggregates: Record, }; #aggregates: Record> = {}; #aggregatesSortedFlags: Record = {}; profile: Profile; nodeTypeOffset!: number; nodeNameOffset!: number; nodeIdOffset!: number; nodeSelfSizeOffset!: number; #nodeEdgeCountOffset!: number; nodeTraceNodeIdOffset!: number; nodeFieldCount!: number; nodeTypes!: string[]; nodeArrayType!: number; nodeHiddenType!: number; nodeObjectType!: number; nodeNativeType!: number; nodeStringType!: number; nodeConsStringType!: number; nodeSlicedStringType!: number; nodeCodeType!: number; nodeSyntheticType!: number; nodeClosureType!: number; nodeRegExpType!: number; edgeFieldsCount!: number; edgeTypeOffset!: number; edgeNameOffset!: number; edgeToNodeOffset!: number; edgeTypes!: string[]; edgeElementType!: number; edgeHiddenType!: number; edgeInternalType!: number; edgeShortcutType!: number; edgeWeakType!: number; edgeInvisibleType!: number; edgePropertyType!: number; #locationIndexOffset!: number; #locationScriptIdOffset!: number; #locationLineOffset!: number; #locationColumnOffset!: number; #locationFieldCount!: number; nodeCount!: number; #edgeCount!: number; retainedSizes!: Float64Array; firstEdgeIndexes!: Uint32Array; retainingNodes!: Uint32Array; retainingEdges!: Uint32Array; firstRetainerIndex!: Uint32Array; nodeDistances!: Int32Array; firstDominatedNodeIndex!: Uint32Array; dominatedNodes!: Uint32Array; dominatorsTree!: Uint32Array; #allocationProfile!: AllocationProfile; nodeDetachednessAndClassIndexOffset!: number; #locationMap!: Map; #ignoredNodesInRetainersView = new Set(); #ignoredEdgesInRetainersView = new Set(); #nodeDistancesForRetainersView: Int32Array|undefined; #edgeNamesThatAreNotWeakMaps: Platform.TypedArrayUtilities.BitVector; detachednessAndClassIndexArray?: Uint32Array; #interfaceNames = new Map(); #interfaceDefinitions?: InterfaceDefinition[]; constructor(profile: Profile, progress: HeapSnapshotProgress) { this.nodes = profile.nodes; this.containmentEdges = profile.edges; this.#metaNode = profile.snapshot.meta; this.#rawSamples = profile.samples; this.strings = profile.strings; this.#locations = profile.locations; this.#progress = progress; if (profile.snapshot.root_index) { this.rootNodeIndexInternal = profile.snapshot.root_index; } this.profile = profile; this.#edgeNamesThatAreNotWeakMaps = Platform.TypedArrayUtilities.createBitVector(this.strings.length); } async initialize(secondWorker: PlatformApi.HostRuntime.WorkerMessagePort): Promise { const meta = this.#metaNode; this.nodeTypeOffset = meta.node_fields.indexOf('type'); this.nodeNameOffset = meta.node_fields.indexOf('name'); this.nodeIdOffset = meta.node_fields.indexOf('id'); this.nodeSelfSizeOffset = meta.node_fields.indexOf('self_size'); this.#nodeEdgeCountOffset = meta.node_fields.indexOf('edge_count'); this.nodeTraceNodeIdOffset = meta.node_fields.indexOf('trace_node_id'); this.nodeDetachednessAndClassIndexOffset = meta.node_fields.indexOf('detachedness'); this.nodeFieldCount = meta.node_fields.length; this.nodeTypes = meta.node_types[this.nodeTypeOffset]; this.nodeArrayType = this.nodeTypes.indexOf('array'); this.nodeHiddenType = this.nodeTypes.indexOf('hidden'); this.nodeObjectType = this.nodeTypes.indexOf('object'); this.nodeNativeType = this.nodeTypes.indexOf('native'); this.nodeStringType = this.nodeTypes.indexOf('string'); this.nodeConsStringType = this.nodeTypes.indexOf('concatenated string'); this.nodeSlicedStringType = this.nodeTypes.indexOf('sliced string'); this.nodeCodeType = this.nodeTypes.indexOf('code'); this.nodeSyntheticType = this.nodeTypes.indexOf('synthetic'); this.nodeClosureType = this.nodeTypes.indexOf('closure'); this.nodeRegExpType = this.nodeTypes.indexOf('regexp'); this.edgeFieldsCount = meta.edge_fields.length; this.edgeTypeOffset = meta.edge_fields.indexOf('type'); this.edgeNameOffset = meta.edge_fields.indexOf('name_or_index'); this.edgeToNodeOffset = meta.edge_fields.indexOf('to_node'); this.edgeTypes = meta.edge_types[this.edgeTypeOffset]; this.edgeTypes.push('invisible'); this.edgeElementType = this.edgeTypes.indexOf('element'); this.edgeHiddenType = this.edgeTypes.indexOf('hidden'); this.edgeInternalType = this.edgeTypes.indexOf('internal'); this.edgeShortcutType = this.edgeTypes.indexOf('shortcut'); this.edgeWeakType = this.edgeTypes.indexOf('weak'); this.edgeInvisibleType = this.edgeTypes.indexOf('invisible'); this.edgePropertyType = this.edgeTypes.indexOf('property'); const locationFields = meta.location_fields || []; this.#locationIndexOffset = locationFields.indexOf('object_index'); this.#locationScriptIdOffset = locationFields.indexOf('script_id'); this.#locationLineOffset = locationFields.indexOf('line'); this.#locationColumnOffset = locationFields.indexOf('column'); this.#locationFieldCount = locationFields.length; this.nodeCount = this.nodes.length / this.nodeFieldCount; this.#edgeCount = this.containmentEdges.length / this.edgeFieldsCount; this.#progress.updateStatus('Building edge indexes…'); this.firstEdgeIndexes = new Uint32Array(this.nodeCount + 1); this.buildEdgeIndexes(); this.#progress.updateStatus('Building retainers…'); const resultsFromSecondWorker = this.startInitStep1InSecondThread(secondWorker); this.#progress.updateStatus('Propagating DOM state…'); this.propagateDOMState(); this.#progress.updateStatus('Calculating node flags…'); this.calculateFlags(); this.#progress.updateStatus('Building dominated nodes…'); this.startInitStep2InSecondThread(secondWorker); this.#progress.updateStatus('Calculating shallow sizes…'); this.calculateShallowSizes(); this.#progress.updateStatus('Calculating retained sizes…'); this.startInitStep3InSecondThread(secondWorker); this.#progress.updateStatus('Calculating distances…'); this.nodeDistances = new Int32Array(this.nodeCount); this.calculateDistances(/* isForRetainersView=*/ false); this.#progress.updateStatus('Calculating object names…'); this.calculateObjectNames(); this.applyInterfaceDefinitions(this.inferInterfaceDefinitions()); this.#progress.updateStatus('Calculating samples…'); this.buildSamples(); this.#progress.updateStatus('Building locations…'); this.buildLocationMap(); this.#progress.updateStatus('Calculating retained sizes…'); await this.installResultsFromSecondThread(resultsFromSecondWorker); this.#progress.updateStatus('Calculating statistics…'); this.calculateStatistics(); if (this.profile.snapshot.trace_function_count) { this.#progress.updateStatus('Building allocation statistics…'); const nodes = this.nodes; const nodesLength = nodes.length; const nodeFieldCount = this.nodeFieldCount; const node = this.rootNode(); const liveObjects: LiveObjects = {}; for (let nodeIndex = 0; nodeIndex < nodesLength; nodeIndex += nodeFieldCount) { node.nodeIndex = nodeIndex; const traceNodeId = node.traceNodeId(); let stats: { count: number, size: number, ids: number[], } = liveObjects[traceNodeId]; if (!stats) { liveObjects[traceNodeId] = stats = {count: 0, size: 0, ids: []}; } stats.count++; stats.size += node.selfSize(); stats.ids.push(node.id()); } this.#allocationProfile = new AllocationProfile(this.profile, liveObjects); } this.#progress.updateStatus('Finished processing.'); } private startInitStep1InSecondThread(secondWorker: PlatformApi.HostRuntime.WorkerMessagePort): Promise { const resultsFromSecondWorker = new Promise((resolve, reject) => { const listener = (e: unknown): void => { const data = (e as PlatformApi.HostRuntime.WorkerMessageEvent).data; if (data?.problemReport) { const problemReport: HeapSnapshotProblemReport = data.problemReport; console.warn(formatProblemReport(this, problemReport)); } else if (data?.resultsFromSecondWorker) { secondWorker.removeEventListener('message', listener); resolve(data.resultsFromSecondWorker); } else if (data?.error) { secondWorker.removeEventListener('message', listener); reject(data.error); } }; secondWorker.addEventListener('message', listener); secondWorker.start(); }); const edgeCount = this.#edgeCount; const {containmentEdges, edgeToNodeOffset, edgeFieldsCount, nodeFieldCount} = this; const edgeToNodeOrdinals = new Uint32Array(edgeCount); for (let edgeOrdinal = 0; edgeOrdinal < edgeCount; ++edgeOrdinal) { const toNodeIndex = containmentEdges.getValue(edgeOrdinal * edgeFieldsCount + edgeToNodeOffset); if (toNodeIndex % nodeFieldCount) { throw new Error('Invalid toNodeIndex ' + toNodeIndex); } edgeToNodeOrdinals[edgeOrdinal] = toNodeIndex / nodeFieldCount; } const args: SecondaryInitArgumentsStep1 = { edgeToNodeOrdinals, firstEdgeIndexes: this.firstEdgeIndexes, nodeCount: this.nodeCount, edgeFieldsCount: this.edgeFieldsCount, nodeFieldCount: this.nodeFieldCount, }; // Note that firstEdgeIndexes is not transferred; each thread needs its own copy. secondWorker.postMessage({step: 1, args}, [edgeToNodeOrdinals.buffer]); return resultsFromSecondWorker; } private startInitStep2InSecondThread(secondWorker: PlatformApi.HostRuntime.WorkerMessagePort): void { const rootNodeOrdinal = this.rootNodeIndexInternal / this.nodeFieldCount; const essentialEdges = this.initEssentialEdges(); const args: SecondaryInitArgumentsStep2 = {rootNodeOrdinal, essentialEdgesBuffer: essentialEdges.buffer}; secondWorker.postMessage({step: 2, args}, [essentialEdges.buffer]); } private startInitStep3InSecondThread(secondWorker: PlatformApi.HostRuntime.WorkerMessagePort): void { const {nodes, nodeFieldCount, nodeSelfSizeOffset, nodeCount} = this; const nodeSelfSizes = new Uint32Array(nodeCount); for (let nodeOrdinal = 0; nodeOrdinal < nodeCount; ++nodeOrdinal) { nodeSelfSizes[nodeOrdinal] = nodes.getValue(nodeOrdinal * nodeFieldCount + nodeSelfSizeOffset); } const args: SecondaryInitArgumentsStep3 = {nodeSelfSizes}; secondWorker.postMessage({step: 3, args}, [nodeSelfSizes.buffer]); } private async installResultsFromSecondThread(resultsFromSecondWorker: Promise): Promise { const results = await resultsFromSecondWorker; this.dominatedNodes = results.dominatedNodes; this.dominatorsTree = results.dominatorsTree; this.firstDominatedNodeIndex = results.firstDominatedNodeIndex; this.firstRetainerIndex = results.firstRetainerIndex; this.retainedSizes = results.retainedSizes; this.retainingEdges = results.retainingEdges; this.retainingNodes = results.retainingNodes; } private buildEdgeIndexes(): void { const nodes = this.nodes; const nodeCount = this.nodeCount; const firstEdgeIndexes = this.firstEdgeIndexes; const nodeFieldCount = this.nodeFieldCount; const edgeFieldsCount = this.edgeFieldsCount; const nodeEdgeCountOffset = this.#nodeEdgeCountOffset; firstEdgeIndexes[nodeCount] = this.containmentEdges.length; for (let nodeOrdinal = 0, edgeIndex = 0; nodeOrdinal < nodeCount; ++nodeOrdinal) { firstEdgeIndexes[nodeOrdinal] = edgeIndex; edgeIndex += nodes.getValue(nodeOrdinal * nodeFieldCount + nodeEdgeCountOffset) * edgeFieldsCount; } } static buildRetainers(inputs: ArgumentsToBuildRetainers): Retainers { const {edgeToNodeOrdinals, firstEdgeIndexes, nodeCount, edgeFieldsCount, nodeFieldCount} = inputs; const edgeCount = edgeToNodeOrdinals.length; const retainingNodes = new Uint32Array(edgeCount); const retainingEdges = new Uint32Array(edgeCount); const firstRetainerIndex = new Uint32Array(nodeCount + 1); for (let edgeOrdinal = 0; edgeOrdinal < edgeCount; ++edgeOrdinal) { const toNodeOrdinal = edgeToNodeOrdinals[edgeOrdinal]; ++firstRetainerIndex[toNodeOrdinal]; } for (let i = 0, firstUnusedRetainerSlot = 0; i < nodeCount; i++) { const retainersCount = firstRetainerIndex[i]; firstRetainerIndex[i] = firstUnusedRetainerSlot; retainingNodes[firstUnusedRetainerSlot] = retainersCount; firstUnusedRetainerSlot += retainersCount; } firstRetainerIndex[nodeCount] = retainingNodes.length; let nextNodeFirstEdgeIndex: number = firstEdgeIndexes[0]; for (let srcNodeOrdinal = 0; srcNodeOrdinal < nodeCount; ++srcNodeOrdinal) { const firstEdgeIndex = nextNodeFirstEdgeIndex; nextNodeFirstEdgeIndex = firstEdgeIndexes[srcNodeOrdinal + 1]; const srcNodeIndex = srcNodeOrdinal * nodeFieldCount; for (let edgeIndex = firstEdgeIndex; edgeIndex < nextNodeFirstEdgeIndex; edgeIndex += edgeFieldsCount) { const toNodeOrdinal = edgeToNodeOrdinals[edgeIndex / edgeFieldsCount]; const firstRetainerSlotIndex = firstRetainerIndex[toNodeOrdinal]; const nextUnusedRetainerSlotIndex = firstRetainerSlotIndex + (--retainingNodes[firstRetainerSlotIndex]); retainingNodes[nextUnusedRetainerSlotIndex] = srcNodeIndex; retainingEdges[nextUnusedRetainerSlotIndex] = edgeIndex; } } return { retainingNodes, retainingEdges, firstRetainerIndex, }; } abstract createNode(_nodeIndex?: number): HeapSnapshotNode; abstract createEdge(_edgeIndex: number): JSHeapSnapshotEdge; abstract createRetainingEdge(_retainerIndex: number): JSHeapSnapshotRetainerEdge; private allNodes(): HeapSnapshotNodeIterator { return new HeapSnapshotNodeIterator(this.rootNode()); } rootNode(): HeapSnapshotNode { return this.createNode(this.rootNodeIndexInternal); } get rootNodeIndex(): number { return this.rootNodeIndexInternal; } get totalSize(): number { return this.rootNode().retainedSize() + (this.profile.snapshot.extra_native_bytes ?? 0); } private createFilter(nodeFilter: HeapSnapshotModel.HeapSnapshotModel.NodeFilter): ((arg0: HeapSnapshotNode) => boolean)|undefined { const {minNodeId, maxNodeId, allocationNodeId, filterName} = nodeFilter; let filter; if (typeof allocationNodeId === 'number') { filter = this.createAllocationStackFilter(allocationNodeId); if (!filter) { throw new Error('Unable to create filter'); } // @ts-expect-error key can be added as a static property filter.key = 'AllocationNodeId: ' + allocationNodeId; } else if (typeof minNodeId === 'number' && typeof maxNodeId === 'number') { filter = this.createNodeIdFilter(minNodeId, maxNodeId); // @ts-expect-error key can be added as a static property filter.key = 'NodeIdRange: ' + minNodeId + '..' + maxNodeId; } else if (filterName !== undefined) { filter = this.createNamedFilter(filterName); // @ts-expect-error key can be added as a static property filter.key = 'NamedFilter: ' + filterName; } return filter; } search( searchConfig: HeapSnapshotModel.HeapSnapshotModel.SearchConfig, nodeFilter: HeapSnapshotModel.HeapSnapshotModel.NodeFilter): number[] { const query = searchConfig.query; function filterString(matchedStringIndexes: Set, string: string, index: number): Set { if (string.indexOf(query) !== -1) { matchedStringIndexes.add(index); } return matchedStringIndexes; } const regexp = searchConfig.isRegex ? new RegExp(query) : Platform.StringUtilities.createPlainTextSearchRegex(query, 'i'); function filterRegexp(matchedStringIndexes: Set, string: string, index: number): Set { if (regexp.test(string)) { matchedStringIndexes.add(index); } return matchedStringIndexes; } const useRegExp = searchConfig.isRegex || !searchConfig.caseSensitive; const stringFilter = useRegExp ? filterRegexp : filterString; const stringIndexes = this.strings.reduce(stringFilter, new Set()); const filter = this.createFilter(nodeFilter); const nodeIds = []; const nodesLength = this.nodes.length; const nodes = this.nodes; const nodeNameOffset = this.nodeNameOffset; const nodeIdOffset = this.nodeIdOffset; const nodeFieldCount = this.nodeFieldCount; const node = this.rootNode(); for (let nodeIndex = 0; nodeIndex < nodesLength; nodeIndex += nodeFieldCount) { node.nodeIndex = nodeIndex; if (filter && !filter(node)) { continue; } if (node.selfSize() === 0) { // Nodes with size zero are omitted in the data grid, so avoid returning // search results that can't be navigated to. continue; } const name = node.name(); if (name === node.rawName()) { // If the string displayed to the user matches the raw name from the // snapshot, then we can use the Set computed above. This avoids // repeated work when multiple nodes have the same name. if (stringIndexes.has(nodes.getValue(nodeIndex + nodeNameOffset))) { nodeIds.push(nodes.getValue(nodeIndex + nodeIdOffset)); } // If the node is displaying a customized name, then we must perform the // full string search within that name here. } else if (useRegExp ? regexp.test(name) : (name.indexOf(query) !== -1)) { nodeIds.push(nodes.getValue(nodeIndex + nodeIdOffset)); } } return nodeIds; } aggregatesWithFilter(nodeFilter: HeapSnapshotModel.HeapSnapshotModel.NodeFilter): Record { const filter = this.createFilter(nodeFilter); // @ts-expect-error key is added in createFilter const key = filter ? filter.key : 'allObjects'; return this.getAggregatesByClassKey(false, key, filter); } private createNodeIdFilter(minNodeId: number, maxNodeId: number): (arg0: HeapSnapshotNode) => boolean { function nodeIdFilter(node: HeapSnapshotNode): boolean { const id = node.id(); return id > minNodeId && id <= maxNodeId; } return nodeIdFilter; } private createAllocationStackFilter(bottomUpAllocationNodeId: number): ((arg0: HeapSnapshotNode) => boolean)|undefined { if (!this.#allocationProfile) { throw new Error('No Allocation Profile provided'); } const traceIds = this.#allocationProfile.traceIds(bottomUpAllocationNodeId); if (!traceIds.length) { return undefined; } const set: Record = {}; for (let i = 0; i < traceIds.length; i++) { set[traceIds[i]] = true; } function traceIdFilter(node: HeapSnapshotNode): boolean { return Boolean(set[node.traceNodeId()]); } return traceIdFilter; } private createNamedFilter(filterName: string): (node: HeapSnapshotNode) => boolean { // Allocate an array with a single bit per node, which can be used by each // specific filter implemented below. const bitmap = Platform.TypedArrayUtilities.createBitVector(this.nodeCount); const getBit = (node: HeapSnapshotNode): boolean => { const ordinal = node.nodeIndex / this.nodeFieldCount; return bitmap.getBit(ordinal); }; // Traverses the graph in breadth-first order with the given filter, and // sets the bit in `bitmap` for every visited node. const traverse = (filter: (node: HeapSnapshotNode, edge: HeapSnapshotEdge) => boolean): void => { const distances = new Int32Array(this.nodeCount); for (let i = 0; i < this.nodeCount; ++i) { distances[i] = this.#noDistance; } const nodesToVisit = new Uint32Array(this.nodeCount); distances[this.rootNode().ordinal()] = 0; nodesToVisit[0] = this.rootNode().nodeIndex; const nodesToVisitLength = 1; this.bfs(nodesToVisit, nodesToVisitLength, distances, filter); for (let i = 0; i < this.nodeCount; ++i) { if (distances[i] !== this.#noDistance) { bitmap.setBit(i); } } }; const markUnreachableNodes = (): void => { for (let i = 0; i < this.nodeCount; ++i) { if (this.nodeDistances[i] === this.#noDistance) { bitmap.setBit(i); } } }; switch (filterName) { case 'objectsRetainedByDetachedDomNodes': // Traverse the graph, avoiding detached nodes. traverse((_node: HeapSnapshotNode, edge: HeapSnapshotEdge) => { return edge.node().detachedness() !== DOMLinkState.DETACHED; }); markUnreachableNodes(); return (node: HeapSnapshotNode) => !getBit(node); case 'objectsRetainedByConsole': // Traverse the graph, avoiding edges that represent globals owned by // the DevTools console. traverse((node: HeapSnapshotNode, edge: HeapSnapshotEdge) => { return !(node.isSynthetic() && edge.hasStringName() && edge.name().endsWith(' / DevTools console')); }); markUnreachableNodes(); return (node: HeapSnapshotNode) => !getBit(node); case 'duplicatedStrings': { const stringToNodeIndexMap = new Map(); const node = this.createNode(0); for (let i = 0; i < this.nodeCount; ++i) { node.nodeIndex = i * this.nodeFieldCount; const rawType = node.rawType(); if (rawType === this.nodeStringType || rawType === this.nodeConsStringType) { // Check whether the cons string is already "flattened", meaning // that one of its two parts is the empty string. If so, we should // skip it. We don't help anyone by reporting a flattened cons // string as a duplicate with its own content, since V8 controls // that behavior internally. if (node.isFlatConsString()) { continue; } const name = node.name(); const alreadyVisitedNodeIndex = stringToNodeIndexMap.get(name); if (alreadyVisitedNodeIndex === undefined) { stringToNodeIndexMap.set(name, node.nodeIndex); } else { bitmap.setBit(alreadyVisitedNodeIndex / this.nodeFieldCount); bitmap.setBit(node.nodeIndex / this.nodeFieldCount); } } } return getBit; } case 'objectsRetainedByEventHandlers': { // This filter is based on the assumption that event handler functions are contained // (directly or indirectly) by V8EventListener nodes. In particular, the callback_object_ // field of V8EventListener points to either the function used as the event handler, // or to a framework-specific wrapper object that in turn contains the actual handler. // // The filter works in two steps: // 1. Identify all event handler functions and mark them in a bitmap. // 2. Traverse the graph, avoiding paths that pass through any of the event handlers const node = this.createNode(0); const nodeFieldCount = this.nodeFieldCount; // First, identify which nodes are event handlers const eventHandlerBitmap = Platform.TypedArrayUtilities.createBitVector(this.nodeCount); // Iterate all nodes looking for V8EventListener objects for (let i = 0; i < this.nodeCount; ++i) { node.nodeIndex = i * nodeFieldCount; // Check if this node is a V8EventListener if (node.rawName() === 'V8EventListener') { // Get the callback_object_ (edge "1") const callbackNode = this.getEdgeTarget(node, '1'); if (!callbackNode) { continue; } const callbackOrdinal = callbackNode.nodeIndex / nodeFieldCount; // Check if callback has a "code" edge (direct function handler) if (this.getEdgeTarget(callbackNode, 'code')) { eventHandlerBitmap.setBit(callbackOrdinal); continue; } // Check if any child has a "code" edge (framework wrapper) let foundChildWithCode = false; for (let childEdgeIt = callbackNode.edges(); childEdgeIt.hasNext(); childEdgeIt.next()) { const childNode = childEdgeIt.item().node(); if (this.getEdgeTarget(childNode, 'code')) { eventHandlerBitmap.setBit(childNode.nodeIndex / nodeFieldCount); foundChildWithCode = true; break; } } // Fallback to marking the callback node itself if (!foundChildWithCode) { eventHandlerBitmap.setBit(callbackOrdinal); } } } // Traverse the graph, avoiding paths that pass through event handlers traverse((currentNode: HeapSnapshotNode, edge: HeapSnapshotEdge) => { const targetNode = edge.node(); const targetOrdinal = targetNode.nodeIndex / nodeFieldCount; // Return false (don't traverse) if the target node is an event handler return !eventHandlerBitmap.getBit(targetOrdinal); }); markUnreachableNodes(); return (node: HeapSnapshotNode) => !getBit(node); } } throw new Error('Invalid filter name'); } getAggregatesByClassKey(sortedIndexes: boolean, key?: string, filter?: ((arg0: HeapSnapshotNode) => boolean)): Record { let aggregates: Record; if (key && this.#aggregates[key]) { aggregates = this.#aggregates[key]; } else { const aggregatesMap = this.buildAggregates(filter); this.calculateClassesRetainedSize(aggregatesMap, filter); // In the two previous steps, we used class keys that were simple and // could be produced quickly. For many objects, this meant using the index // of the string containing its class name. However, string indices are // not consistent across snapshots, and this aggregate data might end up // being used in a comparison, so here we convert to a more durable format // for class keys. aggregates = Object.create(null); for (const [classKey, aggregate] of aggregatesMap.entries()) { const newKey = this.#classKeyFromClassKey(classKey); aggregates[newKey] = aggregate; } if (key) { this.#aggregates[key] = aggregates; } } if (sortedIndexes && (!key || !this.#aggregatesSortedFlags[key])) { this.sortAggregateIndexes(aggregates); if (key) { this.#aggregatesSortedFlags[key] = sortedIndexes; } } return aggregates; } allocationTracesTops(): HeapSnapshotModel.HeapSnapshotModel.SerializedAllocationNode[] { return this.#allocationProfile.serializeTraceTops(); } allocationNodeCallers(nodeId: number): HeapSnapshotModel.HeapSnapshotModel.AllocationNodeCallers { return this.#allocationProfile.serializeCallers(nodeId); } allocationStack(nodeIndex: number): HeapSnapshotModel.HeapSnapshotModel.AllocationStackFrame[]|null { const node = this.createNode(nodeIndex); const allocationNodeId = node.traceNodeId(); if (!allocationNodeId) { return null; } return this.#allocationProfile.serializeAllocationStack(allocationNodeId); } aggregatesForDiff(interfaceDefinitions: string): Record { if (this.#aggregatesForDiff?.interfaceDefinitions === interfaceDefinitions) { return this.#aggregatesForDiff.aggregates; } // Temporarily apply the interface definitions from the other snapshot. const originalInterfaceDefinitions = this.#interfaceDefinitions; this.applyInterfaceDefinitions(JSON.parse(interfaceDefinitions) as InterfaceDefinition[]); const aggregates = this.getAggregatesByClassKey(true, 'allObjects'); this.applyInterfaceDefinitions(originalInterfaceDefinitions ?? []); const result: Record = {}; const node = this.createNode(); for (const classKey in aggregates) { const aggregate = aggregates[classKey]; const indexes = aggregate.idxs; const ids = new Array(indexes.length); const selfSizes = new Array(indexes.length); for (let i = 0; i < indexes.length; i++) { node.nodeIndex = indexes[i]; ids[i] = node.id(); selfSizes[i] = node.selfSize(); } result[classKey] = {name: node.className(), indexes, ids, selfSizes}; } this.#aggregatesForDiff = {interfaceDefinitions, aggregates: result}; return result; } isUserRoot(_node: HeapSnapshotNode): boolean { return true; } calculateShallowSizes(): void { } calculateDistances( isForRetainersView: boolean, filter?: ((arg0: HeapSnapshotNode, arg1: HeapSnapshotEdge) => boolean)): void { const nodeCount = this.nodeCount; if (isForRetainersView) { const originalFilter = filter; filter = (node: HeapSnapshotNode, edge: HeapSnapshotEdge) => { return !this.#ignoredNodesInRetainersView.has(edge.nodeIndex()) && (!originalFilter || originalFilter(node, edge)); }; if (this.#nodeDistancesForRetainersView === undefined) { this.#nodeDistancesForRetainersView = new Int32Array(nodeCount); } } const distances = isForRetainersView ? (this.#nodeDistancesForRetainersView as Int32Array) : this.nodeDistances; const noDistance = this.#noDistance; for (let i = 0; i < nodeCount; ++i) { distances[i] = noDistance; } const nodesToVisit = new Uint32Array(this.nodeCount); let nodesToVisitLength = 0; // BFS for user root objects. for (let iter = this.rootNode().edges(); iter.hasNext(); iter.next()) { const node = iter.edge.node(); if (this.isUserRoot(node)) { distances[node.ordinal()] = 1; nodesToVisit[nodesToVisitLength++] = node.nodeIndex; } } this.bfs(nodesToVisit, nodesToVisitLength, distances, filter); // BFS for objects not reached from user roots. distances[this.rootNode().ordinal()] = nodesToVisitLength > 0 ? HeapSnapshotModel.HeapSnapshotModel.baseSystemDistance : 0; nodesToVisit[0] = this.rootNode().nodeIndex; nodesToVisitLength = 1; this.bfs(nodesToVisit, nodesToVisitLength, distances, filter); } private bfs( nodesToVisit: Uint32Array, nodesToVisitLength: number, distances: Int32Array, filter?: ((arg0: HeapSnapshotNode, arg1: HeapSnapshotEdge) => boolean)): void { // Preload fields into local variables for better performance. const edgeFieldsCount = this.edgeFieldsCount; const nodeFieldCount = this.nodeFieldCount; const containmentEdges = this.containmentEdges; const firstEdgeIndexes = this.firstEdgeIndexes; const edgeToNodeOffset = this.edgeToNodeOffset; const edgeTypeOffset = this.edgeTypeOffset; const nodeCount = this.nodeCount; const edgeWeakType = this.edgeWeakType; const noDistance = this.#noDistance; let index = 0; const edge = this.createEdge(0); const node = this.createNode(0); while (index < nodesToVisitLength) { const nodeIndex = nodesToVisit[index++]; // shift generates too much garbage. const nodeOrdinal = nodeIndex / nodeFieldCount; const distance = distances[nodeOrdinal] + 1; const firstEdgeIndex = firstEdgeIndexes[nodeOrdinal]; const edgesEnd = firstEdgeIndexes[nodeOrdinal + 1]; node.nodeIndex = nodeIndex; for (let edgeIndex = firstEdgeIndex; edgeIndex < edgesEnd; edgeIndex += edgeFieldsCount) { const edgeType = containmentEdges.getValue(edgeIndex + edgeTypeOffset); if (edgeType === edgeWeakType) { continue; } const childNodeIndex = containmentEdges.getValue(edgeIndex + edgeToNodeOffset); const childNodeOrdinal = childNodeIndex / nodeFieldCount; if (distances[childNodeOrdinal] !== noDistance) { continue; } edge.edgeIndex = edgeIndex; if (filter && !filter(node, edge)) { continue; } distances[childNodeOrdinal] = distance; nodesToVisit[nodesToVisitLength++] = childNodeIndex; } } if (nodesToVisitLength > nodeCount) { throw new Error( 'BFS failed. Nodes to visit (' + nodesToVisitLength + ') is more than nodes count (' + nodeCount + ')'); } } private buildAggregates(filter?: ((arg0: HeapSnapshotNode) => boolean)): Map { const aggregates = new Map(); const nodes = this.nodes; const nodesLength = nodes.length; const nodeFieldCount = this.nodeFieldCount; const selfSizeOffset = this.nodeSelfSizeOffset; const node = this.rootNode(); const nodeDistances = this.nodeDistances; for (let nodeIndex = 0; nodeIndex < nodesLength; nodeIndex += nodeFieldCount) { node.nodeIndex = nodeIndex; if (filter && !filter(node)) { continue; } const selfSize = nodes.getValue(nodeIndex + selfSizeOffset); if (!selfSize) { continue; } const classKey = node.classKeyInternal(); const nodeOrdinal = nodeIndex / nodeFieldCount; const distance = nodeDistances[nodeOrdinal]; let aggregate = aggregates.get(classKey); if (!aggregate) { aggregate = { count: 1, distance, self: selfSize, maxRet: 0, name: node.className(), idxs: [nodeIndex], }; aggregates.set(classKey, aggregate); } else { aggregate.distance = Math.min(aggregate.distance, distance); ++aggregate.count; aggregate.self += selfSize; aggregate.idxs.push(nodeIndex); } } // Shave off provisionally allocated space. for (const aggregate of aggregates.values()) { aggregate.idxs = aggregate.idxs.slice(); } return aggregates; } private calculateClassesRetainedSize( aggregates: Map, filter?: ((arg0: HeapSnapshotNode) => boolean)): void { const rootNodeIndex = this.rootNodeIndexInternal; const node = this.createNode(rootNodeIndex); const list = [rootNodeIndex]; const sizes = [-1]; const classKeys: Array = []; const seenClassKeys = new Map(); const nodeFieldCount = this.nodeFieldCount; const dominatedNodes = this.dominatedNodes; const firstDominatedNodeIndex = this.firstDominatedNodeIndex; while (list.length) { const nodeIndex = (list.pop() as number); node.nodeIndex = nodeIndex; let classKey = node.classKeyInternal(); const seen = Boolean(seenClassKeys.get(classKey)); const nodeOrdinal = nodeIndex / nodeFieldCount; const dominatedIndexFrom = firstDominatedNodeIndex[nodeOrdinal]; const dominatedIndexTo = firstDominatedNodeIndex[nodeOrdinal + 1]; if (!seen && (!filter || filter(node)) && node.selfSize()) { (aggregates.get(classKey) as HeapSnapshotModel.HeapSnapshotModel.AggregatedInfo).maxRet += node.retainedSize(); if (dominatedIndexFrom !== dominatedIndexTo) { seenClassKeys.set(classKey, true); sizes.push(list.length); classKeys.push(classKey); } } for (let i = dominatedIndexFrom; i < dominatedIndexTo; i++) { list.push(dominatedNodes[i]); } const l = list.length; while (sizes[sizes.length - 1] === l) { sizes.pop(); classKey = (classKeys.pop() as string); seenClassKeys.set(classKey, false); } } } private sortAggregateIndexes(aggregates: Record): void { const nodeA = this.createNode(); const nodeB = this.createNode(); for (const clss in aggregates) { aggregates[clss].idxs.sort((idxA, idxB) => { nodeA.nodeIndex = idxA; nodeB.nodeIndex = idxB; return nodeA.id() < nodeB.id() ? -1 : 1; }); } } tryParseWeakMapEdgeName(edgeNameIndex: number): {duplicatedPart: string, tableId: string}|undefined { const previousResult = this.#edgeNamesThatAreNotWeakMaps.getBit(edgeNameIndex); if (previousResult) { return undefined; } const edgeName = this.strings[edgeNameIndex]; const ephemeronNameRegex = /^\d+(? \/ part of key $.*? @\d+$ -> value $.*? @\d+$ pair in WeakMap $table @(?\d+)$)$/; const match = edgeName.match(ephemeronNameRegex); if (!match) { this.#edgeNamesThatAreNotWeakMaps.setBit(edgeNameIndex); return undefined; } return match.groups as {duplicatedPart: string, tableId: string}; } private computeIsEssentialEdge( nodeIndex: number, edgeIndex: number, userObjectsMapAndFlag: {map: Uint8Array, flag: number}|null): boolean { const edgeType = this.containmentEdges.getValue(edgeIndex + this.edgeTypeOffset); // Values in WeakMaps are retained by the key and table together. Removing // either the key or the table would be sufficient to remove the edge from // the other one, so we needn't use both of those edges when computing // dominators. We've found that the edge from the key generally produces // more useful results, so here we skip the edge from the table. if (edgeType === this.edgeInternalType) { const edgeNameIndex = this.containmentEdges.getValue(edgeIndex + this.edgeNameOffset); const match = this.tryParseWeakMapEdgeName(edgeNameIndex); if (match) { const nodeId = this.nodes.getValue(nodeIndex + this.nodeIdOffset); if (nodeId === parseInt(match.tableId, 10)) { return false; } } } // Weak edges never retain anything. if (edgeType === this.edgeWeakType) { return false; } const childNodeIndex = this.containmentEdges.getValue(edgeIndex + this.edgeToNodeOffset); // Ignore self edges. if (nodeIndex === childNodeIndex) { return false; } if (nodeIndex !== this.rootNodeIndex) { // Shortcuts at the root node have special meaning of marking user global objects. if (edgeType === this.edgeShortcutType) { return false; } const flags = userObjectsMapAndFlag ? userObjectsMapAndFlag.map : null; const userObjectFlag = userObjectsMapAndFlag ? userObjectsMapAndFlag.flag : 0; const nodeOrdinal = nodeIndex / this.nodeFieldCount; const childNodeOrdinal = childNodeIndex / this.nodeFieldCount; const nodeFlag = !flags || (flags[nodeOrdinal] & userObjectFlag); const childNodeFlag = !flags || (flags[childNodeOrdinal] & userObjectFlag); // We are skipping the edges from non-page-owned nodes to page-owned nodes. // Otherwise the dominators for the objects that also were retained by debugger would be affected. if (childNodeFlag && !nodeFlag) { return false; } } return true; } // Returns a bitmap indicating whether each edge should be considered when building the dominator tree. private initEssentialEdges(): Platform.TypedArrayUtilities.BitVector { const essentialEdges = Platform.TypedArrayUtilities.createBitVector(this.#edgeCount); const {nodes, nodeFieldCount, edgeFieldsCount} = this; const userObjectsMapAndFlag = this.userObjectsMapAndFlag(); const endNodeIndex = nodes.length; const node = this.createNode(0); for (let nodeIndex = 0; nodeIndex < endNodeIndex; nodeIndex += nodeFieldCount) { node.nodeIndex = nodeIndex; const edgeIndexesEnd = node.edgeIndexesEnd(); for (let edgeIndex = node.edgeIndexesStart(); edgeIndex < edgeIndexesEnd; edgeIndex += edgeFieldsCount) { if (this.computeIsEssentialEdge(nodeIndex, edgeIndex, userObjectsMapAndFlag)) { essentialEdges.setBit(edgeIndex / edgeFieldsCount); } } } return essentialEdges; } static hasOnlyWeakRetainers(inputs: ArgumentsToComputeDominatorsAndRetainedSizes, nodeOrdinal: number): boolean { const {retainingEdges, edgeFieldsCount, firstRetainerIndex, essentialEdges} = inputs; const beginRetainerIndex = firstRetainerIndex[nodeOrdinal]; const endRetainerIndex = firstRetainerIndex[nodeOrdinal + 1]; for (let retainerIndex = beginRetainerIndex; retainerIndex < endRetainerIndex; ++retainerIndex) { const retainerEdgeIndex = retainingEdges[retainerIndex]; if (essentialEdges.getBit(retainerEdgeIndex / edgeFieldsCount)) { return false; } } return true; } // The algorithm for building the dominator tree is from the paper: // Thomas Lengauer and Robert Endre Tarjan. 1979. A fast algorithm for finding dominators in a flowgraph. // ACM Trans. Program. Lang. Syst. 1, 1 (July 1979), 121–141. https://doi.org/10.1145/357062.357071 static async calculateDominatorsAndRetainedSizes(inputs: ArgumentsToComputeDominatorsAndRetainedSizes): Promise { // Preload fields into local variables for better performance. const { nodeCount, firstEdgeIndexes, edgeFieldsCount, nodeFieldCount, firstRetainerIndex, retainingEdges, retainingNodes, edgeToNodeOrdinals, rootNodeOrdinal, essentialEdges, nodeSelfSizesPromise, port } = inputs; function isEssentialEdge(edgeIndex: number): boolean { return essentialEdges.getBit(edgeIndex / edgeFieldsCount); } // The Lengauer-Tarjan algorithm expects vectors to be numbered from 1 to n // and uses 0 as an invalid value, so use 1-indexing for all the arrays. // Convert between ordinals and vertex numbers by adding/subtracting 1. const arrayLength = nodeCount + 1; const parent = new Uint32Array(arrayLength); const ancestor = new Uint32Array(arrayLength); const vertex = new Uint32Array(arrayLength); const label = new Uint32Array(arrayLength); const semi = new Uint32Array(arrayLength); const bucket = new Array>(arrayLength); let n = 0; // Iterative DFS since the recursive version can cause stack overflows. // Use an array to keep track of the next edge index to be examined for each node. const nextEdgeIndex = new Uint32Array(arrayLength); const dfs = (root: number): void => { const rootOrdinal = root - 1; nextEdgeIndex[rootOrdinal] = firstEdgeIndexes[rootOrdinal]; let v = root; while (v !== 0) { // First process v if not done already. if (semi[v] === 0) { semi[v] = ++n; vertex[n] = label[v] = v; } // The next node to process is the first unprocessed successor w of v, // or parent[v] if all of v's successors have already been processed. let vNext = parent[v]; const vOrdinal = v - 1; for (; nextEdgeIndex[vOrdinal] < firstEdgeIndexes[vOrdinal + 1]; nextEdgeIndex[vOrdinal] += edgeFieldsCount) { const edgeIndex = nextEdgeIndex[vOrdinal]; if (!isEssentialEdge(edgeIndex)) { continue; } const wOrdinal = edgeToNodeOrdinals[edgeIndex / edgeFieldsCount]; const w = wOrdinal + 1; if (semi[w] === 0) { parent[w] = v; nextEdgeIndex[wOrdinal] = firstEdgeIndexes[wOrdinal]; vNext = w; break; } } v = vNext; } }; // Iterative version since the recursive version can cause stack overflows. // Preallocate a stack since compress() is called several times. // The stack cannot grow larger than the number of nodes since we walk up // the tree represented by the ancestor array. const compressionStack = new Uint32Array(arrayLength); const compress = (v: number): void => { let stackPointer = 0; while (ancestor[ancestor[v]] !== 0) { compressionStack[++stackPointer] = v; v = ancestor[v]; } while (stackPointer > 0) { const w = compressionStack[stackPointer--]; if (semi[label[ancestor[w]]] < semi[label[w]]) { label[w] = label[ancestor[w]]; } ancestor[w] = ancestor[ancestor[w]]; } }; // Simple versions of eval and link from the paper. const evaluate = (v: number): number => { if (ancestor[v] === 0) { return v; } compress(v); return label[v]; }; const link = (v: number, w: number): void => { ancestor[w] = v; }; // Algorithm begins here. The variable names are as per the paper. const r = rootNodeOrdinal + 1; n = 0; const dom = new Uint32Array(arrayLength); // First perform DFS from the root. dfs(r); // Then perform DFS from orphan nodes (ones with only weak retainers) if any. if (n < nodeCount) { const errors: HeapSnapshotProblemReport = [`Heap snapshot: ${nodeCount - n} nodes are unreachable from the root.`]; appendToProblemReport(errors, 'The following nodes have only weak retainers:'); for (let v = 1; v <= nodeCount; v++) { const vOrdinal = v - 1; if (semi[v] === 0 && HeapSnapshot.hasOnlyWeakRetainers(inputs, vOrdinal)) { appendToProblemReport(errors, vOrdinal * nodeFieldCount); parent[v] = r; dfs(v); } } reportProblemToPrimaryWorker(errors, port); } // If there are unreachable nodes still, visit them individually from the root. // This can happen when there is a clique of nodes retained by one another. if (n < nodeCount) { const errors: HeapSnapshotProblemReport = [`Heap snapshot: Still found ${nodeCount - n} unreachable nodes:`]; for (let v = 1; v <= nodeCount; v++) { if (semi[v] === 0) { const vOrdinal = v - 1; appendToProblemReport(errors, vOrdinal * nodeFieldCount); parent[v] = r; semi[v] = ++n; vertex[n] = label[v] = v; } } reportProblemToPrimaryWorker(errors, port); } // Main loop. Process the vertices in decreasing order by DFS number. for (let i = n; i >= 2; --i) { const w = vertex[i]; // Iterate over all predecessors v of w. const wOrdinal = w - 1; let isOrphanNode = true; for (let retainerIndex = firstRetainerIndex[wOrdinal]; retainerIndex < firstRetainerIndex[wOrdinal + 1]; retainerIndex++) { if (!isEssentialEdge(retainingEdges[retainerIndex])) { continue; } isOrphanNode = false; const vOrdinal = retainingNodes[retainerIndex] / nodeFieldCount; const v = vOrdinal + 1; const u = evaluate(v); if (semi[u] < semi[w]) { semi[w] = semi[u]; } } if (isOrphanNode) { // We treat orphan nodes as having a single predecessor - the root. // semi[r] is always less than any semi[w] so set it unconditionally. semi[w] = semi[r]; } if (bucket[vertex[semi[w]]] === undefined) { bucket[vertex[semi[w]]] = new Set(); } bucket[vertex[semi[w]]].add(w); link(parent[w], w); // Process all vertices v in bucket(parent(w)). if (bucket[parent[w]] !== undefined) { for (const v of bucket[parent[w]]) { const u = evaluate(v); dom[v] = semi[u] < semi[v] ? u : parent[w]; } bucket[parent[w]].clear(); } } // Final step. Fill in the immediate dominators not explicitly computed above. // Unlike the paper, we consider the root to be its own dominator and // set dom[0] to r to propagate the root as the dominator of unreachable nodes. dom[0] = dom[r] = r; for (let i = 2; i <= n; i++) { const w = vertex[i]; if (dom[w] !== vertex[semi[w]]) { dom[w] = dom[dom[w]]; } } // Algorithm ends here. // Transform the dominators into an ordinal-indexed array and populate the self sizes. const dominatorsTree = new Uint32Array(nodeCount); const retainedSizes = new Float64Array(nodeCount); const nodeSelfSizes = await nodeSelfSizesPromise; for (let nodeOrdinal = 0; nodeOrdinal < nodeCount; nodeOrdinal++) { dominatorsTree[nodeOrdinal] = dom[nodeOrdinal + 1] - 1; retainedSizes[nodeOrdinal] = nodeSelfSizes[nodeOrdinal]; } // Then propagate up the retained sizes for each traversed node excluding the root. for (let i = n; i > 1; i--) { const nodeOrdinal = vertex[i] - 1; const dominatorOrdinal = dominatorsTree[nodeOrdinal]; retainedSizes[dominatorOrdinal] += retainedSizes[nodeOrdinal]; } return {dominatorsTree, retainedSizes}; } static buildDominatedNodes(inputs: ArgumentsToBuildDominatedNodes): DominatedNodes { const {nodeCount, dominatorsTree, rootNodeOrdinal, nodeFieldCount} = inputs; // Builds up two arrays: // - "dominatedNodes" is a continuous array, where each node owns an // interval (can be empty) with corresponding dominated nodes. // - "indexArray" is an array of indexes in the "dominatedNodes" // with the same positions as in the _nodeIndex. const indexArray = new Uint32Array(nodeCount + 1); // All nodes except the root have dominators. const dominatedNodes = new Uint32Array(nodeCount - 1); // Count the number of dominated nodes for each node. Skip the root (node at // index 0) as it is the only node that dominates itself. let fromNodeOrdinal = 0; let toNodeOrdinal: number = nodeCount; if (rootNodeOrdinal === fromNodeOrdinal) { fromNodeOrdinal = 1; } else if (rootNodeOrdinal === toNodeOrdinal - 1) { toNodeOrdinal = toNodeOrdinal - 1; } else { throw new Error('Root node is expected to be either first or last'); } for (let nodeOrdinal = fromNodeOrdinal; nodeOrdinal < toNodeOrdinal; ++nodeOrdinal) { ++indexArray[dominatorsTree[nodeOrdinal]]; } // Put in the first slot of each dominatedNodes slice the count of entries // that will be filled. let firstDominatedNodeIndex = 0; for (let i = 0, l = nodeCount; i < l; ++i) { const dominatedCount = dominatedNodes[firstDominatedNodeIndex] = indexArray[i]; indexArray[i] = firstDominatedNodeIndex; firstDominatedNodeIndex += dominatedCount; } indexArray[nodeCount] = dominatedNodes.length; // Fill up the dominatedNodes array with indexes of dominated nodes. Skip the root (node at // index 0) as it is the only node that dominates itself. for (let nodeOrdinal = fromNodeOrdinal; nodeOrdinal < toNodeOrdinal; ++nodeOrdinal) { const dominatorOrdinal = dominatorsTree[nodeOrdinal]; let dominatedRefIndex = indexArray[dominatorOrdinal]; dominatedRefIndex += (--dominatedNodes[dominatedRefIndex]); dominatedNodes[dominatedRefIndex] = nodeOrdinal * nodeFieldCount; } return {firstDominatedNodeIndex: indexArray, dominatedNodes}; } private calculateObjectNames(): void { const { nodes, nodeCount, nodeNameOffset, nodeNativeType, nodeHiddenType, nodeObjectType, nodeCodeType, nodeClosureType, nodeRegExpType, } = this; // If the snapshot doesn't contain a detachedness field in each node, then // allocate a separate array so there is somewhere to store the class index. if (this.nodeDetachednessAndClassIndexOffset === -1) { this.detachednessAndClassIndexArray = new Uint32Array(nodeCount); } // We'll add some new values to the `strings` array during the processing below. // This map lets us easily find the index for each added string. const stringTable = new Map(); const getIndexForString = (s: string): number => { let index = stringTable.get(s); if (index === undefined) { index = this.addString(s); stringTable.set(s, index); } return index; }; const hiddenClassIndex = getIndexForString('(system)'); const codeClassIndex = getIndexForString('(compiled code)'); const functionClassIndex = getIndexForString('Function'); const regExpClassIndex = getIndexForString('RegExp'); function getNodeClassIndex(node: HeapSnapshotNode): number { switch (node.rawType()) { case nodeHiddenType: return hiddenClassIndex; case nodeObjectType: case nodeNativeType: { let name = node.rawName(); // If the node name is (for example) '

', then the class // name should be just '

'. If the node name is already short // enough, like '

', we must still call getIndexForString on that // name, because the names added by getIndexForString are not // deduplicated with preexisting strings, and we want all objects with // class name '

' to refer to that class name via the same index. // Otherwise, object categorization doesn't work. if (name.startsWith('<')) { const firstSpace = name.indexOf(' '); if (firstSpace !== -1) { name = name.substring(0, firstSpace) + '>'; } return getIndexForString(name); } if (name.startsWith('Detached <')) { const firstSpace = name.indexOf(' ', 10); if (firstSpace !== -1) { name = name.substring(0, firstSpace) + '>'; } return getIndexForString(name); } // Avoid getIndexForString here; the class name index should match the name index. return nodes.getValue(node.nodeIndex + nodeNameOffset); } case nodeCodeType: return codeClassIndex; case nodeClosureType: return functionClassIndex; case nodeRegExpType: return regExpClassIndex; default: return getIndexForString('(' + node.type() + ')'); } } const node = this.createNode(0); for (let i = 0; i < nodeCount; ++i) { node.setClassIndex(getNodeClassIndex(node)); node.nodeIndex = node.nextNodeIndex(); } } interfaceDefinitions(): string { return JSON.stringify(this.#interfaceDefinitions ?? []); } private isPlainJSObject(node: HeapSnapshotNode): boolean { return node.rawType() === this.nodeObjectType && node.rawName() === 'Object'; } private inferInterfaceDefinitions(): InterfaceDefinition[] { const {edgePropertyType} = this; /** * First, produce a set of candidate definitions by iterating the properties * on every plain JS Object in the snapshot. **/ interface InterfaceDefinitionCandidate extends InterfaceDefinition { // How many objects start with these properties in this order. count: number; } // A map from interface names to their definitions. const candidates = new Map(); let totalObjectCount = 0; for (let it = this.allNodes(); it.hasNext(); it.next()) { const node = it.item(); if (!this.isPlainJSObject(node)) { continue; } ++totalObjectCount; let interfaceName = '{'; const properties: string[] = []; for (let edgeIt = node.edges(); edgeIt.hasNext(); edgeIt.next()) { const edge = edgeIt.item(); const edgeName = edge.name(); if (edge.rawType() !== edgePropertyType || edgeName === '__proto__') { continue; } const formattedEdgeName = JSHeapSnapshotNode.formatPropertyName(edgeName); if (interfaceName.length > MIN_INTERFACE_PROPERTY_COUNT && interfaceName.length + formattedEdgeName.length > MAX_INTERFACE_NAME_LENGTH) { break; // The interface name is getting too long. } if (interfaceName.length !== 1) { interfaceName += ', '; } interfaceName += formattedEdgeName; properties.push(edgeName); } // The empty interface is not very meaningful, and can be sort of misleading // since someone might incorrectly interpret it as objects with no properties. if (properties.length === 0) { continue; } interfaceName += '}'; const candidate = candidates.get(interfaceName); if (candidate) { ++candidate.count; } else { candidates.set(interfaceName, {name: interfaceName, properties, count: 1}); } } // Next, sort the candidates and select the most popular ones. It's possible that // some candidates represent the same properties in different orders, but that's // okay: by sorting here, we ensure that the most popular ordering appears first // in the result list, and the rules for applying interface definitions will prefer // the first matching definition if multiple matches contain the same properties. const sortedCandidates = Array.from(candidates.values()); sortedCandidates.sort((a, b) => b.count - a.count); const result: InterfaceDefinition[] = []; const minCount = Math.max(MIN_OBJECT_COUNT_PER_INTERFACE, totalObjectCount / MIN_OBJECT_PROPORTION_PER_INTERFACE); for (let i = 0; i < sortedCandidates.length; ++i) { const candidate = sortedCandidates[i]; if (candidate.count < minCount) { break; } result.push(candidate); } return result; } private applyInterfaceDefinitions(definitions: InterfaceDefinition[]): void { const {edgePropertyType} = this; this.#interfaceDefinitions = definitions; // Any computed aggregate data will be wrong after recategorization, so clear it. this.#aggregates = {}; this.#aggregatesSortedFlags = {}; /** Information about a named interface. **/ interface MatchInfo { name: string; // The number of properties listed in the interface definition. propertyCount: number; // The position of the interface definition in the list of definitions. index: number; } function selectBetterMatch(a: MatchInfo, b: MatchInfo|null): MatchInfo { if (!b || a.propertyCount > b.propertyCount) { return a; } if (b.propertyCount > a.propertyCount) { return b; } return a.index <= b.index ? a : b; } /** * A node in the tree which allows us to search for interfaces matching an object. * Each edge in this tree represents adding a property, starting from an empty * object. Properties must be iterated in sorted order. **/ interface PropertyTreeNode { // All possible successors from this node. Keys are property names. next: Map; // If this node corresponds to a named interface, then matchInfo contains that name. matchInfo: MatchInfo|null; // The maximum of all keys in `next`. This helps determine when no further transitions // are possible from this node. greatestNext: string|null; } // The root node of the tree. const propertyTree: PropertyTreeNode = { next: new Map(), matchInfo: null, greatestNext: null, }; // Build up the property tree. for (let interfaceIndex = 0; interfaceIndex < definitions.length; ++interfaceIndex) { const definition = definitions[interfaceIndex]; const properties = definition.properties.toSorted(); let currentNode = propertyTree; for (const property of properties) { const nextMap = currentNode.next; let nextNode = nextMap.get(property); if (!nextNode) { nextNode = { next: new Map(), matchInfo: null, greatestNext: null, }; nextMap.set(property, nextNode); if (currentNode.greatestNext === null || currentNode.greatestNext < property) { currentNode.greatestNext = property; } } currentNode = nextNode; } // Only set matchInfo on this node if it wasn't already set, to ensure that // interfaces defined earlier in the list have priority. if (!currentNode.matchInfo) { currentNode.matchInfo = { name: definition.name, propertyCount: properties.length, index: interfaceIndex, }; } } // The fallback match for objects which don't match any defined interface. const initialMatch: MatchInfo = { name: 'Object', propertyCount: 0, index: Infinity, }; // Iterate all nodes and check whether they match a named interface, using // the tree constructed above. Then update the class name for each node. for (let it = this.allNodes(); it.hasNext(); it.next()) { const node = it.item(); if (!this.isPlainJSObject(node)) { continue; } // Collect and sort the properties of this object. const properties: string[] = []; for (let edgeIt = node.edges(); edgeIt.hasNext(); edgeIt.next()) { const edge = edgeIt.item(); if (edge.rawType() === edgePropertyType) { properties.push(edge.name()); } } properties.sort(); // We may explore multiple possible paths through the tree, so this set tracks // all states that match with the properties iterated thus far. const states = new Set(); states.add(propertyTree); // This variable represents the best match found thus far. We start by checking // whether there is an interface definition for the empty object. let match = selectBetterMatch(initialMatch, propertyTree.matchInfo); // Traverse the tree to find any matches. for (const property of properties) { // Iterate only the states that already exist, not the ones added during the loop below. for (const currentState of Array.from(states.keys())) { if (currentState.greatestNext === null || property >= currentState.greatestNext) { // No further transitions are possible from this state. states.delete(currentState); } const nextState = currentState.next.get(property); if (nextState) { states.add(nextState); match = selectBetterMatch(match, nextState.matchInfo); } } } // Update the node's class name accordingly. let classIndex = match === initialMatch ? node.rawNameIndex() : this.#interfaceNames.get(match.name); if (classIndex === undefined) { classIndex = this.addString(match.name); this.#interfaceNames.set(match.name, classIndex); } node.setClassIndex(classIndex); } } /** * Iterates children of a node. */ private iterateFilteredChildren( nodeOrdinal: number, edgeFilterCallback: (arg0: number) => boolean, childCallback: (arg0: number) => void): void { const beginEdgeIndex = this.firstEdgeIndexes[nodeOrdinal]; const endEdgeIndex = this.firstEdgeIndexes[nodeOrdinal + 1]; for (let edgeIndex = beginEdgeIndex; edgeIndex < endEdgeIndex; edgeIndex += this.edgeFieldsCount) { const childNodeIndex = this.containmentEdges.getValue(edgeIndex + this.edgeToNodeOffset); const childNodeOrdinal = childNodeIndex / this.nodeFieldCount; const type = this.containmentEdges.getValue(edgeIndex + this.edgeTypeOffset); if (!edgeFilterCallback(type)) { continue; } childCallback(childNodeOrdinal); } } /** * Adds a string to the snapshot. */ private addString(string: string): number { this.strings.push(string); return this.strings.length - 1; } /** * Gets the target node of an edge with the specified name. * @param node The source node to search from * @param edgeName The name of the edge to find * @returns The target node if found, null otherwise */ private getEdgeTarget(node: HeapSnapshotNode, edgeName: string): HeapSnapshotNode|null { for (let edgeIt = node.edges(); edgeIt.hasNext(); edgeIt.next()) { const edge = edgeIt.item(); if (edge.name() === edgeName) { return edge.node(); } } return null; } /** * The phase propagates whether a node is attached or detached through the * graph and adjusts the low-level representation of nodes. * * State propagation: * 1. Any object reachable from an attached object is itself attached. * 2. Any object reachable from a detached object that is not already * attached is considered detached. * * Representation: * - Name of any detached node is changed from """ to * "Detached ". */ private propagateDOMState(): void { if (this.nodeDetachednessAndClassIndexOffset === -1) { return; } console.time('propagateDOMState'); const visited = new Uint8Array(this.nodeCount); const attached: number[] = []; const detached: number[] = []; const stringIndexCache = new Map(); const node = this.createNode(0); /** * Adds a 'Detached ' prefix to the name of a node. */ const addDetachedPrefixToNodeName = function(snapshot: HeapSnapshot, nodeIndex: number): void { const oldStringIndex = snapshot.nodes.getValue(nodeIndex + snapshot.nodeNameOffset); let newStringIndex = stringIndexCache.get(oldStringIndex); if (newStringIndex === undefined) { newStringIndex = snapshot.addString('Detached ' + snapshot.strings[oldStringIndex]); stringIndexCache.set(oldStringIndex, newStringIndex); } snapshot.nodes.setValue(nodeIndex + snapshot.nodeNameOffset, newStringIndex); }; /** * Processes a node represented by nodeOrdinal: * - Changes its name based on newState. * - Puts it onto working sets for attached or detached nodes. */ const processNode = function(snapshot: HeapSnapshot, nodeOrdinal: number, newState: number): void { if (visited[nodeOrdinal]) { return; } const nodeIndex = nodeOrdinal * snapshot.nodeFieldCount; // Early bailout: Do not propagate the state (and name change) through JavaScript. Every // entry point into embedder code is a node that knows its own state. All embedder nodes // have their node type set to native. if (snapshot.nodes.getValue(nodeIndex + snapshot.nodeTypeOffset) !== snapshot.nodeNativeType) { visited[nodeOrdinal] = 1; return; } node.nodeIndex = nodeIndex; node.setDetachedness(newState); if (newState === DOMLinkState.ATTACHED) { attached.push(nodeOrdinal); } else if (newState === DOMLinkState.DETACHED) { // Detached state: Rewire node name. addDetachedPrefixToNodeName(snapshot, nodeIndex); detached.push(nodeOrdinal); } visited[nodeOrdinal] = 1; }; const propagateState = function(snapshot: HeapSnapshot, parentNodeOrdinal: number, newState: number): void { snapshot.iterateFilteredChildren( parentNodeOrdinal, edgeType => ![snapshot.edgeHiddenType, snapshot.edgeInvisibleType, snapshot.edgeWeakType].includes(edgeType), nodeOrdinal => processNode(snapshot, nodeOrdinal, newState)); }; // 1. We re-use the deserialized field to store the propagated state. While // the state for known nodes is already set, they still need to go // through processing to have their name adjusted and them enqueued in // the respective queues. for (let nodeOrdinal = 0; nodeOrdinal < this.nodeCount; ++nodeOrdinal) { node.nodeIndex = nodeOrdinal * this.nodeFieldCount; const state = node.detachedness(); // Bail out for objects that have no known state. For all other objects set that state. if (state === DOMLinkState.UNKNOWN) { continue; } processNode(this, nodeOrdinal, state); } // 2. If the parent is attached, then the child is also attached. while (attached.length !== 0) { const nodeOrdinal = (attached.pop() as number); propagateState(this, nodeOrdinal, DOMLinkState.ATTACHED); } // 3. If the parent is not attached, then the child inherits the parent's state. while (detached.length !== 0) { const nodeOrdinal = (detached.pop() as number); node.nodeIndex = nodeOrdinal * this.nodeFieldCount; const nodeState = node.detachedness(); // Ignore if the node has been found through propagating forward attached state. if (nodeState === DOMLinkState.ATTACHED) { continue; } propagateState(this, nodeOrdinal, DOMLinkState.DETACHED); } console.timeEnd('propagateDOMState'); } private buildSamples(): void { const samples = this.#rawSamples; if (!samples?.length) { return; } const sampleCount = samples.length / 2; const sizeForRange = new Array(sampleCount); const timestamps = new Array(sampleCount); const lastAssignedIds = new Array(sampleCount); const timestampOffset = this.#metaNode.sample_fields.indexOf('timestamp_us'); const lastAssignedIdOffset = this.#metaNode.sample_fields.indexOf('last_assigned_id'); for (let i = 0; i < sampleCount; i++) { sizeForRange[i] = 0; timestamps[i] = (samples[2 * i + timestampOffset]) / 1000; lastAssignedIds[i] = samples[2 * i + lastAssignedIdOffset]; } const nodes = this.nodes; const nodesLength = nodes.length; const nodeFieldCount = this.nodeFieldCount; const node = this.rootNode(); for (let nodeIndex = 0; nodeIndex < nodesLength; nodeIndex += nodeFieldCount) { node.nodeIndex = nodeIndex; const nodeId = node.id(); // JS objects have odd ids, skip native objects. if (nodeId % 2 === 0) { continue; } const rangeIndex = Platform.ArrayUtilities.lowerBound(lastAssignedIds, nodeId, Platform.ArrayUtilities.DEFAULT_COMPARATOR); if (rangeIndex === sampleCount) { // TODO: make heap profiler not allocate while taking snapshot continue; } sizeForRange[rangeIndex] += node.selfSize(); } this.#samples = new HeapSnapshotModel.HeapSnapshotModel.Samples(timestamps, lastAssignedIds, sizeForRange); } private buildLocationMap(): void { const map = new Map(); const locations = this.#locations; for (let i = 0; i < locations.length; i += this.#locationFieldCount) { const nodeIndex = locations[i + this.#locationIndexOffset]; const scriptId = locations[i + this.#locationScriptIdOffset]; const line = locations[i + this.#locationLineOffset]; const col = locations[i + this.#locationColumnOffset]; map.set(nodeIndex, new HeapSnapshotModel.HeapSnapshotModel.Location(scriptId, line, col)); } this.#locationMap = map; } getLocation(nodeIndex: number): HeapSnapshotModel.HeapSnapshotModel.Location|null { return this.#locationMap.get(nodeIndex) || null; } getSamples(): HeapSnapshotModel.HeapSnapshotModel.Samples|null { return this.#samples; } calculateFlags(): void { throw new Error('Not implemented'); } calculateStatistics(): void { throw new Error('Not implemented'); } userObjectsMapAndFlag(): {map: Uint8Array, flag: number}|null { throw new Error('Not implemented'); } calculateSnapshotDiff( baseSnapshotId: string, baseSnapshotAggregates: Record): Record { let snapshotDiff: Record = this.#snapshotDiffs[baseSnapshotId]; if (snapshotDiff) { return snapshotDiff; } snapshotDiff = {}; const aggregates = this.getAggregatesByClassKey(true, 'allObjects'); for (const classKey in baseSnapshotAggregates) { const baseAggregate = baseSnapshotAggregates[classKey]; const diff = this.calculateDiffForClass(baseAggregate, aggregates[classKey]); if (diff) { snapshotDiff[classKey] = diff; } } const emptyBaseAggregate = new HeapSnapshotModel.HeapSnapshotModel.AggregateForDiff(); for (const classKey in aggregates) { if (classKey in baseSnapshotAggregates) { continue; } const classDiff = this.calculateDiffForClass(emptyBaseAggregate, aggregates[classKey]); if (classDiff) { snapshotDiff[classKey] = classDiff; } } this.#snapshotDiffs[baseSnapshotId] = snapshotDiff; return snapshotDiff; } private calculateDiffForClass( baseAggregate: HeapSnapshotModel.HeapSnapshotModel.AggregateForDiff, aggregate?: HeapSnapshotModel.HeapSnapshotModel.AggregatedInfo): HeapSnapshotModel.HeapSnapshotModel.Diff|null { const baseIds = baseAggregate.ids; const baseIndexes = baseAggregate.indexes; const baseSelfSizes = baseAggregate.selfSizes; const indexes = aggregate ? aggregate.idxs : []; let i = 0; let j = 0; const l = baseIds.length; const m = indexes.length; const diff = new HeapSnapshotModel.HeapSnapshotModel.Diff(aggregate ? aggregate.name : baseAggregate.name); const nodeB = this.createNode(indexes[j]); while (i < l && j < m) { const nodeAId = baseIds[i]; if (nodeAId < nodeB.id()) { diff.deletedIndexes.push(baseIndexes[i]); diff.removedCount++; diff.removedSize += baseSelfSizes[i]; ++i; } else if ( nodeAId > nodeB.id()) { // Native nodes(e.g. dom groups) may have ids less than max JS object id in the base snapshot diff.addedIndexes.push(indexes[j]); diff.addedCount++; diff.addedSize += nodeB.selfSize(); nodeB.nodeIndex = indexes[++j]; } else { // nodeAId === nodeB.id() ++i; nodeB.nodeIndex = indexes[++j]; } } while (i < l) { diff.deletedIndexes.push(baseIndexes[i]); diff.removedCount++; diff.removedSize += baseSelfSizes[i]; ++i; } while (j < m) { diff.addedIndexes.push(indexes[j]); diff.addedCount++; diff.addedSize += nodeB.selfSize(); nodeB.nodeIndex = indexes[++j]; } diff.countDelta = diff.addedCount - diff.removedCount; diff.sizeDelta = diff.addedSize - diff.removedSize; if (!diff.addedCount && !diff.removedCount) { return null; } return diff; } private nodeForSnapshotObjectId(snapshotObjectId: number): HeapSnapshotNode|null { for (let it = this.allNodes(); it.hasNext(); it.next()) { if (it.node.id() === snapshotObjectId) { return it.node; } } return null; } // Converts an internal class key, suitable for categorizing within this // snapshot, to a public class key, which can be used in comparisons // between multiple snapshots. #classKeyFromClassKey(key: string|number): string { return typeof key === 'number' ? (',' + this.strings[key]) : key; } nodeClassKey(snapshotObjectId: number): string|null { const node = this.nodeForSnapshotObjectId(snapshotObjectId); if (node) { return this.#classKeyFromClassKey(node.classKeyInternal()); } return null; } createEdgesProvider(nodeIndex: number): HeapSnapshotEdgesProvider { const node = this.createNode(nodeIndex); const filter = this.containmentEdgesFilter(); const indexProvider = new HeapSnapshotEdgeIndexProvider(this); return new HeapSnapshotEdgesProvider(this, filter, node.edges(), indexProvider); } createEdgesProviderForTest(nodeIndex: number, filter: ((arg0: HeapSnapshotEdge) => boolean)|null): HeapSnapshotEdgesProvider { const node = this.createNode(nodeIndex); const indexProvider = new HeapSnapshotEdgeIndexProvider(this); return new HeapSnapshotEdgesProvider(this, filter, node.edges(), indexProvider); } retainingEdgesFilter(): ((arg0: HeapSnapshotEdge) => boolean)|null { return null; } containmentEdgesFilter(): ((arg0: HeapSnapshotEdge) => boolean)|null { return null; } createRetainingEdgesProvider(nodeIndex: number): HeapSnapshotEdgesProvider { const node = this.createNode(nodeIndex); const filter = this.retainingEdgesFilter(); const indexProvider = new HeapSnapshotRetainerEdgeIndexProvider(this); return new HeapSnapshotEdgesProvider(this, filter, node.retainers(), indexProvider); } createAddedNodesProvider(baseSnapshotId: string, classKey: string): HeapSnapshotNodesProvider { const snapshotDiff = this.#snapshotDiffs[baseSnapshotId]; const diffForClass = snapshotDiff[classKey]; return new HeapSnapshotNodesProvider(this, diffForClass.addedIndexes); } createDeletedNodesProvider(nodeIndexes: number[]): HeapSnapshotNodesProvider { return new HeapSnapshotNodesProvider(this, nodeIndexes); } createNodesProviderForClass(classKey: string, nodeFilter: HeapSnapshotModel.HeapSnapshotModel.NodeFilter): HeapSnapshotNodesProvider { return new HeapSnapshotNodesProvider(this, this.aggregatesWithFilter(nodeFilter)[classKey].idxs); } private maxJsNodeId(): number { const nodeFieldCount = this.nodeFieldCount; const nodes = this.nodes; const nodesLength = nodes.length; let id = 0; for (let nodeIndex = this.nodeIdOffset; nodeIndex < nodesLength; nodeIndex += nodeFieldCount) { const nextId = nodes.getValue(nodeIndex); // JS objects have odd ids, skip native objects. if (nextId % 2 === 0) { continue; } if (id < nextId) { id = nextId; } } return id; } updateStaticData(): HeapSnapshotModel.HeapSnapshotModel.StaticData { return new HeapSnapshotModel.HeapSnapshotModel.StaticData( this.nodeCount, this.rootNodeIndexInternal, this.totalSize, this.maxJsNodeId()); } ignoreNodeInRetainersView(nodeIndex: number): void { this.#ignoredNodesInRetainersView.add(nodeIndex); this.calculateDistances(/* isForRetainersView=*/ true); this.#updateIgnoredEdgesInRetainersView(); } unignoreNodeInRetainersView(nodeIndex: number): void { this.#ignoredNodesInRetainersView.delete(nodeIndex); if (this.#ignoredNodesInRetainersView.size === 0) { this.#nodeDistancesForRetainersView = undefined; } else { this.calculateDistances(/* isForRetainersView=*/ true); } this.#updateIgnoredEdgesInRetainersView(); } unignoreAllNodesInRetainersView(): void { this.#ignoredNodesInRetainersView.clear(); this.#nodeDistancesForRetainersView = undefined; this.#updateIgnoredEdgesInRetainersView(); } #updateIgnoredEdgesInRetainersView(): void { const distances = this.#nodeDistancesForRetainersView; this.#ignoredEdgesInRetainersView.clear(); if (distances === undefined) { return; } // To retain a value in a WeakMap, both the WeakMap and the corresponding // key must stay alive. If one of those two retainers is unreachable due to // the user ignoring some nodes, then the other retainer edge should also be // shown as unreachable, since it would be insufficient on its own to retain // the value. const unreachableWeakMapEdges = new Platform.MapUtilities.Multimap(); const noDistance = this.#noDistance; const {nodeCount, nodeFieldCount} = this; const node = this.createNode(0); // Populate unreachableWeakMapEdges. for (let nodeOrdinal = 0; nodeOrdinal < nodeCount; ++nodeOrdinal) { if (distances[nodeOrdinal] !== noDistance) { continue; } node.nodeIndex = nodeOrdinal * nodeFieldCount; for (let iter = node.edges(); iter.hasNext(); iter.next()) { const edge = iter.edge; if (!edge.isInternal()) { continue; } const match = this.tryParseWeakMapEdgeName(edge.nameIndex()); if (match) { unreachableWeakMapEdges.set(edge.nodeIndex(), match.duplicatedPart); } } } // Iterate the retaining edges for the target nodes found in the previous // step and mark any relevant WeakMap edges as ignored. for (const targetNodeIndex of unreachableWeakMapEdges.keys()) { node.nodeIndex = targetNodeIndex; for (let it = node.retainers(); it.hasNext(); it.next()) { const reverseEdge = it.item(); if (!reverseEdge.isInternal()) { continue; } const match = this.tryParseWeakMapEdgeName(reverseEdge.nameIndex()); if (match && unreachableWeakMapEdges.hasValue(targetNodeIndex, match.duplicatedPart)) { const forwardEdgeIndex = this.retainingEdges[reverseEdge.itemIndex()]; this.#ignoredEdgesInRetainersView.add(forwardEdgeIndex); } } } } areNodesIgnoredInRetainersView(): boolean { return this.#ignoredNodesInRetainersView.size > 0; } getDistanceForRetainersView(nodeIndex: number): number { const nodeOrdinal = nodeIndex / this.nodeFieldCount; const distances = this.#nodeDistancesForRetainersView ?? this.nodeDistances; const distance = distances[nodeOrdinal]; if (distance === this.#noDistance) { // An unreachable node should be sorted to the end, not the beginning. // To give such nodes a reasonable sorting order, we add a very large // number to the original distance computed without ignoring any nodes. return Math.max(0, this.nodeDistances[nodeOrdinal]) + HeapSnapshotModel.HeapSnapshotModel.baseUnreachableDistance; } return distance; } isNodeIgnoredInRetainersView(nodeIndex: number): boolean { return this.#ignoredNodesInRetainersView.has(nodeIndex); } isEdgeIgnoredInRetainersView(edgeIndex: number): boolean { return this.#ignoredEdgesInRetainersView.has(edgeIndex); } } interface HeapSnapshotMetaInfo { /* eslint-disable @typescript-eslint/naming-convention */ location_fields: string[]; node_fields: string[]; node_types: string[][]; edge_fields: string[]; edge_types: string[][]; trace_function_info_fields: string[]; trace_node_fields: string[]; sample_fields: string[]; type_strings: Record; /* eslint-enable @typescript-eslint/naming-convention */ } export interface HeapSnapshotHeader { /* eslint-disable @typescript-eslint/naming-convention */ title: string; meta: HeapSnapshotMetaInfo; node_count: number; edge_count: number; trace_function_count: number; root_index: number; extra_native_bytes?: number; /* eslint-enable @typescript-eslint/naming-convention */ } export abstract class HeapSnapshotItemProvider { protected readonly iterator: HeapSnapshotItemIterator; readonly #indexProvider: HeapSnapshotItemIndexProvider; readonly #isEmpty: boolean; protected iterationOrder: number[]|null; protected currentComparator: HeapSnapshotModel.HeapSnapshotModel.ComparatorConfig|null; #sortedPrefixLength: number; #sortedSuffixLength: number; constructor(iterator: HeapSnapshotItemIterator, indexProvider: HeapSnapshotItemIndexProvider) { this.iterator = iterator; this.#indexProvider = indexProvider; this.#isEmpty = !iterator.hasNext(); this.iterationOrder = null; this.currentComparator = null; this.#sortedPrefixLength = 0; this.#sortedSuffixLength = 0; } protected createIterationOrder(): void { if (this.iterationOrder) { return; } this.iterationOrder = []; for (let iterator = this.iterator; iterator.hasNext(); iterator.next()) { this.iterationOrder.push(iterator.item().itemIndex()); } } isEmpty(): boolean { return this.#isEmpty; } serializeItemsRange(begin: number, end: number): HeapSnapshotModel.HeapSnapshotModel.ItemsRange { this.createIterationOrder(); if (begin > end) { throw new Error('Start position > end position: ' + begin + ' > ' + end); } if (!this.iterationOrder) { throw new Error('Iteration order undefined'); } if (end > this.iterationOrder.length) { end = this.iterationOrder.length; } if (this.#sortedPrefixLength < end && begin < this.iterationOrder.length - this.#sortedSuffixLength && this.currentComparator) { const currentComparator = this.currentComparator; this.sort( currentComparator, this.#sortedPrefixLength, this.iterationOrder.length - 1 - this.#sortedSuffixLength, begin, end - 1); if (begin <= this.#sortedPrefixLength) { this.#sortedPrefixLength = end; } if (end >= this.iterationOrder.length - this.#sortedSuffixLength) { this.#sortedSuffixLength = this.iterationOrder.length - begin; } } let position = begin; const count = end - begin; const result = new Array(count); for (let i = 0; i < count; ++i) { const itemIndex = this.iterationOrder[position++]; const item = this.#indexProvider.itemForIndex(itemIndex); result[i] = item.serialize(); } return new HeapSnapshotModel.HeapSnapshotModel.ItemsRange(begin, end, this.iterationOrder.length, result); } sortAndRewind(comparator: HeapSnapshotModel.HeapSnapshotModel.ComparatorConfig): void { this.currentComparator = comparator; this.#sortedPrefixLength = 0; this.#sortedSuffixLength = 0; } abstract sort( comparator: HeapSnapshotModel.HeapSnapshotModel.ComparatorConfig, leftBound: number, rightBound: number, windowLeft: number, windowRight: number): void; } export class HeapSnapshotEdgesProvider extends HeapSnapshotItemProvider { snapshot: HeapSnapshot; constructor( snapshot: HeapSnapshot, filter: ((arg0: HeapSnapshotEdge) => boolean)|null, edgesIter: HeapSnapshotEdgeIterator|HeapSnapshotRetainerEdgeIterator, indexProvider: HeapSnapshotItemIndexProvider) { const iter = filter ? new HeapSnapshotFilteredIterator(edgesIter, (filter as (arg0: HeapSnapshotItem) => boolean)) : edgesIter; super(iter, indexProvider); this.snapshot = snapshot; } sort( comparator: HeapSnapshotModel.HeapSnapshotModel.ComparatorConfig, leftBound: number, rightBound: number, windowLeft: number, windowRight: number): void { const fieldName1 = comparator.fieldName1; const fieldName2 = comparator.fieldName2; const ascending1 = comparator.ascending1; const ascending2 = comparator.ascending2; const edgeA = (this.iterator.item() as HeapSnapshotEdge | HeapSnapshotRetainerEdge).clone(); const edgeB = edgeA.clone(); const nodeA = this.snapshot.createNode(); const nodeB = this.snapshot.createNode(); function compareEdgeField(fieldName: string, ascending: boolean, indexA: number, indexB: number): number { edgeA.edgeIndex = indexA; edgeB.edgeIndex = indexB; let result = 0; if (fieldName === '!edgeName') { if (edgeB.name() === '__proto__') { return -1; } if (edgeA.name() === '__proto__') { return 1; } result = edgeA.hasStringName() === edgeB.hasStringName() ? (edgeA.name() < edgeB.name() ? -1 : (edgeA.name() > edgeB.name() ? 1 : 0)) : (edgeA.hasStringName() ? -1 : 1); } else { result = edgeA.getValueForSorting(fieldName) - edgeB.getValueForSorting(fieldName); } return ascending ? result : -result; } function compareNodeField(fieldName: string, ascending: boolean, indexA: number, indexB: number): number { edgeA.edgeIndex = indexA; nodeA.nodeIndex = edgeA.nodeIndex(); // TODO(crbug.com/1172300) Ignored during the jsdoc to ts migration) // eslint-disable-next-line @typescript-eslint/no-explicit-any const valueA = (nodeA as any)[fieldName](); edgeB.edgeIndex = indexB; nodeB.nodeIndex = edgeB.nodeIndex(); // TODO(crbug.com/1172300) Ignored during the jsdoc to ts migration) // eslint-disable-next-line @typescript-eslint/no-explicit-any const valueB = (nodeB as any)[fieldName](); const result = valueA < valueB ? -1 : (valueA > valueB ? 1 : 0); return ascending ? result : -result; } function compareEdgeAndEdge(indexA: number, indexB: number): number { let result = compareEdgeField(fieldName1, ascending1, indexA, indexB); if (result === 0) { result = compareEdgeField(fieldName2, ascending2, indexA, indexB); } if (result === 0) { return indexA - indexB; } return result; } function compareEdgeAndNode(indexA: number, indexB: number): number { let result = compareEdgeField(fieldName1, ascending1, indexA, indexB); if (result === 0) { result = compareNodeField(fieldName2, ascending2, indexA, indexB); } if (result === 0) { return indexA - indexB; } return result; } function compareNodeAndEdge(indexA: number, indexB: number): number { let result = compareNodeField(fieldName1, ascending1, indexA, indexB); if (result === 0) { result = compareEdgeField(fieldName2, ascending2, indexA, indexB); } if (result === 0) { return indexA - indexB; } return result; } function compareNodeAndNode(indexA: number, indexB: number): number { let result = compareNodeField(fieldName1, ascending1, indexA, indexB); if (result === 0) { result = compareNodeField(fieldName2, ascending2, indexA, indexB); } if (result === 0) { return indexA - indexB; } return result; } if (!this.iterationOrder) { throw new Error('Iteration order not defined'); } function isEdgeFieldName(fieldName: string): boolean { return fieldName.startsWith('!edge'); } if (isEdgeFieldName(fieldName1)) { if (isEdgeFieldName(fieldName2)) { Platform.ArrayUtilities.sortRange( this.iterationOrder, compareEdgeAndEdge, leftBound, rightBound, windowLeft, windowRight); } else { Platform.ArrayUtilities.sortRange( this.iterationOrder, compareEdgeAndNode, leftBound, rightBound, windowLeft, windowRight); } } else if (isEdgeFieldName(fieldName2)) { Platform.ArrayUtilities.sortRange( this.iterationOrder, compareNodeAndEdge, leftBound, rightBound, windowLeft, windowRight); } else { Platform.ArrayUtilities.sortRange( this.iterationOrder, compareNodeAndNode, leftBound, rightBound, windowLeft, windowRight); } } } export class HeapSnapshotNodesProvider extends HeapSnapshotItemProvider { snapshot: HeapSnapshot; constructor(snapshot: HeapSnapshot, nodeIndexes: number[]|Uint32Array) { const indexProvider = new HeapSnapshotNodeIndexProvider(snapshot); const it = new HeapSnapshotIndexRangeIterator(indexProvider, nodeIndexes); super(it, indexProvider); this.snapshot = snapshot; } nodePosition(snapshotObjectId: number): number { this.createIterationOrder(); const node = this.snapshot.createNode(); let i = 0; if (!this.iterationOrder) { throw new Error('Iteration order not defined'); } for (; i < this.iterationOrder.length; i++) { node.nodeIndex = this.iterationOrder[i]; if (node.id() === snapshotObjectId) { break; } } if (i === this.iterationOrder.length) { return -1; } const targetNodeIndex = this.iterationOrder[i]; let smallerCount = 0; const currentComparator = (this.currentComparator as HeapSnapshotModel.HeapSnapshotModel.ComparatorConfig); const compare = this.buildCompareFunction(currentComparator); for (let i = 0; i < this.iterationOrder.length; i++) { if (compare(this.iterationOrder[i], targetNodeIndex) < 0) { ++smallerCount; } } return smallerCount; } private buildCompareFunction(comparator: HeapSnapshotModel.HeapSnapshotModel.ComparatorConfig): (arg0: number, arg1: number) => number { const nodeA = this.snapshot.createNode(); const nodeB = this.snapshot.createNode(); // TODO(crbug.com/1172300) Ignored during the jsdoc to ts migration) // eslint-disable-next-line @typescript-eslint/no-explicit-any const fieldAccessor1 = (nodeA as any)[comparator.fieldName1]; // TODO(crbug.com/1172300) Ignored during the jsdoc to ts migration) // eslint-disable-next-line @typescript-eslint/no-explicit-any const fieldAccessor2 = (nodeA as any)[comparator.fieldName2]; const ascending1 = comparator.ascending1 ? 1 : -1; const ascending2 = comparator.ascending2 ? 1 : -1; function sortByNodeField(fieldAccessor: () => void, ascending: number): number { const valueA = fieldAccessor.call(nodeA); const valueB = fieldAccessor.call(nodeB); return valueA < valueB ? -ascending : (valueA > valueB ? ascending : 0); } function sortByComparator(indexA: number, indexB: number): number { nodeA.nodeIndex = indexA; nodeB.nodeIndex = indexB; let result = sortByNodeField(fieldAccessor1, ascending1); if (result === 0) { result = sortByNodeField(fieldAccessor2, ascending2); } return result || indexA - indexB; } return sortByComparator; } sort( comparator: HeapSnapshotModel.HeapSnapshotModel.ComparatorConfig, leftBound: number, rightBound: number, windowLeft: number, windowRight: number): void { if (!this.iterationOrder) { throw new Error('Iteration order not defined'); } Platform.ArrayUtilities.sortRange( this.iterationOrder, this.buildCompareFunction(comparator), leftBound, rightBound, windowLeft, windowRight); } } export class JSHeapSnapshot extends HeapSnapshot { readonly nodeFlags: { // bit flags in 8-bit value canBeQueried: number, detachedDOMTreeNode: number, pageObject: number, // The idea is to track separately the objects owned by the page and the objects owned by debugger. }; private flags!: Uint8Array; #statistics?: HeapSnapshotModel.HeapSnapshotModel.Statistics; constructor(profile: Profile, progress: HeapSnapshotProgress) { super(profile, progress); this.nodeFlags = { // bit flags in 8-bit value canBeQueried: 1, detachedDOMTreeNode: 2, pageObject: 4, // The idea is to track separately the objects owned by the page and the objects owned by debugger. }; } createNode(nodeIndex?: number): JSHeapSnapshotNode { return new JSHeapSnapshotNode(this, nodeIndex === undefined ? -1 : nodeIndex); } createEdge(edgeIndex: number): JSHeapSnapshotEdge { return new JSHeapSnapshotEdge(this, edgeIndex); } createRetainingEdge(retainerIndex: number): JSHeapSnapshotRetainerEdge { return new JSHeapSnapshotRetainerEdge(this, retainerIndex); } override containmentEdgesFilter(): (arg0: HeapSnapshotEdge) => boolean { return (edge: HeapSnapshotEdge): boolean => !edge.isInvisible(); } override retainingEdgesFilter(): (arg0: HeapSnapshotEdge) => boolean { const containmentEdgesFilter = this.containmentEdgesFilter(); function filter(edge: HeapSnapshotEdge): boolean { return containmentEdgesFilter(edge) && !edge.node().isRoot() && !edge.isWeak(); } return filter; } override calculateFlags(): void { this.flags = new Uint8Array(this.nodeCount); this.markDetachedDOMTreeNodes(); this.markQueriableHeapObjects(); this.markPageOwnedNodes(); } #hasUserRoots(): boolean { for (let iter = this.rootNode().edges(); iter.hasNext(); iter.next()) { if (this.isUserRoot(iter.edge.node())) { return true; } } return false; } // Updates the shallow sizes for "owned" objects of types kArray or kHidden to // zero, and add their sizes to the "owner" object instead. override calculateShallowSizes(): void { // If there are no user roots, then that means the snapshot was produced with // the "expose internals" option enabled. In that case, we should faithfully // represent the actual memory allocations rather than attempting to make the // output more understandable to web developers. if (!this.#hasUserRoots()) { return; } const {nodeCount, nodes, nodeFieldCount, nodeSelfSizeOffset} = this; const kUnvisited = 0xffffffff; const kHasMultipleOwners = 0xfffffffe; if (nodeCount >= kHasMultipleOwners) { throw new Error('Too many nodes for calculateShallowSizes'); } // For each node in order, `owners` will contain the index of the owning // node or one of the two values kUnvisited or kHasMultipleOwners. The // indexes in this array are NOT already multiplied by nodeFieldCount. const owners = new Uint32Array(nodeCount); // The worklist contains the indexes of nodes which should be visited during // the second loop below. The order of visiting doesn't matter. The indexes // in this array are NOT already multiplied by nodeFieldCount. const worklist: number[] = []; const node = this.createNode(0); for (let i = 0; i < nodeCount; ++i) { if (node.isHidden() || node.isArray() || (node.isNative() && node.rawName() === 'system / ExternalStringData')) { owners[i] = kUnvisited; } else { // The node owns itself. owners[i] = i; worklist.push(i); } node.nodeIndex = node.nextNodeIndex(); } while (worklist.length !== 0) { const id = worklist.pop() as number; const owner = owners[id]; node.nodeIndex = id * nodeFieldCount; for (let iter = node.edges(); iter.hasNext(); iter.next()) { const edge = iter.edge; if (edge.isWeak()) { continue; } const targetId = edge.nodeIndex() / nodeFieldCount; switch (owners[targetId]) { case kUnvisited: owners[targetId] = owner; worklist.push(targetId); break; case targetId: case owner: case kHasMultipleOwners: // There is no change necessary if the target is already marked as: // * owned by itself, // * owned by the owner of the current source node, or // * owned by multiple nodes. break; default: owners[targetId] = kHasMultipleOwners; // It is possible that this node is already in the worklist // somewhere, but visiting it an extra time is not harmful. The // iteration is guaranteed to complete because each node can only be // added twice to the worklist: once when changing from kUnvisited // to a specific owner, and a second time when changing from that // owner to kHasMultipleOwners. worklist.push(targetId); break; } } } for (let i = 0; i < nodeCount; ++i) { const ownerId = owners[i]; switch (ownerId) { case kUnvisited: case kHasMultipleOwners: case i: break; default: { const ownedNodeIndex = i * nodeFieldCount; const ownerNodeIndex = ownerId * nodeFieldCount; node.nodeIndex = ownerNodeIndex; if (node.isSynthetic() || node.isRoot()) { // Adding shallow size to synthetic or root nodes is not useful. break; } const sizeToTransfer = nodes.getValue(ownedNodeIndex + nodeSelfSizeOffset); nodes.setValue(ownedNodeIndex + nodeSelfSizeOffset, 0); nodes.setValue( ownerNodeIndex + nodeSelfSizeOffset, nodes.getValue(ownerNodeIndex + nodeSelfSizeOffset) + sizeToTransfer); break; } } } } override calculateDistances(isForRetainersView: boolean): void { const pendingEphemeronEdges = new Set(); const snapshot = this; function filter(node: HeapSnapshotNode, edge: HeapSnapshotEdge): boolean { if (node.isHidden() && edge.name() === 'sloppy_function_map' && node.rawName() === 'system / NativeContext') { return false; } if (node.isArray() && node.rawName() === '(map descriptors)') { // DescriptorArrays are fixed arrays used to hold instance descriptors. // The format of the these objects is: // [0]: Number of descriptors // [1]: Either Smi(0) if uninitialized, or a pointer to small fixed array: // [0]: pointer to fixed array with enum cache // [1]: either Smi(0) or pointer to fixed array with indices // [i*3+2]: i-th key // [i*3+3]: i-th type // [i*3+4]: i-th descriptor // As long as maps may share descriptor arrays some of the descriptor // links may not be valid for all the maps. We just skip // all the descriptor links when calculating distances. // For more details see http://crbug.com/413608 const index = parseInt(edge.name(), 10); return index < 2 || (index % 3) !== 1; } if (edge.isInternal()) { // Snapshots represent WeakMap values as being referenced by two edges: // one from the WeakMap, and a second from the corresponding key. To // avoid the case described in crbug.com/1290800, we should set the // distance of that value to the greater of (WeakMap+1, key+1). This // part of the filter skips the first edge in the matched pair of edges, // so that the distance gets set based on the second, which should be // greater or equal due to traversal order. const match = snapshot.tryParseWeakMapEdgeName(edge.nameIndex()); if (match) { if (!pendingEphemeronEdges.delete(match.duplicatedPart)) { pendingEphemeronEdges.add(match.duplicatedPart); return false; } } } return true; } super.calculateDistances(isForRetainersView, filter); } override isUserRoot(node: HeapSnapshotNode): boolean { return node.isUserRoot() || node.isDocumentDOMTreesRoot(); } override userObjectsMapAndFlag(): {map: Uint8Array, flag: number}|null { return {map: this.flags, flag: this.nodeFlags.pageObject}; } flagsOfNode(node: HeapSnapshotNode): number { return this.flags[node.nodeIndex / this.nodeFieldCount]; } private markDetachedDOMTreeNodes(): void { const nodes = this.nodes; const nodesLength = nodes.length; const nodeFieldCount = this.nodeFieldCount; const nodeNativeType = this.nodeNativeType; const nodeTypeOffset = this.nodeTypeOffset; const flag = this.nodeFlags.detachedDOMTreeNode; const node = this.rootNode(); for (let nodeIndex = 0, ordinal = 0; nodeIndex < nodesLength; nodeIndex += nodeFieldCount, ordinal++) { const nodeType = nodes.getValue(nodeIndex + nodeTypeOffset); if (nodeType !== nodeNativeType) { continue; } node.nodeIndex = nodeIndex; if (node.name().startsWith('Detached ')) { this.flags[ordinal] |= flag; } } } private markQueriableHeapObjects(): void { // Allow runtime properties query for objects accessible from Window objects // via regular properties, and for DOM wrappers. Trying to access random objects // can cause a crash due to inconsistent state of internal properties of wrappers. const flag = this.nodeFlags.canBeQueried; const hiddenEdgeType = this.edgeHiddenType; const internalEdgeType = this.edgeInternalType; const invisibleEdgeType = this.edgeInvisibleType; const weakEdgeType = this.edgeWeakType; const edgeToNodeOffset = this.edgeToNodeOffset; const edgeTypeOffset = this.edgeTypeOffset; const edgeFieldsCount = this.edgeFieldsCount; const containmentEdges = this.containmentEdges; const nodeFieldCount = this.nodeFieldCount; const firstEdgeIndexes = this.firstEdgeIndexes; const flags = this.flags; const list: number[] = []; for (let iter = this.rootNode().edges(); iter.hasNext(); iter.next()) { if (iter.edge.node().isUserRoot()) { list.push(iter.edge.node().nodeIndex / nodeFieldCount); } } while (list.length) { const nodeOrdinal = (list.pop() as number); if (flags[nodeOrdinal] & flag) { continue; } flags[nodeOrdinal] |= flag; const beginEdgeIndex = firstEdgeIndexes[nodeOrdinal]; const endEdgeIndex = firstEdgeIndexes[nodeOrdinal + 1]; for (let edgeIndex = beginEdgeIndex; edgeIndex < endEdgeIndex; edgeIndex += edgeFieldsCount) { const childNodeIndex = containmentEdges.getValue(edgeIndex + edgeToNodeOffset); const childNodeOrdinal = childNodeIndex / nodeFieldCount; if (flags[childNodeOrdinal] & flag) { continue; } const type = containmentEdges.getValue(edgeIndex + edgeTypeOffset); if (type === hiddenEdgeType || type === invisibleEdgeType || type === internalEdgeType || type === weakEdgeType) { continue; } list.push(childNodeOrdinal); } } } private markPageOwnedNodes(): void { const edgeShortcutType = this.edgeShortcutType; const edgeElementType = this.edgeElementType; const edgeToNodeOffset = this.edgeToNodeOffset; const edgeTypeOffset = this.edgeTypeOffset; const edgeFieldsCount = this.edgeFieldsCount; const edgeWeakType = this.edgeWeakType; const firstEdgeIndexes = this.firstEdgeIndexes; const containmentEdges = this.containmentEdges; const nodeFieldCount = this.nodeFieldCount; const nodesCount = this.nodeCount; const flags = this.flags; const pageObjectFlag = this.nodeFlags.pageObject; const nodesToVisit = new Uint32Array(nodesCount); let nodesToVisitLength = 0; const rootNodeOrdinal = this.rootNodeIndexInternal / nodeFieldCount; const node = this.rootNode(); // Populate the entry points. They are Window objects and DOM Tree Roots. for (let edgeIndex = firstEdgeIndexes[rootNodeOrdinal], endEdgeIndex = firstEdgeIndexes[rootNodeOrdinal + 1]; edgeIndex < endEdgeIndex; edgeIndex += edgeFieldsCount) { const edgeType = containmentEdges.getValue(edgeIndex + edgeTypeOffset); const nodeIndex = containmentEdges.getValue(edgeIndex + edgeToNodeOffset); if (edgeType === edgeElementType) { node.nodeIndex = nodeIndex; if (!node.isDocumentDOMTreesRoot()) { continue; } } else if (edgeType !== edgeShortcutType) { continue; } const nodeOrdinal = nodeIndex / nodeFieldCount; nodesToVisit[nodesToVisitLength++] = nodeOrdinal; flags[nodeOrdinal] |= pageObjectFlag; } // Mark everything reachable with the pageObject flag. while (nodesToVisitLength) { const nodeOrdinal = nodesToVisit[--nodesToVisitLength]; const beginEdgeIndex = firstEdgeIndexes[nodeOrdinal]; const endEdgeIndex = firstEdgeIndexes[nodeOrdinal + 1]; for (let edgeIndex = beginEdgeIndex; edgeIndex < endEdgeIndex; edgeIndex += edgeFieldsCount) { const childNodeIndex = containmentEdges.getValue(edgeIndex + edgeToNodeOffset); const childNodeOrdinal = childNodeIndex / nodeFieldCount; if (flags[childNodeOrdinal] & pageObjectFlag) { continue; } const type = containmentEdges.getValue(edgeIndex + edgeTypeOffset); if (type === edgeWeakType) { continue; } nodesToVisit[nodesToVisitLength++] = childNodeOrdinal; flags[childNodeOrdinal] |= pageObjectFlag; } } } override calculateStatistics(): void { const nodeFieldCount = this.nodeFieldCount; const nodes = this.nodes; const nodesLength = nodes.length; const nodeTypeOffset = this.nodeTypeOffset; const nodeSizeOffset = this.nodeSelfSizeOffset; const nodeNativeType = this.nodeNativeType; const nodeCodeType = this.nodeCodeType; const nodeConsStringType = this.nodeConsStringType; const nodeSlicedStringType = this.nodeSlicedStringType; const nodeHiddenType = this.nodeHiddenType; const nodeStringType = this.nodeStringType; let sizeNative = this.profile.snapshot.extra_native_bytes ?? 0; let sizeTypedArrays = 0; let sizeCode = 0; let sizeStrings = 0; let sizeJSArrays = 0; let sizeSystem = 0; const node = this.rootNode(); for (let nodeIndex = 0; nodeIndex < nodesLength; nodeIndex += nodeFieldCount) { const nodeSize = nodes.getValue(nodeIndex + nodeSizeOffset); const nodeType = nodes.getValue(nodeIndex + nodeTypeOffset); if (nodeType === nodeHiddenType) { sizeSystem += nodeSize; continue; } node.nodeIndex = nodeIndex; if (nodeType === nodeNativeType) { sizeNative += nodeSize; if (node.rawName() === 'system / JSArrayBufferData') { sizeTypedArrays += nodeSize; } } else if (nodeType === nodeCodeType) { sizeCode += nodeSize; } else if (nodeType === nodeConsStringType || nodeType === nodeSlicedStringType || nodeType === nodeStringType) { sizeStrings += nodeSize; } else if (node.rawName() === 'Array') { sizeJSArrays += this.calculateArraySize(node); } } this.#statistics = { total: this.totalSize, native: { total: sizeNative, typedArrays: sizeTypedArrays, }, v8heap: { total: this.totalSize - sizeNative, code: sizeCode, jsArrays: sizeJSArrays, strings: sizeStrings, system: sizeSystem, } }; } private calculateArraySize(node: HeapSnapshotNode): number { let size = node.selfSize(); const beginEdgeIndex = node.edgeIndexesStart(); const endEdgeIndex = node.edgeIndexesEnd(); const containmentEdges = this.containmentEdges; const strings = this.strings; const edgeToNodeOffset = this.edgeToNodeOffset; const edgeTypeOffset = this.edgeTypeOffset; const edgeNameOffset = this.edgeNameOffset; const edgeFieldsCount = this.edgeFieldsCount; const edgeInternalType = this.edgeInternalType; for (let edgeIndex = beginEdgeIndex; edgeIndex < endEdgeIndex; edgeIndex += edgeFieldsCount) { const edgeType = containmentEdges.getValue(edgeIndex + edgeTypeOffset); if (edgeType !== edgeInternalType) { continue; } const edgeName = strings[containmentEdges.getValue(edgeIndex + edgeNameOffset)]; if (edgeName !== 'elements') { continue; } const elementsNodeIndex = containmentEdges.getValue(edgeIndex + edgeToNodeOffset); node.nodeIndex = elementsNodeIndex; if (node.retainersCount() === 1) { size += node.selfSize(); } break; } return size; } getStatistics(): HeapSnapshotModel.HeapSnapshotModel.Statistics { return this.#statistics as HeapSnapshotModel.HeapSnapshotModel.Statistics; } } /** Creates and initializes a JSHeapSnapshot using only one thread. **/ export async function createJSHeapSnapshotForTesting(profile: Profile): Promise { const result = new JSHeapSnapshot(profile, new HeapSnapshotProgress()); const channel = new MessageChannel(); new SecondaryInitManager(channel.port2); await result.initialize(channel.port1); return result; } export class JSHeapSnapshotNode extends HeapSnapshotNode { canBeQueried(): boolean { const snapshot = (this.snapshot as JSHeapSnapshot); const flags = snapshot.flagsOfNode(this); return Boolean(flags & snapshot.nodeFlags.canBeQueried); } override name(): string { const snapshot = this.snapshot; if (this.rawType() === snapshot.nodeConsStringType) { return this.consStringName(); } if (this.rawType() === snapshot.nodeObjectType && this.rawName() === 'Object') { return this.#plainObjectName(); } return this.rawName(); } private consStringName(): string { const snapshot = this.snapshot; const consStringType = snapshot.nodeConsStringType; const edgeInternalType = snapshot.edgeInternalType; const edgeFieldsCount = snapshot.edgeFieldsCount; const edgeToNodeOffset = snapshot.edgeToNodeOffset; const edgeTypeOffset = snapshot.edgeTypeOffset; const edgeNameOffset = snapshot.edgeNameOffset; const strings = snapshot.strings; const edges = snapshot.containmentEdges; const firstEdgeIndexes = snapshot.firstEdgeIndexes; const nodeFieldCount = snapshot.nodeFieldCount; const nodeTypeOffset = snapshot.nodeTypeOffset; const nodeNameOffset = snapshot.nodeNameOffset; const nodes = snapshot.nodes; const nodesStack = []; nodesStack.push(this.nodeIndex); let name = ''; while (nodesStack.length && name.length < 1024) { const nodeIndex = (nodesStack.pop() as number); if (nodes.getValue(nodeIndex + nodeTypeOffset) !== consStringType) { name += strings[nodes.getValue(nodeIndex + nodeNameOffset)]; continue; } const nodeOrdinal = nodeIndex / nodeFieldCount; const beginEdgeIndex = firstEdgeIndexes[nodeOrdinal]; const endEdgeIndex = firstEdgeIndexes[nodeOrdinal + 1]; let firstNodeIndex = 0; let secondNodeIndex = 0; for (let edgeIndex = beginEdgeIndex; edgeIndex < endEdgeIndex && (!firstNodeIndex || !secondNodeIndex); edgeIndex += edgeFieldsCount) { const edgeType = edges.getValue(edgeIndex + edgeTypeOffset); if (edgeType === edgeInternalType) { const edgeName = strings[edges.getValue(edgeIndex + edgeNameOffset)]; if (edgeName === 'first') { firstNodeIndex = edges.getValue(edgeIndex + edgeToNodeOffset); } else if (edgeName === 'second') { secondNodeIndex = edges.getValue(edgeIndex + edgeToNodeOffset); } } } nodesStack.push(secondNodeIndex); nodesStack.push(firstNodeIndex); } return name; } // Creates a name for plain JS objects, which looks something like // '{propName, otherProp, thirdProp, ..., secondToLastProp, lastProp}'. // A variable number of property names is included, depending on the length // of the property names, so that the result fits nicely in a reasonably // sized DevTools window. #plainObjectName(): string { const snapshot = this.snapshot; const {edgeFieldsCount, edgePropertyType} = snapshot; const edge = snapshot.createEdge(0); let categoryNameStart = '{'; let categoryNameEnd = '}'; let edgeIndexFromStart = this.edgeIndexesStart(); let edgeIndexFromEnd = this.edgeIndexesEnd() - edgeFieldsCount; let nextFromEnd = false; while (edgeIndexFromStart <= edgeIndexFromEnd) { edge.edgeIndex = nextFromEnd ? edgeIndexFromEnd : edgeIndexFromStart; // Skip non-property edges and the special __proto__ property. if (edge.rawType() !== edgePropertyType || edge.name() === '__proto__') { if (nextFromEnd) { edgeIndexFromEnd -= edgeFieldsCount; } else { edgeIndexFromStart += edgeFieldsCount; } continue; } const formatted = JSHeapSnapshotNode.formatPropertyName(edge.name()); // Always include at least one property, regardless of its length. Beyond that point, // only include more properties if the name isn't too long. if (categoryNameStart.length > 1 && categoryNameStart.length + categoryNameEnd.length + formatted.length > 100) { break; } if (nextFromEnd) { edgeIndexFromEnd -= edgeFieldsCount; if (categoryNameEnd.length > 1) { categoryNameEnd = ', ' + categoryNameEnd; } categoryNameEnd = formatted + categoryNameEnd; } else { edgeIndexFromStart += edgeFieldsCount; if (categoryNameStart.length > 1) { categoryNameStart += ', '; } categoryNameStart += formatted; } nextFromEnd = !nextFromEnd; } if (edgeIndexFromStart <= edgeIndexFromEnd) { categoryNameStart += ', …'; } if (categoryNameEnd.length > 1) { categoryNameStart += ', '; } return categoryNameStart + categoryNameEnd; } static formatPropertyName(name: string): string { // We don't need a strict test for whether a property name follows the // rules for being a JS identifier, but property names containing commas, // quotation marks, or braces could cause confusion, so we'll escape those. if (/[,'"{}]/.test(name)) { name = JSON.stringify({[name]: 0}); name = name.substring(1, name.length - 3); } return name; } override id(): number { const snapshot = this.snapshot; return snapshot.nodes.getValue(this.nodeIndex + snapshot.nodeIdOffset); } override isHidden(): boolean { return this.rawType() === this.snapshot.nodeHiddenType; } override isArray(): boolean { return this.rawType() === this.snapshot.nodeArrayType; } override isSynthetic(): boolean { return this.rawType() === this.snapshot.nodeSyntheticType; } isNative(): boolean { return this.rawType() === this.snapshot.nodeNativeType; } override isUserRoot(): boolean { return !this.isSynthetic(); } override isDocumentDOMTreesRoot(): boolean { return this.isSynthetic() && this.rawName() === '(Document DOM trees)'; } override serialize(): HeapSnapshotModel.HeapSnapshotModel.Node { const result = super.serialize(); const snapshot = (this.snapshot as JSHeapSnapshot); const flags = snapshot.flagsOfNode(this); if (flags & snapshot.nodeFlags.canBeQueried) { result.canBeQueried = true; } if (flags & snapshot.nodeFlags.detachedDOMTreeNode) { result.detachedDOMTreeNode = true; } return result; } } export class JSHeapSnapshotEdge extends HeapSnapshotEdge { override clone(): JSHeapSnapshotEdge { const snapshot = (this.snapshot as JSHeapSnapshot); return new JSHeapSnapshotEdge(snapshot, this.edgeIndex); } override hasStringName(): boolean { if (!this.isShortcut()) { return this.#hasStringName(); } // @ts-expect-error parseInt is successful against numbers. return isNaN(parseInt(this.#name(), 10)); } isElement(): boolean { return this.rawType() === this.snapshot.edgeElementType; } isHidden(): boolean { return this.rawType() === this.snapshot.edgeHiddenType; } override isWeak(): boolean { return this.rawType() === this.snapshot.edgeWeakType; } override isInternal(): boolean { return this.rawType() === this.snapshot.edgeInternalType; } override isInvisible(): boolean { return this.rawType() === this.snapshot.edgeInvisibleType; } isShortcut(): boolean { return this.rawType() === this.snapshot.edgeShortcutType; } override name(): string { const name = this.#name(); if (!this.isShortcut()) { return String(name); } // @ts-expect-error parseInt is successful against numbers. const numName = parseInt(name, 10); return String(isNaN(numName) ? name : numName); } override toString(): string { const name = this.name(); switch (this.type()) { case 'context': return '->' + name; case 'element': return '[' + name + ']'; case 'weak': return '[[' + name + ']]'; case 'property': return name.indexOf(' ') === -1 ? '.' + name : '["' + name + '"]'; case 'shortcut': if (typeof name === 'string') { return name.indexOf(' ') === -1 ? '.' + name : '["' + name + '"]'; } return '[' + name + ']'; case 'internal': case 'hidden': case 'invisible': return '{' + name + '}'; } return '?' + name + '?'; } #hasStringName(): boolean { const type = this.rawType(); const snapshot = this.snapshot; return type !== snapshot.edgeElementType && type !== snapshot.edgeHiddenType; } #name(): string|number { return this.#hasStringName() ? this.snapshot.strings[this.nameOrIndex()] : this.nameOrIndex(); } private nameOrIndex(): number { return this.edges.getValue(this.edgeIndex + this.snapshot.edgeNameOffset); } override rawType(): number { return this.edges.getValue(this.edgeIndex + this.snapshot.edgeTypeOffset); } override nameIndex(): number { if (!this.#hasStringName()) { throw new Error('Edge does not have string name'); } return this.nameOrIndex(); } } export class JSHeapSnapshotRetainerEdge extends HeapSnapshotRetainerEdge { override clone(): JSHeapSnapshotRetainerEdge { const snapshot = (this.snapshot as JSHeapSnapshot); return new JSHeapSnapshotRetainerEdge(snapshot, this.retainerIndex()); } isHidden(): boolean { return this.edge().isHidden(); } isInvisible(): boolean { return this.edge().isInvisible(); } isShortcut(): boolean { return this.edge().isShortcut(); } isWeak(): boolean { return this.edge().isWeak(); } }