| // Copyright (c) 2018, the Dart project authors. Please see the AUTHORS file |
| // for details. All rights reserved. Use of this source code is governed by a |
| // BSD-style license that can be found in the LICENSE file. |
| |
| import "package:expect/expect.dart"; |
| import "package:dart2js_info/src/graph.dart"; |
| |
| class _NodeInfo { |
| int type; |
| int name; |
| int id; |
| int selfSize; |
| int edgeCount; |
| _NodeInfo( |
| this.type, |
| this.name, |
| this.id, |
| this.selfSize, |
| this.edgeCount, |
| ); |
| } |
| |
| const List<String> _kRequiredNodeFields = [ |
| "type", |
| "name", |
| "id", |
| "self_size", |
| "edge_count", |
| ]; |
| |
| class _EdgeInfo { |
| int type; |
| int nameOrIndex; |
| int nodeOffset; |
| _EdgeInfo( |
| this.type, |
| this.nameOrIndex, |
| this.nodeOffset, |
| ); |
| } |
| |
| const List<String> _kRequiredEdgeFields = [ |
| "type", |
| "name_or_index", |
| "to_node", |
| ]; |
| |
| class NodeInfo { |
| final String type; |
| final String name; |
| final int id; |
| final int selfSize; |
| NodeInfo( |
| this.type, |
| this.name, |
| this.id, |
| this.selfSize, |
| ); |
| } |
| |
| class EdgeInfo { |
| final int target; |
| final String type; |
| |
| // Either a string for property names or an int for array/context elements. |
| final dynamic nameOrIndex; |
| |
| EdgeInfo(this.target, this.type, this.nameOrIndex); |
| } |
| |
| class V8SnapshotProfile extends Graph<int> { |
| // Indexed by node offset. |
| final Map<int, _NodeInfo> _nodes = {}; |
| |
| // Indexed by start node offset. |
| final Map<int, List<_EdgeInfo>> _toEdges = {}; |
| final Map<int, List<_EdgeInfo>> _fromEdges = {}; |
| |
| List<String> _nodeFields = []; |
| List<String> _edgeFields = []; |
| |
| List<String> _nodeTypes = []; |
| List<String> _edgeTypes = []; |
| |
| List<String> _strings = []; |
| |
| // Only used to ensure IDs are unique. |
| Set<int> _ids = Set<int>(); |
| |
| V8SnapshotProfile.fromJson(Map top) { |
| final Map snapshot = top["snapshot"]; |
| _parseMetadata(snapshot["meta"]); |
| |
| _parseStrings(top["strings"]); |
| Expect.equals(snapshot["node_count"], _parseNodes(top["nodes"])); |
| Expect.equals(snapshot["edge_count"], _parseEdges(top["edges"])); |
| |
| _verifyRoot(); |
| |
| _calculateFromEdges(); |
| } |
| |
| void _verifyRoot() { |
| // HeapSnapshotWorker.HeapSnapshot.calculateDistances (from HeapSnapshot.js) |
| // assumes that the root does not have more than one edge to any other node |
| // (most likely an oversight). |
| final Set<int> roots = <int>{}; |
| for (final edge in _toEdges[root]) { |
| final int to = edge.nodeOffset; |
| Expect.isTrue(!roots.contains(to)); |
| roots.add(to); |
| } |
| |
| // Check that all nodes are reachable from the root (offset 0). |
| final Set<int> enqueued = {root}; |
| final dfs = <int>[root]; |
| while (!dfs.isEmpty) { |
| final next = dfs.removeLast(); |
| for (final edge in _toEdges[next]) { |
| if (!enqueued.contains(edge.nodeOffset)) { |
| enqueued.add(edge.nodeOffset); |
| dfs.add(edge.nodeOffset); |
| } |
| } |
| } |
| Expect.equals(enqueued.length, nodeCount); |
| } |
| |
| void _parseMetadata(Map meta) { |
| final List nodeFields = meta["node_fields"]; |
| nodeFields.forEach(_nodeFields.add); |
| Expect.isTrue(_kRequiredNodeFields.every(_nodeFields.contains)); |
| |
| final List edgeFields = meta["edge_fields"]; |
| edgeFields.forEach(_edgeFields.add); |
| Expect.isTrue(_kRequiredEdgeFields.every(_edgeFields.contains)); |
| |
| // First entry of "node_types" is an array with the actual node types. IDK |
| // what the other entries are for. |
| List nodeTypes = meta["node_types"]; |
| nodeTypes = nodeTypes[0]; |
| nodeTypes.forEach(_nodeTypes.add); |
| |
| // Same for edges. |
| List edgeTypes = meta["edge_types"]; |
| edgeTypes = edgeTypes[0]; |
| edgeTypes.forEach(_edgeTypes.add); |
| } |
| |
| int _parseNodes(List nodes) { |
| final int typeIndex = _nodeFields.indexOf("type"); |
| final int nameIndex = _nodeFields.indexOf("name"); |
| final int idIndex = _nodeFields.indexOf("id"); |
| final int selfSizeIndex = _nodeFields.indexOf("self_size"); |
| final int edgeCountIndex = _nodeFields.indexOf("edge_count"); |
| |
| int offset = 0; |
| for (; offset < nodes.length; offset += _nodeFields.length) { |
| final int type = nodes[offset + typeIndex]; |
| Expect.isTrue(0 <= type && type < _nodeTypes.length); |
| |
| final int name = nodes[offset + nameIndex]; |
| Expect.isTrue(0 <= name && name < _strings.length); |
| |
| final int id = nodes[offset + idIndex]; |
| Expect.isTrue(id >= 0); |
| Expect.isFalse(_ids.contains(id)); |
| _ids.add(id); |
| |
| final int selfSize = nodes[offset + selfSizeIndex]; |
| Expect.isTrue(selfSize >= 0); |
| |
| final int edgeCount = nodes[offset + edgeCountIndex]; |
| Expect.isTrue(edgeCount >= 0); |
| |
| _nodes[offset] = _NodeInfo(type, name, id, selfSize, edgeCount); |
| } |
| |
| Expect.equals(offset, nodes.length); |
| return offset ~/ _nodeFields.length; |
| } |
| |
| int _parseEdges(List edges) { |
| final int typeIndex = _edgeFields.indexOf("type"); |
| final int nameOrIndexIndex = _edgeFields.indexOf("name_or_index"); |
| final int toNodeIndex = _edgeFields.indexOf("to_node"); |
| |
| int edgeOffset = 0; |
| for (int nodeOffset = 0; |
| nodeOffset < _nodes.length * _nodeFields.length; |
| nodeOffset += _nodeFields.length) { |
| final int edgeCount = _nodes[nodeOffset].edgeCount; |
| final List<_EdgeInfo> nodeEdges = List<_EdgeInfo>(edgeCount); |
| for (int i = 0; i < edgeCount; ++i, edgeOffset += _edgeFields.length) { |
| final int type = edges[edgeOffset + typeIndex]; |
| Expect.isTrue(0 <= type && type < _edgeTypes.length); |
| |
| final int nameOrIndex = edges[edgeOffset + nameOrIndexIndex]; |
| if (_edgeTypes[type] == "property") { |
| Expect.isTrue(0 <= nameOrIndex && nameOrIndex < _strings.length); |
| } else if (_edgeTypes[type] == "element" || |
| _edgeTypes[type] == "context") { |
| Expect.isTrue(nameOrIndex >= 0); |
| } |
| |
| final int toNode = edges[edgeOffset + toNodeIndex]; |
| checkNode(toNode); |
| nodeEdges[i] = _EdgeInfo(type, nameOrIndex, toNode); |
| } |
| _toEdges[nodeOffset] = nodeEdges; |
| } |
| |
| Expect.equals(edgeOffset, edges.length); |
| return edgeOffset ~/ _edgeFields.length; |
| } |
| |
| void checkNode(int offset) { |
| Expect.isTrue(offset >= 0 && |
| offset % _nodeFields.length == 0 && |
| offset ~/ _nodeFields.length < _nodes.length); |
| } |
| |
| void _calculateFromEdges() { |
| for (final MapEntry<int, List<_EdgeInfo>> entry in _toEdges.entries) { |
| final int fromNode = entry.key; |
| for (final _EdgeInfo edge in entry.value) { |
| final List<_EdgeInfo> backEdges = |
| _fromEdges.putIfAbsent(edge.nodeOffset, () => <_EdgeInfo>[]); |
| backEdges.add(_EdgeInfo(edge.type, edge.nameOrIndex, fromNode)); |
| } |
| } |
| } |
| |
| void _parseStrings(List strings) => strings.forEach(_strings.add); |
| |
| int get accountedBytes { |
| int sum = 0; |
| for (final _NodeInfo info in _nodes.values) { |
| sum += info.selfSize; |
| } |
| return sum; |
| } |
| |
| int get unknownCount { |
| final int unknownType = _nodeTypes.indexOf("Unknown"); |
| Expect.isTrue(unknownType >= 0); |
| |
| int count = 0; |
| for (final MapEntry<int, _NodeInfo> entry in _nodes.entries) { |
| if (entry.value.type == unknownType) { |
| ++count; |
| } |
| } |
| return count; |
| } |
| |
| bool get isEmpty => _nodes.isEmpty; |
| int get nodeCount => _nodes.length; |
| |
| Iterable<int> get nodes => _nodes.keys; |
| |
| Iterable<int> targetsOf(int source) { |
| return _toEdges[source].map((_EdgeInfo i) => i.nodeOffset); |
| } |
| |
| Iterable<int> sourcesOf(int source) { |
| return _fromEdges[source].map((_EdgeInfo i) => i.nodeOffset); |
| } |
| |
| int get root => 0; |
| |
| NodeInfo operator [](int node) { |
| _NodeInfo info = _nodes[node]; |
| final type = info.type != null ? _nodeTypes[info.type] : null; |
| final name = info.name != null ? _strings[info.name] : null; |
| return NodeInfo(type, name, info.id, info.selfSize); |
| } |
| |
| Iterable<EdgeInfo> targets(int node) sync* { |
| for (final _EdgeInfo info in _toEdges[node]) { |
| final String type = _edgeTypes[info.type]; |
| yield EdgeInfo(info.nodeOffset, type, |
| type == "property" ? _strings[info.nameOrIndex] : info.nameOrIndex); |
| } |
| } |
| } |