• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1// Copyright (C) 2019 The Android Open Source Project
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//      http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15import {CallsiteInfo, mergeCallsites} from './flamegraph_util';
16
17test('zeroCallsitesMerged', () => {
18  const callsites: CallsiteInfo[] = [
19    {
20      id: 1,
21      parentId: -1,
22      name: 'A',
23      depth: 0,
24      totalSize: 10,
25      selfSize: 0,
26      mapping: 'x',
27      merged: false,
28      highlighted: false,
29    },
30    {
31      id: 2,
32      parentId: -1,
33      name: 'B',
34      depth: 0,
35      totalSize: 8,
36      selfSize: 0,
37      mapping: 'x',
38      merged: false,
39      highlighted: false,
40    },
41    {
42      id: 3,
43      parentId: 1,
44      name: 'A3',
45      depth: 1,
46      totalSize: 4,
47      selfSize: 0,
48      mapping: 'x',
49      merged: false,
50      highlighted: false,
51    },
52    {
53      id: 4,
54      parentId: 2,
55      name: 'B4',
56      depth: 1,
57      totalSize: 4,
58      selfSize: 0,
59      mapping: 'x',
60      merged: false,
61      highlighted: false,
62    },
63  ];
64
65  const mergedCallsites = mergeCallsites(callsites, 5);
66
67  // Small callsites are not next ot each other, nothing should be changed.
68  expect(mergedCallsites).toEqual(callsites);
69});
70
71test('zeroCallsitesMerged2', () => {
72  const callsites: CallsiteInfo[] = [
73    {
74      id: 1,
75      parentId: -1,
76      name: 'A',
77      depth: 0,
78      totalSize: 10,
79      selfSize: 0,
80      mapping: 'x',
81      merged: false,
82      highlighted: false,
83    },
84    {
85      id: 2,
86      parentId: -1,
87      name: 'B',
88      depth: 0,
89      totalSize: 8,
90      selfSize: 0,
91      mapping: 'x',
92      merged: false,
93      highlighted: false,
94    },
95    {
96      id: 3,
97      parentId: 1,
98      name: 'A3',
99      depth: 1,
100      totalSize: 6,
101      selfSize: 0,
102      mapping: 'x',
103      merged: false,
104      highlighted: false,
105    },
106    {
107      id: 4,
108      parentId: 1,
109      name: 'A4',
110      depth: 1,
111      totalSize: 4,
112      selfSize: 0,
113      mapping: 'x',
114      merged: false,
115      highlighted: false,
116    },
117    {
118      id: 5,
119      parentId: 2,
120      name: 'B5',
121      depth: 1,
122      totalSize: 8,
123      selfSize: 0,
124      mapping: 'x',
125      merged: false,
126      highlighted: false,
127    },
128  ];
129
130  const mergedCallsites = mergeCallsites(callsites, 5);
131
132  // Small callsites are not next ot each other, nothing should be changed.
133  expect(mergedCallsites).toEqual(callsites);
134});
135
136test('twoCallsitesMerged', () => {
137  const callsites: CallsiteInfo[] = [
138    {
139      id: 1,
140      parentId: -1,
141      name: 'A',
142      depth: 0,
143      totalSize: 10,
144      selfSize: 0,
145      mapping: 'x',
146      merged: false,
147      highlighted: false,
148    },
149    {
150      id: 2,
151      parentId: 1,
152      name: 'A2',
153      depth: 1,
154      totalSize: 5,
155      selfSize: 0,
156      mapping: 'x',
157      merged: false,
158      highlighted: false,
159    },
160    {
161      id: 3,
162      parentId: 1,
163      name: 'A3',
164      depth: 1,
165      totalSize: 5,
166      selfSize: 0,
167      mapping: 'x',
168      merged: false,
169      highlighted: false,
170    },
171  ];
172
173  const mergedCallsites = mergeCallsites(callsites, 6);
174
175  expect(mergedCallsites).toEqual([
176    {
177      id: 1,
178      parentId: -1,
179      name: 'A',
180      depth: 0,
181      totalSize: 10,
182      selfSize: 0,
183      mapping: 'x',
184      merged: false,
185      highlighted: false,
186    },
187    {
188      id: 2,
189      parentId: 1,
190      name: '[merged]',
191      depth: 1,
192      totalSize: 10,
193      selfSize: 0,
194      mapping: 'x',
195      merged: true,
196      highlighted: false,
197    },
198  ]);
199});
200
201test('manyCallsitesMerged', () => {
202  const callsites: CallsiteInfo[] = [
203    {
204      id: 1,
205      parentId: -1,
206      name: 'A',
207      depth: 0,
208      totalSize: 10,
209      selfSize: 0,
210      mapping: 'x',
211      merged: false,
212      highlighted: false,
213    },
214    {
215      id: 2,
216      parentId: 1,
217      name: 'A2',
218      depth: 1,
219      totalSize: 5,
220      selfSize: 0,
221      mapping: 'x',
222      merged: false,
223      highlighted: false,
224    },
225    {
226      id: 3,
227      parentId: 1,
228      name: 'A3',
229      depth: 1,
230      totalSize: 3,
231      selfSize: 0,
232      mapping: 'x',
233      merged: false,
234      highlighted: false,
235    },
236    {
237      id: 4,
238      parentId: 1,
239      name: 'A4',
240      depth: 1,
241      totalSize: 1,
242      selfSize: 0,
243      mapping: 'x',
244      merged: false,
245      highlighted: false,
246    },
247    {
248      id: 5,
249      parentId: 1,
250      name: 'A5',
251      depth: 1,
252      totalSize: 1,
253      selfSize: 0,
254      mapping: 'x',
255      merged: false,
256      highlighted: false,
257    },
258    {
259      id: 6,
260      parentId: 3,
261      name: 'A36',
262      depth: 2,
263      totalSize: 1,
264      selfSize: 0,
265      mapping: 'x',
266      merged: false,
267      highlighted: false,
268    },
269    {
270      id: 7,
271      parentId: 4,
272      name: 'A47',
273      depth: 2,
274      totalSize: 1,
275      selfSize: 0,
276      mapping: 'x',
277      merged: false,
278      highlighted: false,
279    },
280    {
281      id: 8,
282      parentId: 5,
283      name: 'A58',
284      depth: 2,
285      totalSize: 1,
286      selfSize: 0,
287      mapping: 'x',
288      merged: false,
289      highlighted: false,
290    },
291  ];
292
293  const expectedMergedCallsites: CallsiteInfo[] = [
294    {
295      id: 1,
296      parentId: -1,
297      name: 'A',
298      depth: 0,
299      totalSize: 10,
300      selfSize: 0,
301      mapping: 'x',
302      merged: false,
303      highlighted: false,
304    },
305    {
306      id: 2,
307      parentId: 1,
308      name: 'A2',
309      depth: 1,
310      totalSize: 5,
311      selfSize: 0,
312      mapping: 'x',
313      merged: false,
314      highlighted: false,
315    },
316    {
317      id: 3,
318      parentId: 1,
319      name: '[merged]',
320      depth: 1,
321      totalSize: 5,
322      selfSize: 0,
323      mapping: 'x',
324      merged: true,
325      highlighted: false,
326    },
327    {
328      id: 6,
329      parentId: 3,
330      name: '[merged]',
331      depth: 2,
332      totalSize: 3,
333      selfSize: 0,
334      mapping: 'x',
335      merged: true,
336      highlighted: false,
337    },
338  ];
339
340  const mergedCallsites = mergeCallsites(callsites, 4);
341
342  // In this case, callsites A3, A4 and A5 should be merged since they are
343  // smaller then 4 and are on same depth with same parent. Callsites A36, A47
344  // and A58 should also be merged since their parents are merged.
345  expect(mergedCallsites).toEqual(expectedMergedCallsites);
346});
347
348test('manyCallsitesMergedWithoutChildren', () => {
349  const callsites: CallsiteInfo[] = [
350    {
351      id: 1,
352      parentId: -1,
353      name: 'A',
354      depth: 0,
355      totalSize: 5,
356      selfSize: 0,
357      mapping: 'x',
358      merged: false,
359      highlighted: false,
360    },
361    {
362      id: 2,
363      parentId: -1,
364      name: 'B',
365      depth: 0,
366      totalSize: 5,
367      selfSize: 0,
368      mapping: 'x',
369      merged: false,
370      highlighted: false,
371    },
372    {
373      id: 3,
374      parentId: 1,
375      name: 'A3',
376      depth: 1,
377      totalSize: 3,
378      selfSize: 0,
379      mapping: 'x',
380      merged: false,
381      highlighted: false,
382    },
383    {
384      id: 4,
385      parentId: 1,
386      name: 'A4',
387      depth: 1,
388      totalSize: 1,
389      selfSize: 0,
390      mapping: 'x',
391      merged: false,
392      highlighted: false,
393    },
394    {
395      id: 5,
396      parentId: 1,
397      name: 'A5',
398      depth: 1,
399      totalSize: 1,
400      selfSize: 0,
401      mapping: 'x',
402      merged: false,
403      highlighted: false,
404    },
405    {
406      id: 6,
407      parentId: 2,
408      name: 'B6',
409      depth: 1,
410      totalSize: 5,
411      selfSize: 0,
412      mapping: 'x',
413      merged: false,
414      highlighted: false,
415    },
416    {
417      id: 7,
418      parentId: 4,
419      name: 'A47',
420      depth: 2,
421      totalSize: 1,
422      selfSize: 0,
423      mapping: 'x',
424      merged: false,
425      highlighted: false,
426    },
427    {
428      id: 8,
429      parentId: 6,
430      name: 'B68',
431      depth: 2,
432      totalSize: 1,
433      selfSize: 0,
434      mapping: 'x',
435      merged: false,
436      highlighted: false,
437    },
438  ];
439
440  const expectedMergedCallsites: CallsiteInfo[] = [
441    {
442      id: 1,
443      parentId: -1,
444      name: 'A',
445      depth: 0,
446      totalSize: 5,
447      selfSize: 0,
448      mapping: 'x',
449      merged: false,
450      highlighted: false,
451    },
452    {
453      id: 2,
454      parentId: -1,
455      name: 'B',
456      depth: 0,
457      totalSize: 5,
458      selfSize: 0,
459      mapping: 'x',
460      merged: false,
461      highlighted: false,
462    },
463    {
464      id: 3,
465      parentId: 1,
466      name: '[merged]',
467      depth: 1,
468      totalSize: 5,
469      selfSize: 0,
470      mapping: 'x',
471      merged: true,
472      highlighted: false,
473    },
474    {
475      id: 6,
476      parentId: 2,
477      name: 'B6',
478      depth: 1,
479      totalSize: 5,
480      selfSize: 0,
481      mapping: 'x',
482      merged: false,
483      highlighted: false,
484    },
485    {
486      id: 7,
487      parentId: 3,
488      name: 'A47',
489      depth: 2,
490      totalSize: 1,
491      selfSize: 0,
492      mapping: 'x',
493      merged: false,
494      highlighted: false,
495    },
496    {
497      id: 8,
498      parentId: 6,
499      name: 'B68',
500      depth: 2,
501      totalSize: 1,
502      selfSize: 0,
503      mapping: 'x',
504      merged: false,
505      highlighted: false,
506    },
507  ];
508
509  const mergedCallsites = mergeCallsites(callsites, 4);
510
511  // In this case, callsites A3, A4 and A5 should be merged since they are
512  // smaller then 4 and are on same depth with same parent. Callsite A47
513  // should not be merged with B68 althought they are small because they don't
514  // have sam parent. A47 should now have parent A3 because A4 is merged.
515  expect(mergedCallsites).toEqual(expectedMergedCallsites);
516});
517
518test('smallCallsitesNotNextToEachOtherInArray', () => {
519  const callsites: CallsiteInfo[] = [
520    {
521      id: 1,
522      parentId: -1,
523      name: 'A',
524      depth: 0,
525      totalSize: 20,
526      selfSize: 0,
527      mapping: 'x',
528      merged: false,
529      highlighted: false,
530    },
531    {
532      id: 2,
533      parentId: 1,
534      name: 'A2',
535      depth: 1,
536      totalSize: 8,
537      selfSize: 0,
538      mapping: 'x',
539      merged: false,
540      highlighted: false,
541    },
542    {
543      id: 3,
544      parentId: 1,
545      name: 'A3',
546      depth: 1,
547      totalSize: 1,
548      selfSize: 0,
549      mapping: 'x',
550      merged: false,
551      highlighted: false,
552    },
553    {
554      id: 4,
555      parentId: 1,
556      name: 'A4',
557      depth: 1,
558      totalSize: 8,
559      selfSize: 0,
560      mapping: 'x',
561      merged: false,
562      highlighted: false,
563    },
564    {
565      id: 5,
566      parentId: 1,
567      name: 'A5',
568      depth: 1,
569      totalSize: 3,
570      selfSize: 0,
571      mapping: 'x',
572      merged: false,
573      highlighted: false,
574    },
575  ];
576
577  const expectedMergedCallsites: CallsiteInfo[] = [
578    {
579      id: 1,
580      parentId: -1,
581      name: 'A',
582      depth: 0,
583      totalSize: 20,
584      selfSize: 0,
585      mapping: 'x',
586      merged: false,
587      highlighted: false,
588    },
589    {
590      id: 2,
591      parentId: 1,
592      name: 'A2',
593      depth: 1,
594      totalSize: 8,
595      selfSize: 0,
596      mapping: 'x',
597      merged: false,
598      highlighted: false,
599    },
600    {
601      id: 3,
602      parentId: 1,
603      name: '[merged]',
604      depth: 1,
605      totalSize: 4,
606      selfSize: 0,
607      mapping: 'x',
608      merged: true,
609      highlighted: false,
610    },
611    {
612      id: 4,
613      parentId: 1,
614      name: 'A4',
615      depth: 1,
616      totalSize: 8,
617      selfSize: 0,
618      mapping: 'x',
619      merged: false,
620      highlighted: false,
621    },
622  ];
623
624  const mergedCallsites = mergeCallsites(callsites, 4);
625
626  // In this case, callsites A3, A4 and A5 should be merged since they are
627  // smaller then 4 and are on same depth with same parent. Callsite A47
628  // should not be merged with B68 althought they are small because they don't
629  // have sam parent. A47 should now have parent A3 because A4 is merged.
630  expect(mergedCallsites).toEqual(expectedMergedCallsites);
631});
632
633test('smallCallsitesNotMerged', () => {
634  const callsites: CallsiteInfo[] = [
635    {
636      id: 1,
637      parentId: -1,
638      name: 'A',
639      depth: 0,
640      totalSize: 10,
641      selfSize: 0,
642      mapping: 'x',
643      merged: false,
644      highlighted: false,
645    },
646    {
647      id: 2,
648      parentId: 1,
649      name: 'A2',
650      depth: 1,
651      totalSize: 2,
652      selfSize: 0,
653      mapping: 'x',
654      merged: false,
655      highlighted: false,
656    },
657    {
658      id: 3,
659      parentId: 1,
660      name: 'A3',
661      depth: 1,
662      totalSize: 2,
663      selfSize: 0,
664      mapping: 'x',
665      merged: false,
666      highlighted: false,
667    },
668  ];
669
670  const mergedCallsites = mergeCallsites(callsites, 1);
671
672  expect(mergedCallsites).toEqual(callsites);
673});
674
675test('mergingRootCallsites', () => {
676  const callsites: CallsiteInfo[] = [
677    {
678      id: 1,
679      parentId: -1,
680      name: 'A',
681      depth: 0,
682      totalSize: 10,
683      selfSize: 0,
684      mapping: 'x',
685      merged: false,
686      highlighted: false,
687    },
688    {
689      id: 2,
690      parentId: -1,
691      name: 'B',
692      depth: 0,
693      totalSize: 2,
694      selfSize: 0,
695      mapping: 'x',
696      merged: false,
697      highlighted: false,
698    },
699  ];
700
701  const mergedCallsites = mergeCallsites(callsites, 20);
702
703  expect(mergedCallsites).toEqual([
704    {
705      id: 1,
706      parentId: -1,
707      name: '[merged]',
708      depth: 0,
709      totalSize: 12,
710      selfSize: 0,
711      mapping: 'x',
712      merged: true,
713      highlighted: false,
714    },
715  ]);
716});
717
718test('largerFlamegraph', () => {
719  const data: CallsiteInfo[] = [
720    {
721      id: 1,
722      parentId: -1,
723      name: 'A',
724      depth: 0,
725      totalSize: 60,
726      selfSize: 0,
727      mapping: 'x',
728      merged: false,
729      highlighted: false,
730    },
731    {
732      id: 2,
733      parentId: -1,
734      name: 'B',
735      depth: 0,
736      totalSize: 40,
737      selfSize: 0,
738      mapping: 'x',
739      merged: false,
740      highlighted: false,
741    },
742    {
743      id: 3,
744      parentId: 1,
745      name: 'A3',
746      depth: 1,
747      totalSize: 25,
748      selfSize: 0,
749      mapping: 'x',
750      merged: false,
751      highlighted: false,
752    },
753    {
754      id: 4,
755      parentId: 1,
756      name: 'A4',
757      depth: 1,
758      totalSize: 15,
759      selfSize: 0,
760      mapping: 'x',
761      merged: false,
762      highlighted: false,
763    },
764    {
765      id: 5,
766      parentId: 1,
767      name: 'A5',
768      depth: 1,
769      totalSize: 10,
770      selfSize: 0,
771      mapping: 'x',
772      merged: false,
773      highlighted: false,
774    },
775    {
776      id: 6,
777      parentId: 1,
778      name: 'A6',
779      depth: 1,
780      totalSize: 10,
781      selfSize: 0,
782      mapping: 'x',
783      merged: false,
784      highlighted: false,
785    },
786    {
787      id: 7,
788      parentId: 2,
789      name: 'B7',
790      depth: 1,
791      totalSize: 30,
792      selfSize: 0,
793      mapping: 'x',
794      merged: false,
795      highlighted: false,
796    },
797    {
798      id: 8,
799      parentId: 2,
800      name: 'B8',
801      depth: 1,
802      totalSize: 10,
803      selfSize: 0,
804      mapping: 'x',
805      merged: false,
806      highlighted: false,
807    },
808    {
809      id: 9,
810      parentId: 3,
811      name: 'A39',
812      depth: 2,
813      totalSize: 20,
814      selfSize: 0,
815      mapping: 'x',
816      merged: false,
817      highlighted: false,
818    },
819    {
820      id: 10,
821      parentId: 4,
822      name: 'A410',
823      depth: 2,
824      totalSize: 10,
825      selfSize: 0,
826      mapping: 'x',
827      merged: false,
828      highlighted: false,
829    },
830    {
831      id: 11,
832      parentId: 4,
833      name: 'A411',
834      depth: 2,
835      totalSize: 3,
836      selfSize: 0,
837      mapping: 'x',
838      merged: false,
839      highlighted: false,
840    },
841    {
842      id: 12,
843      parentId: 4,
844      name: 'A412',
845      depth: 2,
846      totalSize: 2,
847      selfSize: 0,
848      mapping: 'x',
849      merged: false,
850      highlighted: false,
851    },
852    {
853      id: 13,
854      parentId: 5,
855      name: 'A513',
856      depth: 2,
857      totalSize: 5,
858      selfSize: 0,
859      mapping: 'x',
860      merged: false,
861      highlighted: false,
862    },
863    {
864      id: 14,
865      parentId: 5,
866      name: 'A514',
867      depth: 2,
868      totalSize: 5,
869      selfSize: 0,
870      mapping: 'x',
871      merged: false,
872      highlighted: false,
873    },
874    {
875      id: 15,
876      parentId: 7,
877      name: 'A715',
878      depth: 2,
879      totalSize: 10,
880      selfSize: 0,
881      mapping: 'x',
882      merged: false,
883      highlighted: false,
884    },
885    {
886      id: 16,
887      parentId: 7,
888      name: 'A716',
889      depth: 2,
890      totalSize: 5,
891      selfSize: 0,
892      mapping: 'x',
893      merged: false,
894      highlighted: false,
895    },
896    {
897      id: 17,
898      parentId: 7,
899      name: 'A717',
900      depth: 2,
901      totalSize: 5,
902      selfSize: 0,
903      mapping: 'x',
904      merged: false,
905      highlighted: false,
906    },
907    {
908      id: 18,
909      parentId: 7,
910      name: 'A718',
911      depth: 2,
912      totalSize: 5,
913      selfSize: 0,
914      mapping: 'x',
915      merged: false,
916      highlighted: false,
917    },
918    {
919      id: 19,
920      parentId: 9,
921      name: 'A919',
922      depth: 3,
923      totalSize: 10,
924      selfSize: 0,
925      mapping: 'x',
926      merged: false,
927      highlighted: false,
928    },
929    {
930      id: 20,
931      parentId: 17,
932      name: 'A1720',
933      depth: 3,
934      totalSize: 2,
935      selfSize: 0,
936      mapping: 'x',
937      merged: false,
938      highlighted: false,
939    },
940  ];
941
942  const expectedData: CallsiteInfo[] = [
943    {
944      id: 1,
945      parentId: -1,
946      name: 'A',
947      depth: 0,
948      totalSize: 60,
949      selfSize: 0,
950      mapping: 'x',
951      merged: false,
952      highlighted: false,
953    },
954    {
955      id: 2,
956      parentId: -1,
957      name: 'B',
958      depth: 0,
959      totalSize: 40,
960      selfSize: 0,
961      mapping: 'x',
962      merged: false,
963      highlighted: false,
964    },
965    {
966      id: 3,
967      parentId: 1,
968      name: 'A3',
969      depth: 1,
970      totalSize: 25,
971      selfSize: 0,
972      mapping: 'x',
973      merged: false,
974      highlighted: false,
975    },
976    {
977      id: 4,
978      parentId: 1,
979      name: '[merged]',
980      depth: 1,
981      totalSize: 35,
982      selfSize: 0,
983      mapping: 'x',
984      merged: true,
985      highlighted: false,
986    },
987    {
988      id: 7,
989      parentId: 2,
990      name: 'B7',
991      depth: 1,
992      totalSize: 30,
993      selfSize: 0,
994      mapping: 'x',
995      merged: false,
996      highlighted: false,
997    },
998    {
999      id: 8,
1000      parentId: 2,
1001      name: 'B8',
1002      depth: 1,
1003      totalSize: 10,
1004      selfSize: 0,
1005      mapping: 'x',
1006      merged: false,
1007      highlighted: false,
1008    },
1009    {
1010      id: 9,
1011      parentId: 3,
1012      name: 'A39',
1013      depth: 2,
1014      totalSize: 20,
1015      selfSize: 0,
1016      mapping: 'x',
1017      merged: false,
1018      highlighted: false,
1019    },
1020    {
1021      id: 10,
1022      parentId: 4,
1023      name: '[merged]',
1024      depth: 2,
1025      totalSize: 25,
1026      selfSize: 0,
1027      mapping: 'x',
1028      merged: true,
1029      highlighted: false,
1030    },
1031    {
1032      id: 15,
1033      parentId: 7,
1034      name: '[merged]',
1035      depth: 2,
1036      totalSize: 25,
1037      selfSize: 0,
1038      mapping: 'x',
1039      merged: true,
1040      highlighted: false,
1041    },
1042    {
1043      id: 19,
1044      parentId: 9,
1045      name: 'A919',
1046      depth: 3,
1047      totalSize: 10,
1048      selfSize: 0,
1049      mapping: 'x',
1050      merged: false,
1051      highlighted: false,
1052    },
1053    {
1054      id: 20,
1055      parentId: 15,
1056      name: 'A1720',
1057      depth: 3,
1058      totalSize: 2,
1059      selfSize: 0,
1060      mapping: 'x',
1061      merged: false,
1062      highlighted: false,
1063    },
1064  ];
1065
1066  // In this case, on depth 1, callsites A4, A5 and A6 should be merged and
1067  // initiate merging of their children A410, A411, A412, A513, A514. On depth2,
1068  // callsites A715, A716, A717 and A718 should be merged.
1069  const actualData = mergeCallsites(data, 16);
1070
1071  expect(actualData).toEqual(expectedData);
1072});
1073