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