1/*
2 * Copyright (C) 2012 Google Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are
6 * met:
7 *
8 *     * Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 *     * Redistributions in binary form must reproduce the above
11 * copyright notice, this list of conditions and the following disclaimer
12 * in the documentation and/or other materials provided with the
13 * distribution.
14 *     * Neither the name of Google Inc. nor the names of its
15 * contributors may be used to endorse or promote products derived from
16 * this software without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 */
30
31/**
32 * @constructor
33 * @extends {WebInspector.HeapSnapshot}
34 */
35WebInspector.JSHeapSnapshot = function(profile)
36{
37    this._nodeFlags = { // bit flags
38        canBeQueried: 1,
39        detachedDOMTreeNode: 2,
40        pageObject: 4, // The idea is to track separately the objects owned by the page and the objects owned by debugger.
41
42        visitedMarkerMask: 0x0ffff, // bits: 0,1111,1111,1111,1111
43        visitedMarker:     0x10000  // bits: 1,0000,0000,0000,0000
44    };
45    WebInspector.HeapSnapshot.call(this, profile);
46}
47
48WebInspector.JSHeapSnapshot.prototype = {
49    createNode: function(nodeIndex)
50    {
51        return new WebInspector.JSHeapSnapshotNode(this, nodeIndex);
52    },
53
54    createEdge: function(edges, edgeIndex)
55    {
56        return new WebInspector.JSHeapSnapshotEdge(this, edges, edgeIndex);
57    },
58
59    createRetainingEdge: function(retainedNodeIndex, retainerIndex)
60    {
61        return new WebInspector.JSHeapSnapshotRetainerEdge(this, retainedNodeIndex, retainerIndex);
62    },
63
64    classNodesFilter: function()
65    {
66        function filter(node)
67        {
68            return node.isUserObject();
69        }
70        return filter;
71    },
72
73    containmentEdgesFilter: function(showHiddenData)
74    {
75        function filter(edge) {
76            if (edge.isInvisible())
77                return false;
78            if (showHiddenData)
79                return true;
80            return !edge.isHidden() && !edge.node().isHidden();
81        }
82        return filter;
83    },
84
85    retainingEdgesFilter: function(showHiddenData)
86    {
87        var containmentEdgesFilter = this.containmentEdgesFilter(showHiddenData);
88        function filter(edge) {
89            if (!containmentEdgesFilter(edge))
90                return false;
91            return edge.node().id() !== 1 && !edge.node().isSynthetic() && !edge.isWeak();
92        }
93        return filter;
94    },
95
96    dispose: function()
97    {
98        WebInspector.HeapSnapshot.prototype.dispose.call(this);
99        delete this._flags;
100    },
101
102    _markInvisibleEdges: function()
103    {
104        // Mark hidden edges of global objects as invisible.
105        // FIXME: This is a temporary measure. Normally, we should
106        // really hide all hidden nodes.
107        for (var iter = this.rootNode().edges(); iter.hasNext(); iter.next()) {
108            var edge = iter.edge;
109            if (!edge.isShortcut())
110                continue;
111            var node = edge.node();
112            var propNames = {};
113            for (var innerIter = node.edges(); innerIter.hasNext(); innerIter.next()) {
114                var globalObjEdge = innerIter.edge;
115                if (globalObjEdge.isShortcut())
116                    propNames[globalObjEdge._nameOrIndex()] = true;
117            }
118            for (innerIter.rewind(); innerIter.hasNext(); innerIter.next()) {
119                var globalObjEdge = innerIter.edge;
120                if (!globalObjEdge.isShortcut()
121                    && globalObjEdge.node().isHidden()
122                    && globalObjEdge._hasStringName()
123                    && (globalObjEdge._nameOrIndex() in propNames))
124                    this._containmentEdges[globalObjEdge._edges._start + globalObjEdge.edgeIndex + this._edgeTypeOffset] = this._edgeInvisibleType;
125            }
126        }
127    },
128
129    _calculateFlags: function()
130    {
131        this._flags = new Uint32Array(this.nodeCount);
132        this._markDetachedDOMTreeNodes();
133        this._markQueriableHeapObjects();
134        this._markPageOwnedNodes();
135    },
136
137    distanceForUserRoot: function(node)
138    {
139        if (node.isWindow())
140            return 1;
141        if (node.isDocumentDOMTreesRoot())
142            return 0;
143        return -1;
144    },
145
146    userObjectsMapAndFlag: function()
147    {
148        return {
149            map: this._flags,
150            flag: this._nodeFlags.pageObject
151        };
152    },
153
154    _flagsOfNode: function(node)
155    {
156        return this._flags[node.nodeIndex / this._nodeFieldCount];
157    },
158
159    _markDetachedDOMTreeNodes: function()
160    {
161        var flag = this._nodeFlags.detachedDOMTreeNode;
162        var detachedDOMTreesRoot;
163        for (var iter = this.rootNode().edges(); iter.hasNext(); iter.next()) {
164            var node = iter.edge.node();
165            if (node.name() === "(Detached DOM trees)") {
166                detachedDOMTreesRoot = node;
167                break;
168            }
169        }
170
171        if (!detachedDOMTreesRoot)
172            return;
173
174        var detachedDOMTreeRE = /^Detached DOM tree/;
175        for (var iter = detachedDOMTreesRoot.edges(); iter.hasNext(); iter.next()) {
176            var node = iter.edge.node();
177            if (detachedDOMTreeRE.test(node.className())) {
178                for (var edgesIter = node.edges(); edgesIter.hasNext(); edgesIter.next())
179                    this._flags[edgesIter.edge.node().nodeIndex / this._nodeFieldCount] |= flag;
180            }
181        }
182    },
183
184    _markQueriableHeapObjects: function()
185    {
186        // Allow runtime properties query for objects accessible from Window objects
187        // via regular properties, and for DOM wrappers. Trying to access random objects
188        // can cause a crash due to insonsistent state of internal properties of wrappers.
189        var flag = this._nodeFlags.canBeQueried;
190        var hiddenEdgeType = this._edgeHiddenType;
191        var internalEdgeType = this._edgeInternalType;
192        var invisibleEdgeType = this._edgeInvisibleType;
193        var weakEdgeType = this._edgeWeakType;
194        var edgeToNodeOffset = this._edgeToNodeOffset;
195        var edgeTypeOffset = this._edgeTypeOffset;
196        var edgeFieldsCount = this._edgeFieldsCount;
197        var containmentEdges = this._containmentEdges;
198        var nodes = this._nodes;
199        var nodeCount = this.nodeCount;
200        var nodeFieldCount = this._nodeFieldCount;
201        var firstEdgeIndexes = this._firstEdgeIndexes;
202
203        var flags = this._flags;
204        var list = [];
205
206        for (var iter = this.rootNode().edges(); iter.hasNext(); iter.next()) {
207            if (iter.edge.node().isWindow())
208                list.push(iter.edge.node().nodeIndex / nodeFieldCount);
209        }
210
211        while (list.length) {
212            var nodeOrdinal = list.pop();
213            if (flags[nodeOrdinal] & flag)
214                continue;
215            flags[nodeOrdinal] |= flag;
216            var beginEdgeIndex = firstEdgeIndexes[nodeOrdinal];
217            var endEdgeIndex = firstEdgeIndexes[nodeOrdinal + 1];
218            for (var edgeIndex = beginEdgeIndex; edgeIndex < endEdgeIndex; edgeIndex += edgeFieldsCount) {
219                var childNodeIndex = containmentEdges[edgeIndex + edgeToNodeOffset];
220                var childNodeOrdinal = childNodeIndex / nodeFieldCount;
221                if (flags[childNodeOrdinal] & flag)
222                    continue;
223                var type = containmentEdges[edgeIndex + edgeTypeOffset];
224                if (type === hiddenEdgeType || type === invisibleEdgeType || type === internalEdgeType || type === weakEdgeType)
225                    continue;
226                list.push(childNodeOrdinal);
227            }
228        }
229    },
230
231    _markPageOwnedNodes: function()
232    {
233        var edgeShortcutType = this._edgeShortcutType;
234        var edgeElementType = this._edgeElementType;
235        var edgeToNodeOffset = this._edgeToNodeOffset;
236        var edgeTypeOffset = this._edgeTypeOffset;
237        var edgeFieldsCount = this._edgeFieldsCount;
238        var edgeWeakType = this._edgeWeakType;
239        var firstEdgeIndexes = this._firstEdgeIndexes;
240        var containmentEdges = this._containmentEdges;
241        var containmentEdgesLength = containmentEdges.length;
242        var nodes = this._nodes;
243        var nodeFieldCount = this._nodeFieldCount;
244        var nodesCount = this.nodeCount;
245
246        var flags = this._flags;
247        var flag = this._nodeFlags.pageObject;
248        var visitedMarker = this._nodeFlags.visitedMarker;
249        var visitedMarkerMask = this._nodeFlags.visitedMarkerMask;
250        var markerAndFlag = visitedMarker | flag;
251
252        var nodesToVisit = new Uint32Array(nodesCount);
253        var nodesToVisitLength = 0;
254
255        var rootNodeOrdinal = this._rootNodeIndex / nodeFieldCount;
256        var node = this.rootNode();
257        for (var edgeIndex = firstEdgeIndexes[rootNodeOrdinal], endEdgeIndex = firstEdgeIndexes[rootNodeOrdinal + 1];
258             edgeIndex < endEdgeIndex;
259             edgeIndex += edgeFieldsCount) {
260            var edgeType = containmentEdges[edgeIndex + edgeTypeOffset];
261            var nodeIndex = containmentEdges[edgeIndex + edgeToNodeOffset];
262            if (edgeType === edgeElementType) {
263                node.nodeIndex = nodeIndex;
264                if (!node.isDocumentDOMTreesRoot())
265                    continue;
266            } else if (edgeType !== edgeShortcutType)
267                continue;
268            var nodeOrdinal = nodeIndex / nodeFieldCount;
269            nodesToVisit[nodesToVisitLength++] = nodeOrdinal;
270            flags[nodeOrdinal] |= visitedMarker;
271        }
272
273        while (nodesToVisitLength) {
274            var nodeOrdinal = nodesToVisit[--nodesToVisitLength];
275            flags[nodeOrdinal] |= flag;
276            flags[nodeOrdinal] &= visitedMarkerMask;
277            var beginEdgeIndex = firstEdgeIndexes[nodeOrdinal];
278            var endEdgeIndex = firstEdgeIndexes[nodeOrdinal + 1];
279            for (var edgeIndex = beginEdgeIndex; edgeIndex < endEdgeIndex; edgeIndex += edgeFieldsCount) {
280                var childNodeIndex = containmentEdges[edgeIndex + edgeToNodeOffset];
281                var childNodeOrdinal = childNodeIndex / nodeFieldCount;
282                if (flags[childNodeOrdinal] & markerAndFlag)
283                    continue;
284                var type = containmentEdges[edgeIndex + edgeTypeOffset];
285                if (type === edgeWeakType)
286                    continue;
287                nodesToVisit[nodesToVisitLength++] = childNodeOrdinal;
288                flags[childNodeOrdinal] |= visitedMarker;
289            }
290        }
291    },
292
293    __proto__: WebInspector.HeapSnapshot.prototype
294};
295
296/**
297 * @constructor
298 * @extends {WebInspector.HeapSnapshotNode}
299 * @param {WebInspector.JSHeapSnapshot} snapshot
300 * @param {number=} nodeIndex
301 */
302WebInspector.JSHeapSnapshotNode = function(snapshot, nodeIndex)
303{
304    WebInspector.HeapSnapshotNode.call(this, snapshot, nodeIndex)
305}
306
307WebInspector.JSHeapSnapshotNode.prototype = {
308    canBeQueried: function()
309    {
310        var flags = this._snapshot._flagsOfNode(this);
311        return !!(flags & this._snapshot._nodeFlags.canBeQueried);
312    },
313
314    isUserObject: function()
315    {
316        var flags = this._snapshot._flagsOfNode(this);
317        return !!(flags & this._snapshot._nodeFlags.pageObject);
318    },
319
320    className: function()
321    {
322        var type = this.type();
323        switch (type) {
324        case "hidden":
325            return "(system)";
326        case "object":
327        case "native":
328            return this.name();
329        case "code":
330            return "(compiled code)";
331        default:
332            return "(" + type + ")";
333        }
334    },
335
336    classIndex: function()
337    {
338        var snapshot = this._snapshot;
339        var nodes = snapshot._nodes;
340        var type = nodes[this.nodeIndex + snapshot._nodeTypeOffset];;
341        if (type === snapshot._nodeObjectType || type === snapshot._nodeNativeType)
342            return nodes[this.nodeIndex + snapshot._nodeNameOffset];
343        return -1 - type;
344    },
345
346    id: function()
347    {
348        var snapshot = this._snapshot;
349        return snapshot._nodes[this.nodeIndex + snapshot._nodeIdOffset];
350    },
351
352    isHidden: function()
353    {
354        return this._type() === this._snapshot._nodeHiddenType;
355    },
356
357    isSynthetic: function()
358    {
359        return this._type() === this._snapshot._nodeSyntheticType;
360    },
361
362    isWindow: function()
363    {
364        const windowRE = /^Window/;
365        return windowRE.test(this.name());
366    },
367
368    isDocumentDOMTreesRoot: function()
369    {
370        return this.isSynthetic() && this.name() === "(Document DOM trees)";
371    },
372
373    serialize: function()
374    {
375        var result = WebInspector.HeapSnapshotNode.prototype.serialize.call(this);
376        var flags = this._snapshot._flagsOfNode(this);
377        if (flags & this._snapshot._nodeFlags.canBeQueried)
378            result.canBeQueried = true;
379        if (flags & this._snapshot._nodeFlags.detachedDOMTreeNode)
380            result.detachedDOMTreeNode = true;
381        return result;
382    },
383
384    __proto__: WebInspector.HeapSnapshotNode.prototype
385};
386
387/**
388 * @constructor
389 * @extends {WebInspector.HeapSnapshotEdge}
390 * @param {WebInspector.JSHeapSnapshot} snapshot
391 * @param {Array.<number>} edges
392 * @param {number=} edgeIndex
393 */
394WebInspector.JSHeapSnapshotEdge = function(snapshot, edges, edgeIndex)
395{
396    WebInspector.HeapSnapshotEdge.call(this, snapshot, edges, edgeIndex);
397}
398
399WebInspector.JSHeapSnapshotEdge.prototype = {
400    clone: function()
401    {
402        return new WebInspector.JSHeapSnapshotEdge(this._snapshot, this._edges, this.edgeIndex);
403    },
404
405    hasStringName: function()
406    {
407        if (!this.isShortcut())
408            return this._hasStringName();
409        return isNaN(parseInt(this._name(), 10));
410    },
411
412    isElement: function()
413    {
414        return this._type() === this._snapshot._edgeElementType;
415    },
416
417    isHidden: function()
418    {
419        return this._type() === this._snapshot._edgeHiddenType;
420    },
421
422    isWeak: function()
423    {
424        return this._type() === this._snapshot._edgeWeakType;
425    },
426
427    isInternal: function()
428    {
429        return this._type() === this._snapshot._edgeInternalType;
430    },
431
432    isInvisible: function()
433    {
434        return this._type() === this._snapshot._edgeInvisibleType;
435    },
436
437    isShortcut: function()
438    {
439        return this._type() === this._snapshot._edgeShortcutType;
440    },
441
442    name: function()
443    {
444        if (!this.isShortcut())
445            return this._name();
446        var numName = parseInt(this._name(), 10);
447        return isNaN(numName) ? this._name() : numName;
448    },
449
450    toString: function()
451    {
452        var name = this.name();
453        switch (this.type()) {
454        case "context": return "->" + name;
455        case "element": return "[" + name + "]";
456        case "weak": return "[[" + name + "]]";
457        case "property":
458            return name.indexOf(" ") === -1 ? "." + name : "[\"" + name + "\"]";
459        case "shortcut":
460            if (typeof name === "string")
461                return name.indexOf(" ") === -1 ? "." + name : "[\"" + name + "\"]";
462            else
463                return "[" + name + "]";
464        case "internal":
465        case "hidden":
466        case "invisible":
467            return "{" + name + "}";
468        };
469        return "?" + name + "?";
470    },
471
472    _hasStringName: function()
473    {
474        return !this.isElement() && !this.isHidden() && !this.isWeak();
475    },
476
477    _name: function()
478    {
479        return this._hasStringName() ? this._snapshot._strings[this._nameOrIndex()] : this._nameOrIndex();
480    },
481
482    _nameOrIndex: function()
483    {
484        return this._edges.item(this.edgeIndex + this._snapshot._edgeNameOffset);
485    },
486
487    _type: function()
488    {
489        return this._edges.item(this.edgeIndex + this._snapshot._edgeTypeOffset);
490    },
491
492    __proto__: WebInspector.HeapSnapshotEdge.prototype
493};
494
495
496/**
497 * @constructor
498 * @extends {WebInspector.HeapSnapshotRetainerEdge}
499 * @param {WebInspector.JSHeapSnapshot} snapshot
500 */
501WebInspector.JSHeapSnapshotRetainerEdge = function(snapshot, retainedNodeIndex, retainerIndex)
502{
503    WebInspector.HeapSnapshotRetainerEdge.call(this, snapshot, retainedNodeIndex, retainerIndex);
504}
505
506WebInspector.JSHeapSnapshotRetainerEdge.prototype = {
507    clone: function()
508    {
509        return new WebInspector.JSHeapSnapshotRetainerEdge(this._snapshot, this._retainedNodeIndex, this.retainerIndex());
510    },
511
512    isHidden: function()
513    {
514        return this._edge().isHidden();
515    },
516
517    isInternal: function()
518    {
519        return this._edge().isInternal();
520    },
521
522    isInvisible: function()
523    {
524        return this._edge().isInvisible();
525    },
526
527    isShortcut: function()
528    {
529        return this._edge().isShortcut();
530    },
531
532    isWeak: function()
533    {
534        return this._edge().isWeak();
535    },
536
537    __proto__: WebInspector.HeapSnapshotRetainerEdge.prototype
538}
539
540