Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(199)

Side by Side Diff: runtime/observatory/lib/object_graph.dart

Issue 2759973004: Fix observatory tests broken by running dartfmt. Temporarily reverted formatting for evaluate_activ… (Closed)
Patch Set: Created 3 years, 9 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « runtime/observatory/lib/event.dart ('k') | runtime/observatory/lib/src/app/page.dart » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
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
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
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
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
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
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 }
OLDNEW
« no previous file with comments | « runtime/observatory/lib/event.dart ('k') | runtime/observatory/lib/src/app/page.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698