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