1// Copyright (C) 2018 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 {searchSegment} from '../base/binary_search';
16import {cropText} from '../common/canvas_utils';
17
18import {CallsiteInfo} from '../common/state';
19
20interface Node {
21  width: number;
22  x: number;
23  nextXForChildren: number;
24  size: number;
25}
26
27interface CallsiteInfoWidth {
28  callsite: CallsiteInfo;
29  width: number;
30}
31
32// Height of one 'row' on the flame chart including 1px of whitespace
33// below the box.
34const NODE_HEIGHT = 18;
35
36export const HEAP_PROFILE_HOVERED_COLOR = 'hsl(224, 45%, 55%)';
37
38export function findRootSize(data: CallsiteInfo[]) {
39  let totalSize = 0;
40  let i = 0;
41  while (i < data.length && data[i].depth === 0) {
42    totalSize += data[i].totalSize;
43    i++;
44  }
45  return totalSize;
46}
47
48export interface NodeRendering {
49  totalSize?: string;
50  selfSize?: string;
51}
52
53export class Flamegraph {
54  private nodeRendering: NodeRendering = {};
55  private flamegraphData: CallsiteInfo[];
56  private highlightSomeNodes = false;
57  private maxDepth = -1;
58  private totalSize = -1;
59  // Initialised on first draw() call
60  private labelCharWidth = 0;
61  private labelFontStyle = '12px Roboto Mono';
62  private rolloverFontStyle = '12px Roboto Condensed';
63  // Key for the map is depth followed by x coordinate - `depth;x`
64  private graphData: Map<string, CallsiteInfoWidth> = new Map();
65  private xStartsPerDepth: Map<number, number[]> = new Map();
66
67  private hoveredX = -1;
68  private hoveredY = -1;
69  private hoveredCallsite?: CallsiteInfo;
70  private clickedCallsite?: CallsiteInfo;
71
72  private startingY = 0;
73
74  constructor(flamegraphData: CallsiteInfo[]) {
75    this.flamegraphData = flamegraphData;
76    this.findMaxDepth();
77  }
78
79  private findMaxDepth() {
80    this.maxDepth = Math.max(...this.flamegraphData.map(value => value.depth));
81  }
82
83  // Instead of highlighting the interesting nodes, we actually want to
84  // de-emphasize the non-highlighted nodes. Returns true if there
85  // are any highlighted nodes in the flamegraph.
86  private highlightingExists() {
87    this.highlightSomeNodes = this.flamegraphData.some((e) => e.highlighted);
88  }
89
90  generateColor(name: string, isGreyedOut = false, highlighted: boolean):
91      string {
92    if (isGreyedOut) {
93      return '#d9d9d9';
94    }
95    if (name === 'unknown' || name === 'root') {
96      return '#c0c0c0';
97    }
98    let x = 0;
99    for (let i = 0; i < name.length; i += 1) {
100      x += name.charCodeAt(i) % 64;
101    }
102    x = x % 360;
103    let l = '76';
104    // Make non-highlighted node lighter.
105    if (this.highlightSomeNodes && !highlighted) {
106      l = '90';
107    }
108    return `hsl(${x}deg, 45%, ${l}%)`;
109  }
110
111  /**
112   * Caller will have to call draw method after updating data to have updated
113   * graph.
114   */
115  updateDataIfChanged(
116      nodeRendering: NodeRendering, flamegraphData: CallsiteInfo[],
117      clickedCallsite?: CallsiteInfo) {
118    this.nodeRendering = nodeRendering;
119    this.clickedCallsite = clickedCallsite;
120    if (this.flamegraphData === flamegraphData) {
121      return;
122    }
123    this.flamegraphData = flamegraphData;
124    this.clickedCallsite = clickedCallsite;
125    this.findMaxDepth();
126    this.highlightingExists();
127    // Finding total size of roots.
128    this.totalSize = findRootSize(flamegraphData);
129  }
130
131  draw(
132      ctx: CanvasRenderingContext2D, width: number, height: number, x = 0,
133      y = 0, unit = 'B') {
134
135    if (this.flamegraphData === undefined) {
136      return;
137    }
138
139    ctx.font = this.labelFontStyle;
140    ctx.textBaseline = 'middle';
141    if (this.labelCharWidth === 0) {
142      this.labelCharWidth = ctx.measureText('_').width;
143    }
144
145    this.startingY = y;
146
147    // For each node, we use this map to get information about it's parent
148    // (total size of it, width and where it starts in graph) so we can
149    // calculate it's own position in graph.
150    const nodesMap = new Map<number, Node>();
151    let currentY = y;
152    nodesMap.set(-1, {width, nextXForChildren: x, size: this.totalSize, x});
153
154    // Initialize data needed for click/hover behavior.
155    this.graphData = new Map();
156    this.xStartsPerDepth = new Map();
157
158    // Draw root node.
159    ctx.fillStyle = this.generateColor('root', false, false);
160    ctx.fillRect(x, currentY, width, NODE_HEIGHT - 1);
161    const text = cropText(
162        `root: ${
163            this.displaySize(
164                this.totalSize, unit, unit === 'B' ? 1024 : 1000)}`,
165        this.labelCharWidth,
166        width - 2);
167    ctx.fillStyle = 'black';
168    ctx.fillText(text, x + 5, currentY + (NODE_HEIGHT - 1) / 2);
169    currentY += NODE_HEIGHT;
170
171    // Set style for borders.
172    ctx.strokeStyle = 'white';
173    ctx.lineWidth = 0.5;
174
175    for (let i = 0; i < this.flamegraphData.length; i++) {
176      if (currentY > height) {
177        break;
178      }
179      const value = this.flamegraphData[i];
180      const parentNode = nodesMap.get(value.parentId);
181      if (parentNode === undefined) {
182        continue;
183      }
184
185      const isClicked = this.clickedCallsite !== undefined;
186      const isFullWidth =
187          isClicked && value.depth <= this.clickedCallsite!.depth;
188      const isGreyedOut =
189          isClicked && value.depth < this.clickedCallsite!.depth;
190
191      const parent = value.parentId;
192      const parentSize = parent === -1 ? this.totalSize : parentNode.size;
193      // Calculate node's width based on its proportion in parent.
194      const width =
195          (isFullWidth ? 1 : value.totalSize / parentSize) * parentNode.width;
196
197      const currentX = parentNode.nextXForChildren;
198      currentY = y + NODE_HEIGHT * (value.depth + 1);
199
200      // Draw node.
201      const name = this.getCallsiteName(value);
202      ctx.fillStyle = this.generateColor(name, isGreyedOut, value.highlighted);
203      ctx.fillRect(currentX, currentY, width, NODE_HEIGHT - 1);
204
205      // Set current node's data in map for children to use.
206      nodesMap.set(value.id, {
207        width,
208        nextXForChildren: currentX,
209        size: value.totalSize,
210        x: currentX
211      });
212      // Update next x coordinate in parent.
213      nodesMap.set(value.parentId, {
214        width: parentNode.width,
215        nextXForChildren: currentX + width,
216        size: parentNode.size,
217        x: parentNode.x
218      });
219
220      // Draw name.
221      const labelPaddingPx = 5;
222      const maxLabelWidth = width - labelPaddingPx * 2;
223      let text = cropText(name, this.labelCharWidth, maxLabelWidth);
224      // If cropped text and the original text are within 20% we keep the
225      // original text and just squish it a bit.
226      if (text.length * 1.2 > name.length) {
227        text = name;
228      }
229      ctx.fillStyle = 'black';
230      ctx.fillText(
231          text,
232          currentX + labelPaddingPx,
233          currentY + (NODE_HEIGHT - 1) / 2,
234          maxLabelWidth);
235
236      // Draw border on the right of node.
237      ctx.beginPath();
238      ctx.moveTo(currentX + width, currentY);
239      ctx.lineTo(currentX + width, currentY + NODE_HEIGHT);
240      ctx.stroke();
241
242      // Add this node for recognizing in click/hover.
243      // Map graphData contains one callsite which is on that depth and X
244      // start. Map xStartsPerDepth for each depth contains all X start
245      // coordinates that callsites on that level have.
246      this.graphData.set(
247          `${value.depth};${currentX}`, {callsite: value, width});
248      const xStarts = this.xStartsPerDepth.get(value.depth);
249      if (xStarts === undefined) {
250        this.xStartsPerDepth.set(value.depth, [currentX]);
251      } else {
252        xStarts.push(currentX);
253      }
254    }
255
256    // Draw the tooltip.
257    if (this.hoveredX > -1 && this.hoveredY > -1 && this.hoveredCallsite) {
258      // Must set these before measureText below.
259      ctx.font = this.rolloverFontStyle;
260      ctx.textBaseline = 'top';
261
262      // Size in px of the border around the text and the edge of the rollover
263      // background.
264      const paddingPx = 8;
265      // Size in px of the x and y offset between the mouse and the top left
266      // corner of the rollover box.
267      const offsetPx = 4;
268
269      const lines: string[] = [];
270      let lineSplitter: LineSplitter;
271      const nameText = this.getCallsiteName(this.hoveredCallsite);
272      const nameTextSize = ctx.measureText(nameText);
273      lineSplitter =
274          splitIfTooBig(nameText, width - paddingPx, nameTextSize.width);
275      let textWidth = lineSplitter.lineWidth;
276      lines.push(...lineSplitter.lines);
277
278      const mappingText = this.hoveredCallsite.mapping;
279      lineSplitter =
280          splitIfTooBig(mappingText, width, ctx.measureText(mappingText).width);
281      textWidth = Math.max(textWidth, lineSplitter.lineWidth);
282      lines.push(...lineSplitter.lines);
283
284      if (this.nodeRendering.totalSize !== undefined) {
285        const percentage =
286            this.hoveredCallsite.totalSize / this.totalSize * 100;
287        const totalSizeText = `${this.nodeRendering.totalSize}: ${
288            this.displaySize(
289                this.hoveredCallsite.totalSize,
290                unit,
291                unit === 'B' ? 1024 : 1000)} (${percentage.toFixed(2)}%)`;
292        lineSplitter = splitIfTooBig(
293            totalSizeText, width, ctx.measureText(totalSizeText).width);
294        textWidth = Math.max(textWidth, lineSplitter.lineWidth);
295        lines.push(...lineSplitter.lines);
296      }
297
298      if (this.nodeRendering.selfSize !== undefined &&
299          this.hoveredCallsite.selfSize > 0) {
300        const selfPercentage =
301            this.hoveredCallsite.selfSize / this.totalSize * 100;
302        const selfSizeText = `${this.nodeRendering.selfSize}: ${
303            this.displaySize(
304                this.hoveredCallsite.selfSize,
305                unit,
306                unit === 'B' ? 1024 : 1000)} (${selfPercentage.toFixed(2)}%)`;
307        lineSplitter = splitIfTooBig(
308            selfSizeText, width, ctx.measureText(selfSizeText).width);
309        textWidth = Math.max(textWidth, lineSplitter.lineWidth);
310        lines.push(...lineSplitter.lines);
311      }
312
313      // Compute a line height as the bounding box height + 50%:
314      const heightSample = ctx.measureText(
315          'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ');
316      const lineHeight =
317          Math.round(heightSample.actualBoundingBoxDescent * 1.5);
318
319      const rectWidth = textWidth + 2 * paddingPx;
320      const rectHeight = lineHeight * lines.length + 2 * paddingPx;
321
322      let rectXStart = this.hoveredX + offsetPx;
323      let rectYStart = this.hoveredY + offsetPx;
324
325      if (rectXStart + rectWidth > width) {
326        rectXStart = width - rectWidth;
327      }
328
329      if (rectYStart + rectHeight > height) {
330        rectYStart = height - rectHeight;
331      }
332
333      ctx.fillStyle = 'rgba(255, 255, 255, 0.9)';
334      ctx.fillRect(rectXStart, rectYStart, rectWidth, rectHeight);
335      ctx.fillStyle = 'hsl(200, 50%, 40%)';
336      ctx.textAlign = 'left';
337      for (let i = 0; i < lines.length; i++) {
338        const line = lines[i];
339        ctx.fillText(
340            line,
341            rectXStart + paddingPx,
342            rectYStart + paddingPx + i * lineHeight);
343      }
344    }
345  }
346
347  private getCallsiteName(value: CallsiteInfo): string {
348    return value.name === undefined || value.name === '' ? 'unknown' :
349                                                           value.name;
350  }
351
352  private displaySize(totalSize: number, unit: string, step = 1024): string {
353    if (unit === '') return totalSize.toLocaleString();
354    if (totalSize === 0) return `0 ${unit}`;
355    const units = [
356      ['', 1],
357      ['K', step],
358      ['M', Math.pow(step, 2)],
359      ['G', Math.pow(step, 3)]
360    ];
361    let unitsIndex = Math.trunc(Math.log(totalSize) / Math.log(step));
362    unitsIndex = unitsIndex > units.length - 1 ? units.length - 1 : unitsIndex;
363    const result = totalSize / +units[unitsIndex][1];
364    const resultString = totalSize % +units[unitsIndex][1] === 0 ?
365        result.toString() :
366        result.toFixed(2);
367    return `${resultString} ${units[unitsIndex][0]}${unit}`;
368  }
369
370  onMouseMove({x, y}: {x: number, y: number}) {
371    this.hoveredX = x;
372    this.hoveredY = y;
373    this.hoveredCallsite = this.findSelectedCallsite(x, y);
374    const isCallsiteSelected = this.hoveredCallsite !== undefined;
375    if (!isCallsiteSelected) {
376      this.onMouseOut();
377    }
378    return isCallsiteSelected;
379  }
380
381  onMouseOut() {
382    this.hoveredX = -1;
383    this.hoveredY = -1;
384    this.hoveredCallsite = undefined;
385  }
386
387  onMouseClick({x, y}: {x: number, y: number}): CallsiteInfo|undefined {
388    const clickedCallsite = this.findSelectedCallsite(x, y);
389    // TODO(b/148596659): Allow to expand [merged] callsites. Currently,
390    // this expands to the biggest of the nodes that were merged, which
391    // is confusing, so we disallow clicking on them.
392    if (clickedCallsite === undefined || clickedCallsite.merged) {
393      return undefined;
394    }
395    return clickedCallsite;
396  }
397
398  private findSelectedCallsite(x: number, y: number): CallsiteInfo|undefined {
399    const depth =
400        Math.trunc((y - this.startingY) / NODE_HEIGHT) - 1;  // at 0 is root
401    if (depth >= 0 && this.xStartsPerDepth.has(depth)) {
402      const startX = this.searchSmallest(this.xStartsPerDepth.get(depth)!, x);
403      const result = this.graphData.get(`${depth};${startX}`);
404      if (result !== undefined) {
405        const width = result.width;
406        return startX + width >= x ? result.callsite : undefined;
407      }
408    }
409    return undefined;
410  }
411
412  searchSmallest(haystack: number[], needle: number): number {
413    haystack = haystack.sort((n1, n2) => n1 - n2);
414    const [left, ] = searchSegment(haystack, needle);
415    return left === -1 ? -1 : haystack[left];
416  }
417
418  getHeight(): number {
419    return this.flamegraphData.length === 0 ? 0 :
420                                              (this.maxDepth + 2) * NODE_HEIGHT;
421  }
422}
423
424export interface LineSplitter {
425  lineWidth: number;
426  lines: string[];
427}
428
429export function splitIfTooBig(
430    line: string, width: number, lineWidth: number): LineSplitter {
431  if (line === '') return {lineWidth, lines: []};
432  const lines: string[] = [];
433  const charWidth = lineWidth / line.length;
434  const maxWidth = width - 32;
435  const maxLineLen = Math.trunc(maxWidth / charWidth);
436  while (line.length > 0) {
437    lines.push(line.slice(0, maxLineLen));
438    line = line.slice(maxLineLen);
439  }
440  lineWidth = Math.min(maxLineLen * charWidth, lineWidth);
441  return {lineWidth, lines};
442}
443