OLD | NEW |
1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 library object_graph; | 5 library object_graph; |
6 | 6 |
7 import 'dart:async'; | 7 import 'dart:async'; |
8 import 'dart:collection'; | 8 import 'dart:collection'; |
9 import 'dart:typed_data'; | 9 import 'dart:typed_data'; |
10 | 10 |
(...skipping 296 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
307 | 307 |
308 bool operator ==(other) => _id == other._id && _graph == other._graph; | 308 bool operator ==(other) => _id == other._id && _graph == other._graph; |
309 int get hashCode => _id; | 309 int get hashCode => _id; |
310 | 310 |
311 int get vmCid => _graph._cids[_id]; | 311 int get vmCid => _graph._cids[_id]; |
312 | 312 |
313 int get shallowSize { | 313 int get shallowSize { |
314 var cids = _graph._cids; | 314 var cids = _graph._cids; |
315 var size = 0; | 315 var size = 0; |
316 var sibling = _id; | 316 var sibling = _id; |
317 while (sibling != SENTINEL && cids[sibling] == cids[_id]) { | 317 while (sibling != SENTINEL && |
| 318 cids[sibling] == cids[_id]) { |
318 size += _graph._shallowSizes[sibling]; | 319 size += _graph._shallowSizes[sibling]; |
319 sibling = _graph._mergedDomNext[sibling]; | 320 sibling = _graph._mergedDomNext[sibling]; |
320 } | 321 } |
321 return size; | 322 return size; |
322 } | 323 } |
323 | |
324 int get retainedSize { | 324 int get retainedSize { |
325 var cids = _graph._cids; | 325 var cids = _graph._cids; |
326 var size = 0; | 326 var size = 0; |
327 var sibling = _id; | 327 var sibling = _id; |
328 while (sibling != SENTINEL && cids[sibling] == cids[_id]) { | 328 while (sibling != SENTINEL && |
| 329 cids[sibling] == cids[_id]) { |
329 size += _graph._retainedSizes[sibling]; | 330 size += _graph._retainedSizes[sibling]; |
330 sibling = _graph._mergedDomNext[sibling]; | 331 sibling = _graph._mergedDomNext[sibling]; |
331 } | 332 } |
332 return size; | 333 return size; |
333 } | 334 } |
334 | |
335 int get instanceCount { | 335 int get instanceCount { |
336 var cids = _graph._cids; | 336 var cids = _graph._cids; |
337 var count = 0; | 337 var count = 0; |
338 var sibling = _id; | 338 var sibling = _id; |
339 while (sibling != SENTINEL && cids[sibling] == cids[_id]) { | 339 while (sibling != SENTINEL && |
| 340 cids[sibling] == cids[_id]) { |
340 count++; | 341 count++; |
341 sibling = _graph._mergedDomNext[sibling]; | 342 sibling = _graph._mergedDomNext[sibling]; |
342 } | 343 } |
343 return count; | 344 return count; |
344 } | 345 } |
345 | 346 |
346 List<MergedObjectVertex> dominatorTreeChildren() { | 347 List<MergedObjectVertex> dominatorTreeChildren() { |
347 var next = _graph._mergedDomNext; | 348 var next = _graph._mergedDomNext; |
348 var cids = _graph._cids; | 349 var cids = _graph._cids; |
349 | 350 |
350 var domChildren = []; | 351 var domChildren = []; |
351 var prev = SENTINEL; | 352 var prev = SENTINEL; |
352 var child = _graph._mergedDomHead[_id]; | 353 var child = _graph._mergedDomHead[_id]; |
353 // Walk the list of children and look for the representative objects, i.e. | 354 // Walk the list of children and look for the representative objects, i.e. |
354 // the first sibling of each cid. | 355 // the first sibling of each cid. |
355 while (child != SENTINEL) { | 356 while (child != SENTINEL) { |
356 if (prev == SENTINEL || cids[prev] != cids[child]) { | 357 if (prev == SENTINEL || |
| 358 cids[prev] != cids[child]) { |
357 domChildren.add(new MergedObjectVertex._(child, _graph)); | 359 domChildren.add(new MergedObjectVertex._(child, _graph)); |
358 } | 360 } |
359 prev = child; | 361 prev = child; |
360 child = next[child]; | 362 child = next[child]; |
361 } | 363 } |
362 | 364 |
363 return domChildren; | 365 return domChildren; |
364 } | 366 } |
365 } | 367 } |
366 | 368 |
(...skipping 126 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
493 controller.add(["Processed", 100.0]); | 495 controller.add(["Processed", 100.0]); |
494 controller.close(); | 496 controller.close(); |
495 }()); | 497 }()); |
496 return controller.stream; | 498 return controller.stream; |
497 } | 499 } |
498 | 500 |
499 List<ByteData> _chunks; | 501 List<ByteData> _chunks; |
500 | 502 |
501 int _kObjectAlignment; | 503 int _kObjectAlignment; |
502 int _kStackCid; | 504 int _kStackCid; |
503 int _N; // Objects in the snapshot. | 505 int _N; // Objects in the snapshot. |
504 int _Nconnected; // Objects reachable from root. | 506 int _Nconnected; // Objects reachable from root. |
505 int _E; // References in the snapshot. | 507 int _E; // References in the snapshot. |
506 int _size; | 508 int _size; |
507 | 509 |
508 // Indexed by node id, with id 0 representing invalid/uninitialized. | 510 // Indexed by node id, with id 0 representing invalid/uninitialized. |
509 // From snapshot. | 511 // From snapshot. |
510 Uint16List _cids; | 512 Uint16List _cids; |
511 Uint32List _shallowSizes; | 513 Uint32List _shallowSizes; |
512 Uint32List _firstSuccs; | 514 Uint32List _firstSuccs; |
513 Uint32List _succs; | 515 Uint32List _succs; |
514 Uint32List _addressesLow; // No Uint64List in Javascript. | 516 Uint32List _addressesLow; // No Uint64List in Javascript. |
515 Uint32List _addressesHigh; | 517 Uint32List _addressesHigh; |
(...skipping 169 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
685 return true; | 687 return true; |
686 }); | 688 }); |
687 | 689 |
688 if (dfsNumber != N) { | 690 if (dfsNumber != N) { |
689 // Remove successors of unconnected nodes | 691 // Remove successors of unconnected nodes |
690 for (var i = ROOT + 1; i <= N; i++) { | 692 for (var i = ROOT + 1; i <= N; i++) { |
691 if (parent[i] == SENTINEL) { | 693 if (parent[i] == SENTINEL) { |
692 var startSuccIndex = firstSuccs[i]; | 694 var startSuccIndex = firstSuccs[i]; |
693 var limitSuccIndex = firstSuccs[i + 1]; | 695 var limitSuccIndex = firstSuccs[i + 1]; |
694 for (var succIndex = startSuccIndex; | 696 for (var succIndex = startSuccIndex; |
695 succIndex < limitSuccIndex; | 697 succIndex < limitSuccIndex; |
696 succIndex++) { | 698 succIndex++) { |
697 succs[succIndex] = SENTINEL; | 699 succs[succIndex] = SENTINEL; |
698 } | 700 } |
699 } | 701 } |
700 } | 702 } |
701 } | 703 } |
702 | 704 |
703 _Nconnected = dfsNumber; | 705 _Nconnected = dfsNumber; |
704 _vertex = vertex; | 706 _vertex = vertex; |
705 _semi = semi; | 707 _semi = semi; |
706 _parent = parent; | 708 _parent = parent; |
(...skipping 226 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
933 var retainedSizes = new Uint32List.fromList(shallowSizes); | 935 var retainedSizes = new Uint32List.fromList(shallowSizes); |
934 | 936 |
935 // In post order (bottom up), add retained size to dominator's retained | 937 // In post order (bottom up), add retained size to dominator's retained |
936 // size, skipping root. | 938 // size, skipping root. |
937 for (var i = Nconnected; i > 1; i--) { | 939 for (var i = Nconnected; i > 1; i--) { |
938 var v = vertex[i]; | 940 var v = vertex[i]; |
939 assert(v != ROOT); | 941 assert(v != ROOT); |
940 retainedSizes[doms[v]] += retainedSizes[v]; | 942 retainedSizes[doms[v]] += retainedSizes[v]; |
941 } | 943 } |
942 | 944 |
943 assert(retainedSizes[ROOT] == size); // Root retains everything. | 945 assert(retainedSizes[ROOT] == size); // Root retains everything. |
944 | 946 |
945 _retainedSizes = retainedSizes; | 947 _retainedSizes = retainedSizes; |
946 _size = size; | 948 _size = size; |
947 } | 949 } |
948 | 950 |
949 // Build linked lists of the children for each node in the dominator tree. | 951 // Build linked lists of the children for each node in the dominator tree. |
950 void _linkDominatorChildren() { | 952 void _linkDominatorChildren() { |
951 var N = _N; | 953 var N = _N; |
952 var doms = _doms; | 954 var doms = _doms; |
953 var head = new Uint32List(N + 1); | 955 var head = new Uint32List(N + 1); |
954 var next = new Uint32List(N + 1); | 956 var next = new Uint32List(N + 1); |
955 | 957 |
956 for (var child = ROOT; child <= N; child++) { | 958 for (var child = ROOT; child <= N; child++) { |
957 var parent = doms[child]; | 959 var parent = doms[child]; |
958 next[child] = head[parent]; | 960 next[child] = head[parent]; |
959 head[parent] = child; | 961 head[parent] = child; |
960 } | 962 } |
961 | 963 |
962 _mergedDomHead = head; | 964 _mergedDomHead = head; |
963 _mergedDomNext = next; | 965 _mergedDomNext = next; |
964 } | 966 } |
965 | 967 |
966 // Merge the given lists according to the given key in ascending order. | 968 // Merge the given lists according to the given key in ascending order. |
967 // Returns the head of the merged list. | 969 // Returns the head of the merged list. |
968 static int _mergeSorted( | 970 static int _mergeSorted(int head1, int head2, |
969 int head1, int head2, Uint32List next, Uint16List key) { | 971 Uint32List next, Uint16List key) { |
970 var head = head1; | 972 var head = head1; |
971 var beforeInsert = SENTINEL; | 973 var beforeInsert = SENTINEL; |
972 var afterInsert = head1; | 974 var afterInsert = head1; |
973 var startInsert = head2; | 975 var startInsert = head2; |
974 | 976 |
975 while (startInsert != SENTINEL) { | 977 while (startInsert != SENTINEL) { |
976 while ( | 978 while ((afterInsert != SENTINEL) && |
977 (afterInsert != SENTINEL) && (key[afterInsert] <= key[startInsert])) { | 979 (key[afterInsert] <= key[startInsert])) { |
978 beforeInsert = afterInsert; | 980 beforeInsert = afterInsert; |
979 afterInsert = next[beforeInsert]; | 981 afterInsert = next[beforeInsert]; |
980 } | 982 } |
981 | 983 |
982 var endInsert = startInsert; | 984 var endInsert = startInsert; |
983 var peek = next[endInsert]; | 985 var peek = next[endInsert]; |
984 | 986 |
985 while ((peek != SENTINEL) && (key[peek] < key[afterInsert])) { | 987 while ((peek != SENTINEL) && (key[peek] < key[afterInsert])) { |
986 endInsert = peek; | 988 endInsert = peek; |
987 peek = next[endInsert]; | 989 peek = next[endInsert]; |
(...skipping 22 matching lines...) Expand all Loading... |
1010 | 1012 |
1011 // Returns the new head of the sorted list. | 1013 // Returns the new head of the sorted list. |
1012 int sort(int head) { | 1014 int sort(int head) { |
1013 if (head == SENTINEL) return SENTINEL; | 1015 if (head == SENTINEL) return SENTINEL; |
1014 if (next[head] == SENTINEL) return head; | 1016 if (next[head] == SENTINEL) return head; |
1015 | 1017 |
1016 // Find the middle of the list. | 1018 // Find the middle of the list. |
1017 int head1 = head; | 1019 int head1 = head; |
1018 int slow = head; | 1020 int slow = head; |
1019 int fast = head; | 1021 int fast = head; |
1020 while (next[fast] != SENTINEL && next[next[fast]] != SENTINEL) { | 1022 while (next[fast] != SENTINEL && |
| 1023 next[next[fast]] != SENTINEL) { |
1021 slow = next[slow]; | 1024 slow = next[slow]; |
1022 fast = next[next[fast]]; | 1025 fast = next[next[fast]]; |
1023 } | 1026 } |
1024 | 1027 |
1025 // Split the list in half. | 1028 // Split the list in half. |
1026 int head2 = next[slow]; | 1029 int head2 = next[slow]; |
1027 next[slow] = SENTINEL; | 1030 next[slow] = SENTINEL; |
1028 | 1031 |
1029 // Recursively sort the sublists and merge. | 1032 // Recursively sort the sublists and merge. |
1030 assert(head1 != head2); | 1033 assert(head1 != head2); |
(...skipping 17 matching lines...) Expand all Loading... |
1048 var workStackTop = 0; | 1051 var workStackTop = 0; |
1049 | 1052 |
1050 mergeChildrenAndSort(var parent1, var end) { | 1053 mergeChildrenAndSort(var parent1, var end) { |
1051 assert(parent1 != SENTINEL); | 1054 assert(parent1 != SENTINEL); |
1052 if (next[parent1] == end) return; | 1055 if (next[parent1] == end) return; |
1053 | 1056 |
1054 // Find the middle of the list. | 1057 // Find the middle of the list. |
1055 int cid = cids[parent1]; | 1058 int cid = cids[parent1]; |
1056 int slow = parent1; | 1059 int slow = parent1; |
1057 int fast = parent1; | 1060 int fast = parent1; |
1058 while (next[fast] != end && next[next[fast]] != end) { | 1061 while (next[fast] != end && |
| 1062 next[next[fast]] != end) { |
1059 slow = next[slow]; | 1063 slow = next[slow]; |
1060 fast = next[next[fast]]; | 1064 fast = next[next[fast]]; |
1061 } | 1065 } |
1062 | 1066 |
1063 int parent2 = next[slow]; | 1067 int parent2 = next[slow]; |
1064 | 1068 |
1065 assert(parent2 != SENTINEL); | 1069 assert(parent2 != SENTINEL); |
1066 assert(parent1 != parent2); | 1070 assert(parent1 != parent2); |
1067 assert(cids[parent1] == cids[parent2]); | 1071 assert(cids[parent1] == cids[parent2]); |
1068 | 1072 |
(...skipping 15 matching lines...) Expand all Loading... |
1084 var parent = workStack[--workStackTop]; | 1088 var parent = workStack[--workStackTop]; |
1085 | 1089 |
1086 var prev = SENTINEL; | 1090 var prev = SENTINEL; |
1087 var child = head[parent]; | 1091 var child = head[parent]; |
1088 while (child != SENTINEL) { | 1092 while (child != SENTINEL) { |
1089 // Push child. | 1093 // Push child. |
1090 workStack[workStackTop++] = child; | 1094 workStack[workStackTop++] = child; |
1091 | 1095 |
1092 // Find next sibling with a different cid. | 1096 // Find next sibling with a different cid. |
1093 var after = child; | 1097 var after = child; |
1094 while (after != SENTINEL && cids[after] == cids[child]) { | 1098 while (after != SENTINEL && |
| 1099 cids[after] == cids[child]) { |
1095 after = next[after]; | 1100 after = next[after]; |
1096 } | 1101 } |
1097 | 1102 |
1098 // From all the siblings between child and after, take their children, | 1103 // From all the siblings between child and after, take their children, |
1099 // merge them and given to child. | 1104 // merge them and given to child. |
1100 mergeChildrenAndSort(child, after); | 1105 mergeChildrenAndSort(child, after); |
1101 | 1106 |
1102 child = after; | 1107 child = after; |
1103 } | 1108 } |
1104 } | 1109 } |
1105 } | 1110 } |
1106 } | 1111 } |
OLD | NEW |