| 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 |