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