| // Copyright (C) 2018 The Android Open Source Project |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| import {searchSegment} from '../base/binary_search'; |
| import {cropText} from '../common/canvas_utils'; |
| |
| import {CallsiteInfo} from '../common/state'; |
| |
| interface Node { |
| width: number; |
| x: number; |
| nextXForChildren: number; |
| size: number; |
| } |
| |
| interface CallsiteInfoWidth { |
| callsite: CallsiteInfo; |
| width: number; |
| } |
| |
| // Height of one 'row' on the flame chart including 1px of whitespace |
| // below the box. |
| const NODE_HEIGHT = 18; |
| |
| export const FLAMEGRAPH_HOVERED_COLOR = 'hsl(224, 45%, 55%)'; |
| |
| export function findRootSize(data: CallsiteInfo[]) { |
| let totalSize = 0; |
| let i = 0; |
| while (i < data.length && data[i].depth === 0) { |
| totalSize += data[i].totalSize; |
| i++; |
| } |
| return totalSize; |
| } |
| |
| export interface NodeRendering { |
| totalSize?: string; |
| selfSize?: string; |
| } |
| |
| export class Flamegraph { |
| private nodeRendering: NodeRendering = {}; |
| private flamegraphData: CallsiteInfo[]; |
| private highlightSomeNodes = false; |
| private maxDepth = -1; |
| private totalSize = -1; |
| // Initialised on first draw() call |
| private labelCharWidth = 0; |
| private labelFontStyle = '12px Roboto Mono'; |
| private rolloverFontStyle = '12px Roboto Condensed'; |
| // Key for the map is depth followed by x coordinate - `depth;x` |
| private graphData: Map<string, CallsiteInfoWidth> = new Map(); |
| private xStartsPerDepth: Map<number, number[]> = new Map(); |
| |
| private hoveredX = -1; |
| private hoveredY = -1; |
| private hoveredCallsite?: CallsiteInfo; |
| private clickedCallsite?: CallsiteInfo; |
| |
| private startingY = 0; |
| |
| constructor(flamegraphData: CallsiteInfo[]) { |
| this.flamegraphData = flamegraphData; |
| this.findMaxDepth(); |
| } |
| |
| private findMaxDepth() { |
| this.maxDepth = Math.max(...this.flamegraphData.map(value => value.depth)); |
| } |
| |
| // Instead of highlighting the interesting nodes, we actually want to |
| // de-emphasize the non-highlighted nodes. Returns true if there |
| // are any highlighted nodes in the flamegraph. |
| private highlightingExists() { |
| this.highlightSomeNodes = this.flamegraphData.some((e) => e.highlighted); |
| } |
| |
| generateColor(name: string, isGreyedOut = false, highlighted: boolean): |
| string { |
| if (isGreyedOut) { |
| return '#d9d9d9'; |
| } |
| if (name === 'unknown' || name === 'root') { |
| return '#c0c0c0'; |
| } |
| let x = 0; |
| for (let i = 0; i < name.length; i += 1) { |
| x += name.charCodeAt(i) % 64; |
| } |
| x = x % 360; |
| let l = '76'; |
| // Make non-highlighted node lighter. |
| if (this.highlightSomeNodes && !highlighted) { |
| l = '90'; |
| } |
| return `hsl(${x}deg, 45%, ${l}%)`; |
| } |
| |
| /** |
| * Caller will have to call draw method after updating data to have updated |
| * graph. |
| */ |
| updateDataIfChanged( |
| nodeRendering: NodeRendering, flamegraphData: CallsiteInfo[], |
| clickedCallsite?: CallsiteInfo) { |
| this.nodeRendering = nodeRendering; |
| this.clickedCallsite = clickedCallsite; |
| if (this.flamegraphData === flamegraphData) { |
| return; |
| } |
| this.flamegraphData = flamegraphData; |
| this.clickedCallsite = clickedCallsite; |
| this.findMaxDepth(); |
| this.highlightingExists(); |
| // Finding total size of roots. |
| this.totalSize = findRootSize(flamegraphData); |
| } |
| |
| draw( |
| ctx: CanvasRenderingContext2D, width: number, height: number, x = 0, |
| y = 0, unit = 'B') { |
| |
| if (this.flamegraphData === undefined) { |
| return; |
| } |
| |
| ctx.font = this.labelFontStyle; |
| ctx.textBaseline = 'middle'; |
| if (this.labelCharWidth === 0) { |
| this.labelCharWidth = ctx.measureText('_').width; |
| } |
| |
| this.startingY = y; |
| |
| // For each node, we use this map to get information about it's parent |
| // (total size of it, width and where it starts in graph) so we can |
| // calculate it's own position in graph. |
| const nodesMap = new Map<number, Node>(); |
| let currentY = y; |
| nodesMap.set(-1, {width, nextXForChildren: x, size: this.totalSize, x}); |
| |
| // Initialize data needed for click/hover behavior. |
| this.graphData = new Map(); |
| this.xStartsPerDepth = new Map(); |
| |
| // Draw root node. |
| ctx.fillStyle = this.generateColor('root', false, false); |
| ctx.fillRect(x, currentY, width, NODE_HEIGHT - 1); |
| const text = cropText( |
| `root: ${ |
| this.displaySize( |
| this.totalSize, unit, unit === 'B' ? 1024 : 1000)}`, |
| this.labelCharWidth, |
| width - 2); |
| ctx.fillStyle = 'black'; |
| ctx.fillText(text, x + 5, currentY + (NODE_HEIGHT - 1) / 2); |
| currentY += NODE_HEIGHT; |
| |
| // Set style for borders. |
| ctx.strokeStyle = 'white'; |
| ctx.lineWidth = 0.5; |
| |
| for (let i = 0; i < this.flamegraphData.length; i++) { |
| if (currentY > height) { |
| break; |
| } |
| const value = this.flamegraphData[i]; |
| const parentNode = nodesMap.get(value.parentId); |
| if (parentNode === undefined) { |
| continue; |
| } |
| |
| const isClicked = this.clickedCallsite !== undefined; |
| const isFullWidth = |
| isClicked && value.depth <= this.clickedCallsite!.depth; |
| const isGreyedOut = |
| isClicked && value.depth < this.clickedCallsite!.depth; |
| |
| const parent = value.parentId; |
| const parentSize = parent === -1 ? this.totalSize : parentNode.size; |
| // Calculate node's width based on its proportion in parent. |
| const width = |
| (isFullWidth ? 1 : value.totalSize / parentSize) * parentNode.width; |
| |
| const currentX = parentNode.nextXForChildren; |
| currentY = y + NODE_HEIGHT * (value.depth + 1); |
| |
| // Draw node. |
| const name = this.getCallsiteName(value); |
| ctx.fillStyle = this.generateColor(name, isGreyedOut, value.highlighted); |
| ctx.fillRect(currentX, currentY, width, NODE_HEIGHT - 1); |
| |
| // Set current node's data in map for children to use. |
| nodesMap.set(value.id, { |
| width, |
| nextXForChildren: currentX, |
| size: value.totalSize, |
| x: currentX |
| }); |
| // Update next x coordinate in parent. |
| nodesMap.set(value.parentId, { |
| width: parentNode.width, |
| nextXForChildren: currentX + width, |
| size: parentNode.size, |
| x: parentNode.x |
| }); |
| |
| // Draw name. |
| const labelPaddingPx = 5; |
| const maxLabelWidth = width - labelPaddingPx * 2; |
| let text = cropText(name, this.labelCharWidth, maxLabelWidth); |
| // If cropped text and the original text are within 20% we keep the |
| // original text and just squish it a bit. |
| if (text.length * 1.2 > name.length) { |
| text = name; |
| } |
| ctx.fillStyle = 'black'; |
| ctx.fillText( |
| text, |
| currentX + labelPaddingPx, |
| currentY + (NODE_HEIGHT - 1) / 2, |
| maxLabelWidth); |
| |
| // Draw border on the right of node. |
| ctx.beginPath(); |
| ctx.moveTo(currentX + width, currentY); |
| ctx.lineTo(currentX + width, currentY + NODE_HEIGHT); |
| ctx.stroke(); |
| |
| // Add this node for recognizing in click/hover. |
| // Map graphData contains one callsite which is on that depth and X |
| // start. Map xStartsPerDepth for each depth contains all X start |
| // coordinates that callsites on that level have. |
| this.graphData.set( |
| `${value.depth};${currentX}`, {callsite: value, width}); |
| const xStarts = this.xStartsPerDepth.get(value.depth); |
| if (xStarts === undefined) { |
| this.xStartsPerDepth.set(value.depth, [currentX]); |
| } else { |
| xStarts.push(currentX); |
| } |
| } |
| |
| // Draw the tooltip. |
| if (this.hoveredX > -1 && this.hoveredY > -1 && this.hoveredCallsite) { |
| // Must set these before measureText below. |
| ctx.font = this.rolloverFontStyle; |
| ctx.textBaseline = 'top'; |
| |
| // Size in px of the border around the text and the edge of the rollover |
| // background. |
| const paddingPx = 8; |
| // Size in px of the x and y offset between the mouse and the top left |
| // corner of the rollover box. |
| const offsetPx = 4; |
| |
| const lines: string[] = []; |
| |
| let textWidth = this.addToTooltip( |
| this.getCallsiteName(this.hoveredCallsite), |
| width - paddingPx, |
| ctx, |
| lines); |
| if (this.hoveredCallsite.location != null) { |
| textWidth = Math.max( |
| textWidth, |
| this.addToTooltip( |
| this.hoveredCallsite.location, width, ctx, lines)); |
| } |
| textWidth = Math.max( |
| textWidth, |
| this.addToTooltip(this.hoveredCallsite.mapping, width, ctx, lines)); |
| |
| if (this.nodeRendering.totalSize !== undefined) { |
| const percentage = |
| this.hoveredCallsite.totalSize / this.totalSize * 100; |
| const totalSizeText = `${this.nodeRendering.totalSize}: ${ |
| this.displaySize( |
| this.hoveredCallsite.totalSize, |
| unit, |
| unit === 'B' ? 1024 : 1000)} (${percentage.toFixed(2)}%)`; |
| textWidth = Math.max( |
| textWidth, this.addToTooltip(totalSizeText, width, ctx, lines)); |
| } |
| |
| if (this.nodeRendering.selfSize !== undefined && |
| this.hoveredCallsite.selfSize > 0) { |
| const selfPercentage = |
| this.hoveredCallsite.selfSize / this.totalSize * 100; |
| const selfSizeText = `${this.nodeRendering.selfSize}: ${ |
| this.displaySize( |
| this.hoveredCallsite.selfSize, |
| unit, |
| unit === 'B' ? 1024 : 1000)} (${selfPercentage.toFixed(2)}%)`; |
| textWidth = Math.max( |
| textWidth, this.addToTooltip(selfSizeText, width, ctx, lines)); |
| } |
| |
| // Compute a line height as the bounding box height + 50%: |
| const heightSample = ctx.measureText( |
| 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'); |
| const lineHeight = |
| Math.round(heightSample.actualBoundingBoxDescent * 1.5); |
| |
| const rectWidth = textWidth + 2 * paddingPx; |
| const rectHeight = lineHeight * lines.length + 2 * paddingPx; |
| |
| let rectXStart = this.hoveredX + offsetPx; |
| let rectYStart = this.hoveredY + offsetPx; |
| |
| if (rectXStart + rectWidth > width) { |
| rectXStart = width - rectWidth; |
| } |
| |
| if (rectYStart + rectHeight > height) { |
| rectYStart = height - rectHeight; |
| } |
| |
| ctx.fillStyle = 'rgba(255, 255, 255, 0.9)'; |
| ctx.fillRect(rectXStart, rectYStart, rectWidth, rectHeight); |
| ctx.fillStyle = 'hsl(200, 50%, 40%)'; |
| ctx.textAlign = 'left'; |
| for (let i = 0; i < lines.length; i++) { |
| const line = lines[i]; |
| ctx.fillText( |
| line, |
| rectXStart + paddingPx, |
| rectYStart + paddingPx + i * lineHeight); |
| } |
| } |
| } |
| |
| private addToTooltip( |
| text: string, width: number, ctx: CanvasRenderingContext2D, |
| lines: string[]): number { |
| const lineSplitter: LineSplitter = |
| splitIfTooBig(text, width, ctx.measureText(text).width); |
| lines.push(...lineSplitter.lines); |
| return lineSplitter.lineWidth; |
| } |
| |
| private getCallsiteName(value: CallsiteInfo): string { |
| return value.name === undefined || value.name === '' ? 'unknown' : |
| value.name; |
| } |
| |
| private displaySize(totalSize: number, unit: string, step = 1024): string { |
| if (unit === '') return totalSize.toLocaleString(); |
| if (totalSize === 0) return `0 ${unit}`; |
| const units = [ |
| ['', 1], |
| ['K', step], |
| ['M', Math.pow(step, 2)], |
| ['G', Math.pow(step, 3)] |
| ]; |
| let unitsIndex = Math.trunc(Math.log(totalSize) / Math.log(step)); |
| unitsIndex = unitsIndex > units.length - 1 ? units.length - 1 : unitsIndex; |
| const result = totalSize / +units[unitsIndex][1]; |
| const resultString = totalSize % +units[unitsIndex][1] === 0 ? |
| result.toString() : |
| result.toFixed(2); |
| return `${resultString} ${units[unitsIndex][0]}${unit}`; |
| } |
| |
| onMouseMove({x, y}: {x: number, y: number}) { |
| this.hoveredX = x; |
| this.hoveredY = y; |
| this.hoveredCallsite = this.findSelectedCallsite(x, y); |
| const isCallsiteSelected = this.hoveredCallsite !== undefined; |
| if (!isCallsiteSelected) { |
| this.onMouseOut(); |
| } |
| return isCallsiteSelected; |
| } |
| |
| onMouseOut() { |
| this.hoveredX = -1; |
| this.hoveredY = -1; |
| this.hoveredCallsite = undefined; |
| } |
| |
| onMouseClick({x, y}: {x: number, y: number}): CallsiteInfo|undefined { |
| const clickedCallsite = this.findSelectedCallsite(x, y); |
| // TODO(b/148596659): Allow to expand [merged] callsites. Currently, |
| // this expands to the biggest of the nodes that were merged, which |
| // is confusing, so we disallow clicking on them. |
| if (clickedCallsite === undefined || clickedCallsite.merged) { |
| return undefined; |
| } |
| return clickedCallsite; |
| } |
| |
| private findSelectedCallsite(x: number, y: number): CallsiteInfo|undefined { |
| const depth = |
| Math.trunc((y - this.startingY) / NODE_HEIGHT) - 1; // at 0 is root |
| if (depth >= 0 && this.xStartsPerDepth.has(depth)) { |
| const startX = this.searchSmallest(this.xStartsPerDepth.get(depth)!, x); |
| const result = this.graphData.get(`${depth};${startX}`); |
| if (result !== undefined) { |
| const width = result.width; |
| return startX + width >= x ? result.callsite : undefined; |
| } |
| } |
| return undefined; |
| } |
| |
| searchSmallest(haystack: number[], needle: number): number { |
| haystack = haystack.sort((n1, n2) => n1 - n2); |
| const [left, ] = searchSegment(haystack, needle); |
| return left === -1 ? -1 : haystack[left]; |
| } |
| |
| getHeight(): number { |
| return this.flamegraphData.length === 0 ? 0 : |
| (this.maxDepth + 2) * NODE_HEIGHT; |
| } |
| } |
| |
| export interface LineSplitter { |
| lineWidth: number; |
| lines: string[]; |
| } |
| |
| export function splitIfTooBig( |
| line: string, width: number, lineWidth: number): LineSplitter { |
| if (line === '') return {lineWidth, lines: []}; |
| const lines: string[] = []; |
| const charWidth = lineWidth / line.length; |
| const maxWidth = width - 32; |
| const maxLineLen = Math.trunc(maxWidth / charWidth); |
| while (line.length > 0) { |
| lines.push(line.slice(0, maxLineLen)); |
| line = line.slice(maxLineLen); |
| } |
| lineWidth = Math.min(maxLineLen * charWidth, lineWidth); |
| return {lineWidth, lines}; |
| } |