1// Copyright (C) 2024 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 m from 'mithril'; 16import {findRef} from '../base/dom_utils'; 17import {assertExists, assertTrue} from '../base/logging'; 18import {Monitor} from '../base/monitor'; 19import {Button, ButtonBar} from './button'; 20import {EmptyState} from './empty_state'; 21import {Popup, PopupPosition} from './popup'; 22import {scheduleFullRedraw} from './raf'; 23import {Select} from './select'; 24import {Spinner} from './spinner'; 25import {TagInput} from './tag_input'; 26import {SegmentedButtons} from './segmented_buttons'; 27import {z} from 'zod'; 28 29const LABEL_FONT_STYLE = '12px Roboto'; 30const NODE_HEIGHT = 20; 31const MIN_PIXEL_DISPLAYED = 3; 32const FILTER_COMMON_TEXT = ` 33- "Show Stack: foo" or "SS: foo" or "foo" to show only stacks containing "foo" 34- "Hide Stack: foo" or "HS: foo" to hide all stacks containing "foo" 35- "Show From Frame: foo" or "SFF: foo" to show frames containing "foo" and all descendants 36- "Hide Frame: foo" or "HF: foo" to hide all frames containing "foo" 37- "Pivot: foo" or "P: foo" to pivot on frames containing "foo". 38Note: Pivot applies after all other filters and only one pivot can be active at a time. 39`; 40const FILTER_EMPTY_TEXT = ` 41Available filters:${FILTER_COMMON_TEXT} 42`; 43const LABEL_PADDING_PX = 5; 44const LABEL_MIN_WIDTH_FOR_TEXT_PX = 5; 45const PADDING_NODE_COUNT = 8; 46 47interface BaseSource { 48 readonly queryXStart: number; 49 readonly queryXEnd: number; 50 readonly type: 'ABOVE_ROOT' | 'BELOW_ROOT' | 'ROOT'; 51} 52 53interface MergedSource extends BaseSource { 54 readonly kind: 'MERGED'; 55} 56 57interface RootSource extends BaseSource { 58 readonly kind: 'ROOT'; 59} 60 61interface NodeSource extends BaseSource { 62 readonly kind: 'NODE'; 63 readonly queryIdx: number; 64} 65 66type Source = MergedSource | NodeSource | RootSource; 67 68interface RenderNode { 69 readonly x: number; 70 readonly y: number; 71 readonly width: number; 72 readonly source: Source; 73 readonly state: 'NORMAL' | 'PARTIAL' | 'SELECTED'; 74} 75 76interface ZoomRegion { 77 readonly queryXStart: number; 78 readonly queryXEnd: number; 79 readonly type: 'ABOVE_ROOT' | 'BELOW_ROOT' | 'ROOT'; 80} 81 82export interface FlamegraphQueryData { 83 readonly nodes: ReadonlyArray<{ 84 readonly id: number; 85 readonly parentId: number; 86 readonly depth: number; 87 readonly name: string; 88 readonly selfValue: number; 89 readonly cumulativeValue: number; 90 readonly parentCumulativeValue?: number; 91 readonly properties: ReadonlyMap<string, string>; 92 readonly xStart: number; 93 readonly xEnd: number; 94 }>; 95 readonly unfilteredCumulativeValue: number; 96 readonly allRootsCumulativeValue: number; 97 readonly minDepth: number; 98 readonly maxDepth: number; 99} 100 101const FLAMEGRAPH_FILTER_SCHEMA = z 102 .object({ 103 kind: z 104 .union([ 105 z.literal('SHOW_STACK').readonly(), 106 z.literal('HIDE_STACK').readonly(), 107 z.literal('SHOW_FROM_FRAME').readonly(), 108 z.literal('HIDE_FRAME').readonly(), 109 ]) 110 .readonly(), 111 filter: z.string().readonly(), 112 }) 113 .readonly(); 114 115type FlamegraphFilter = z.infer<typeof FLAMEGRAPH_FILTER_SCHEMA>; 116 117const FLAMEGRAPH_VIEW_SCHEMA = z 118 .discriminatedUnion('kind', [ 119 z.object({kind: z.literal('TOP_DOWN').readonly()}), 120 z.object({kind: z.literal('BOTTOM_UP').readonly()}), 121 z.object({ 122 kind: z.literal('PIVOT').readonly(), 123 pivot: z.string().readonly(), 124 }), 125 ]) 126 .readonly(); 127 128export type FlamegraphView = z.infer<typeof FLAMEGRAPH_VIEW_SCHEMA>; 129 130export const FLAMEGRAPH_STATE_SCHEMA = z 131 .object({ 132 selectedMetricName: z.string().readonly(), 133 filters: z.array(FLAMEGRAPH_FILTER_SCHEMA).readonly(), 134 view: FLAMEGRAPH_VIEW_SCHEMA, 135 }) 136 .readonly(); 137 138export type FlamegraphState = z.infer<typeof FLAMEGRAPH_STATE_SCHEMA>; 139 140interface FlamegraphMetric { 141 readonly name: string; 142 readonly unit: string; 143} 144 145export interface FlamegraphAttrs { 146 readonly metrics: ReadonlyArray<FlamegraphMetric>; 147 readonly state: FlamegraphState; 148 readonly data: FlamegraphQueryData | undefined; 149 150 readonly onStateChange: (filters: FlamegraphState) => void; 151} 152 153/* 154 * Widget for visualizing "tree-like" data structures using an interactive 155 * flamegraph visualization. 156 * 157 * To use this widget, provide an array of "metrics", which correspond to 158 * different properties of the tree to switch between (e.g. object size 159 * and object count) and the data which should be displayed. 160 * 161 * Note that it's valid to pass "undefined" as the data: this will cause a 162 * loading container to be shown. 163 * 164 * Example: 165 * 166 * ``` 167 * const metrics = [...]; 168 * let state = ...; 169 * let data = ...; 170 * 171 * m(Flamegraph, { 172 * metrics, 173 * state, 174 * data, 175 * onStateChange: (newState) => { 176 * state = newState, 177 * data = undefined; 178 * fetchData(); 179 * }, 180 * }); 181 * ``` 182 */ 183export class Flamegraph implements m.ClassComponent<FlamegraphAttrs> { 184 private attrs: FlamegraphAttrs; 185 186 private rawFilterText: string = ''; 187 private filterFocus: boolean = false; 188 189 private dataChangeMonitor = new Monitor([() => this.attrs.data]); 190 private zoomRegion?: ZoomRegion; 191 192 private renderNodesMonitor = new Monitor([ 193 () => this.attrs.data, 194 () => this.canvasWidth, 195 () => this.zoomRegion, 196 ]); 197 private renderNodes?: ReadonlyArray<RenderNode>; 198 199 private tooltipPos?: { 200 node: RenderNode; 201 x: number; 202 state: 'HOVER' | 'CLICK' | 'DECLICK'; 203 }; 204 private lastClickedNode?: RenderNode; 205 206 private hoveredX?: number; 207 private hoveredY?: number; 208 209 private canvasWidth = 0; 210 private labelCharWidth = 0; 211 212 constructor({attrs}: m.Vnode<FlamegraphAttrs, {}>) { 213 this.attrs = attrs; 214 } 215 216 view({attrs}: m.Vnode<FlamegraphAttrs, this>): void | m.Children { 217 this.attrs = attrs; 218 if (this.dataChangeMonitor.ifStateChanged()) { 219 this.zoomRegion = undefined; 220 this.lastClickedNode = undefined; 221 this.tooltipPos = undefined; 222 } 223 if (attrs.data === undefined) { 224 return m( 225 '.pf-flamegraph', 226 this.renderFilterBar(attrs), 227 m( 228 '.loading-container', 229 m( 230 EmptyState, 231 { 232 icon: 'bar_chart', 233 title: 'Computing graph ...', 234 className: 'flamegraph-loading', 235 }, 236 m(Spinner, {easing: true}), 237 ), 238 ), 239 ); 240 } 241 const {minDepth, maxDepth} = attrs.data; 242 const canvasHeight = 243 Math.max(maxDepth - minDepth + PADDING_NODE_COUNT, PADDING_NODE_COUNT) * 244 NODE_HEIGHT; 245 return m( 246 '.pf-flamegraph', 247 this.renderFilterBar(attrs), 248 m( 249 '.canvas-container[ref=canvas-container]', 250 { 251 onscroll: () => scheduleFullRedraw(), 252 }, 253 m( 254 Popup, 255 { 256 trigger: m('.popup-anchor', { 257 style: { 258 left: this.tooltipPos?.x + 'px', 259 top: this.tooltipPos?.node.y + 'px', 260 }, 261 }), 262 position: PopupPosition.Bottom, 263 isOpen: 264 this.tooltipPos?.state === 'HOVER' || 265 this.tooltipPos?.state === 'CLICK', 266 className: 'pf-flamegraph-tooltip-popup', 267 offset: NODE_HEIGHT, 268 }, 269 this.renderTooltip(), 270 ), 271 m(`canvas[ref=canvas]`, { 272 style: `height:${canvasHeight}px; width:100%`, 273 onmousemove: ({offsetX, offsetY}: MouseEvent) => { 274 scheduleFullRedraw(); 275 this.hoveredX = offsetX; 276 this.hoveredY = offsetY; 277 if (this.tooltipPos?.state === 'CLICK') { 278 return; 279 } 280 const renderNode = this.renderNodes?.find((n) => 281 isIntersecting(offsetX, offsetY, n), 282 ); 283 if (renderNode === undefined) { 284 this.tooltipPos = undefined; 285 return; 286 } 287 if ( 288 isIntersecting( 289 this.tooltipPos?.x, 290 this.tooltipPos?.node.y, 291 renderNode, 292 ) 293 ) { 294 return; 295 } 296 this.tooltipPos = { 297 x: offsetX, 298 node: renderNode, 299 state: 'HOVER', 300 }; 301 }, 302 onmouseout: () => { 303 this.hoveredX = undefined; 304 this.hoveredY = undefined; 305 document.body.style.cursor = 'default'; 306 if ( 307 this.tooltipPos?.state === 'HOVER' || 308 this.tooltipPos?.state === 'DECLICK' 309 ) { 310 this.tooltipPos = undefined; 311 } 312 scheduleFullRedraw(); 313 }, 314 onclick: ({offsetX, offsetY}: MouseEvent) => { 315 const renderNode = this.renderNodes?.find((n) => 316 isIntersecting(offsetX, offsetY, n), 317 ); 318 this.lastClickedNode = renderNode; 319 if (renderNode === undefined) { 320 this.tooltipPos = undefined; 321 } else if ( 322 isIntersecting( 323 this.tooltipPos?.x, 324 this.tooltipPos?.node.y, 325 renderNode, 326 ) 327 ) { 328 this.tooltipPos!.state = 329 this.tooltipPos?.state === 'CLICK' ? 'DECLICK' : 'CLICK'; 330 } else { 331 this.tooltipPos = { 332 x: offsetX, 333 node: renderNode, 334 state: 'CLICK', 335 }; 336 } 337 scheduleFullRedraw(); 338 }, 339 ondblclick: ({offsetX, offsetY}: MouseEvent) => { 340 const renderNode = this.renderNodes?.find((n) => 341 isIntersecting(offsetX, offsetY, n), 342 ); 343 // TODO(lalitm): ignore merged nodes for now as we haven't quite 344 // figured out the UX for this. 345 if (renderNode?.source.kind === 'MERGED') { 346 return; 347 } 348 this.zoomRegion = renderNode?.source; 349 scheduleFullRedraw(); 350 }, 351 }), 352 ), 353 ); 354 } 355 356 oncreate({dom}: m.VnodeDOM<FlamegraphAttrs, this>) { 357 this.drawCanvas(dom); 358 } 359 360 onupdate({dom}: m.VnodeDOM<FlamegraphAttrs, this>) { 361 this.drawCanvas(dom); 362 } 363 364 static createDefaultState( 365 metrics: ReadonlyArray<FlamegraphMetric>, 366 ): FlamegraphState { 367 return { 368 selectedMetricName: metrics[0].name, 369 filters: [], 370 view: {kind: 'TOP_DOWN'}, 371 }; 372 } 373 374 private drawCanvas(dom: Element) { 375 // TODO(lalitm): consider migrating to VirtualCanvas to improve performance here. 376 const canvasContainer = findRef(dom, 'canvas-container'); 377 if (canvasContainer === null) { 378 return; 379 } 380 const canvas = findRef(dom, 'canvas'); 381 if (canvas === null || !(canvas instanceof HTMLCanvasElement)) { 382 return; 383 } 384 const ctx = canvas.getContext('2d'); 385 if (ctx === null) { 386 return; 387 } 388 canvas.width = canvas.offsetWidth * devicePixelRatio; 389 canvas.height = canvas.offsetHeight * devicePixelRatio; 390 this.canvasWidth = canvas.offsetWidth; 391 392 if (this.renderNodesMonitor.ifStateChanged()) { 393 if (this.attrs.data === undefined) { 394 this.renderNodes = undefined; 395 this.lastClickedNode = undefined; 396 } else { 397 this.renderNodes = computeRenderNodes( 398 this.attrs.data, 399 this.zoomRegion ?? { 400 queryXStart: 0, 401 queryXEnd: this.attrs.data.allRootsCumulativeValue, 402 type: 'ROOT', 403 }, 404 canvas.offsetWidth, 405 ); 406 this.lastClickedNode = this.renderNodes?.find((n) => 407 isIntersecting(this.lastClickedNode?.x, this.lastClickedNode?.y, n), 408 ); 409 } 410 this.tooltipPos = undefined; 411 } 412 if (this.attrs.data === undefined || this.renderNodes === undefined) { 413 return; 414 } 415 416 const containerRect = canvasContainer.getBoundingClientRect(); 417 const canvasRect = canvas.getBoundingClientRect(); 418 419 const yStart = containerRect.top - canvasRect.top; 420 const yEnd = containerRect.bottom - canvasRect.top; 421 422 const {allRootsCumulativeValue, unfilteredCumulativeValue, nodes} = 423 this.attrs.data; 424 const unit = assertExists(this.selectedMetric).unit; 425 426 ctx.clearRect(0, 0, canvas.offsetWidth, canvas.offsetHeight); 427 ctx.save(); 428 ctx.scale(devicePixelRatio, devicePixelRatio); 429 430 ctx.font = LABEL_FONT_STYLE; 431 ctx.textBaseline = 'middle'; 432 433 ctx.strokeStyle = 'white'; 434 ctx.lineWidth = 0.5; 435 436 if (this.labelCharWidth === 0) { 437 this.labelCharWidth = ctx.measureText('_').width; 438 } 439 440 let hoveredNode: RenderNode | undefined = undefined; 441 for (let i = 0; i < this.renderNodes.length; i++) { 442 const node = this.renderNodes[i]; 443 const {x, y, width: width, source, state} = node; 444 if (y + NODE_HEIGHT <= yStart || y >= yEnd) { 445 continue; 446 } 447 448 const hover = isIntersecting(this.hoveredX, this.hoveredY, node); 449 if (hover) { 450 hoveredNode = node; 451 } 452 let name: string; 453 if (source.kind === 'ROOT') { 454 const val = displaySize(allRootsCumulativeValue, unit); 455 const percent = displayPercentage( 456 allRootsCumulativeValue, 457 unfilteredCumulativeValue, 458 ); 459 name = `root: ${val} (${percent})`; 460 ctx.fillStyle = generateColor('root', state === 'PARTIAL', hover); 461 } else if (source.kind === 'MERGED') { 462 name = '(merged)'; 463 ctx.fillStyle = generateColor(name, state === 'PARTIAL', false); 464 } else { 465 name = nodes[source.queryIdx].name; 466 ctx.fillStyle = generateColor(name, state === 'PARTIAL', hover); 467 } 468 ctx.fillRect(x, y, width - 1, NODE_HEIGHT - 1); 469 470 const widthNoPadding = width - LABEL_PADDING_PX * 2; 471 if (widthNoPadding >= LABEL_MIN_WIDTH_FOR_TEXT_PX) { 472 ctx.fillStyle = 'black'; 473 ctx.fillText( 474 name.substring(0, widthNoPadding / this.labelCharWidth), 475 x + LABEL_PADDING_PX, 476 y + (NODE_HEIGHT - 1) / 2, 477 widthNoPadding, 478 ); 479 } 480 if (this.lastClickedNode?.x === x && this.lastClickedNode?.y === y) { 481 ctx.strokeStyle = 'blue'; 482 ctx.lineWidth = 2; 483 ctx.beginPath(); 484 ctx.moveTo(x, y); 485 ctx.lineTo(x + width, y); 486 ctx.lineTo(x + width, y + NODE_HEIGHT - 1); 487 ctx.lineTo(x, y + NODE_HEIGHT - 1); 488 ctx.lineTo(x, y); 489 ctx.stroke(); 490 ctx.strokeStyle = 'white'; 491 ctx.lineWidth = 0.5; 492 } 493 } 494 if (hoveredNode === undefined) { 495 canvas.style.cursor = 'default'; 496 } else { 497 canvas.style.cursor = 'pointer'; 498 } 499 ctx.restore(); 500 } 501 502 private renderFilterBar(attrs: FlamegraphAttrs) { 503 const self = this; 504 return m( 505 '.filter-bar', 506 m( 507 Select, 508 { 509 value: attrs.state.selectedMetricName, 510 onchange: (e: Event) => { 511 const el = e.target as HTMLSelectElement; 512 attrs.onStateChange({ 513 ...self.attrs.state, 514 selectedMetricName: el.value, 515 }); 516 scheduleFullRedraw(); 517 }, 518 }, 519 attrs.metrics.map((x) => { 520 return m('option', {value: x.name}, x.name); 521 }), 522 ), 523 m( 524 Popup, 525 { 526 trigger: m(TagInput, { 527 tags: toTags(self.attrs.state), 528 value: this.rawFilterText, 529 onChange: (value: string) => { 530 self.rawFilterText = value; 531 scheduleFullRedraw(); 532 }, 533 onTagAdd: (tag: string) => { 534 self.rawFilterText = ''; 535 self.attrs.onStateChange(updateState(self.attrs.state, tag)); 536 scheduleFullRedraw(); 537 }, 538 onTagRemove(index: number) { 539 if (index === self.attrs.state.filters.length) { 540 self.attrs.onStateChange({ 541 ...self.attrs.state, 542 view: {kind: 'TOP_DOWN'}, 543 }); 544 } else { 545 const filters = Array.from(self.attrs.state.filters); 546 filters.splice(index, 1); 547 self.attrs.onStateChange({ 548 ...self.attrs.state, 549 filters, 550 }); 551 } 552 scheduleFullRedraw(); 553 }, 554 onfocus() { 555 self.filterFocus = true; 556 }, 557 onblur() { 558 self.filterFocus = false; 559 }, 560 placeholder: 'Add filter...', 561 }), 562 isOpen: self.filterFocus && this.rawFilterText.length === 0, 563 position: PopupPosition.Bottom, 564 }, 565 m('.pf-flamegraph-filter-bar-popup-content', FILTER_EMPTY_TEXT.trim()), 566 ), 567 m(SegmentedButtons, { 568 options: [{label: 'Top Down'}, {label: 'Bottom Up'}], 569 selectedOption: this.attrs.state.view.kind === 'TOP_DOWN' ? 0 : 1, 570 onOptionSelected: (num) => { 571 self.attrs.onStateChange({ 572 ...this.attrs.state, 573 view: {kind: num === 0 ? 'TOP_DOWN' : 'BOTTOM_UP'}, 574 }); 575 scheduleFullRedraw(); 576 }, 577 disabled: this.attrs.state.view.kind === 'PIVOT', 578 }), 579 ); 580 } 581 582 private renderTooltip() { 583 if (this.tooltipPos === undefined) { 584 return undefined; 585 } 586 const {node} = this.tooltipPos; 587 if (node.source.kind === 'MERGED') { 588 return m( 589 'div', 590 m('.tooltip-bold-text', '(merged)'), 591 m('.tooltip-text', 'Nodes too small to show, please use filters'), 592 ); 593 } 594 const {nodes, allRootsCumulativeValue, unfilteredCumulativeValue} = 595 assertExists(this.attrs.data); 596 const {unit} = assertExists(this.selectedMetric); 597 if (node.source.kind === 'ROOT') { 598 const val = displaySize(allRootsCumulativeValue, unit); 599 const percent = displayPercentage( 600 allRootsCumulativeValue, 601 unfilteredCumulativeValue, 602 ); 603 return m( 604 'div', 605 m('.tooltip-bold-text', 'root'), 606 m( 607 '.tooltip-text-line', 608 m('.tooltip-bold-text', 'Cumulative:'), 609 m('.tooltip-text', `${val}, ${percent}`), 610 ), 611 ); 612 } 613 const {queryIdx} = node.source; 614 const { 615 name, 616 cumulativeValue, 617 selfValue, 618 parentCumulativeValue, 619 properties, 620 } = nodes[queryIdx]; 621 const filterButtonClick = (state: FlamegraphState) => { 622 this.attrs.onStateChange(state); 623 this.tooltipPos = undefined; 624 scheduleFullRedraw(); 625 }; 626 627 const percent = displayPercentage( 628 cumulativeValue, 629 unfilteredCumulativeValue, 630 ); 631 const selfPercent = displayPercentage(selfValue, unfilteredCumulativeValue); 632 633 let percentText = `all: ${percent}`; 634 let selfPercentText = `all: ${selfPercent}`; 635 if (parentCumulativeValue !== undefined) { 636 const parentPercent = displayPercentage( 637 cumulativeValue, 638 parentCumulativeValue, 639 ); 640 percentText += `, parent: ${parentPercent}`; 641 const parentSelfPercent = displayPercentage( 642 selfValue, 643 parentCumulativeValue, 644 ); 645 selfPercentText += `, parent: ${parentSelfPercent}`; 646 } 647 return m( 648 'div', 649 m('.tooltip-bold-text', name), 650 m( 651 '.tooltip-text-line', 652 m('.tooltip-bold-text', 'Cumulative:'), 653 m( 654 '.tooltip-text', 655 `${displaySize(cumulativeValue, unit)} (${percentText})`, 656 ), 657 ), 658 m( 659 '.tooltip-text-line', 660 m('.tooltip-bold-text', 'Self:'), 661 m( 662 '.tooltip-text', 663 `${displaySize(selfValue, unit)} (${selfPercentText})`, 664 ), 665 ), 666 Array.from(properties, ([key, value]) => { 667 return m( 668 '.tooltip-text-line', 669 m('.tooltip-bold-text', key + ':'), 670 m('.tooltip-text', value), 671 ); 672 }), 673 m( 674 ButtonBar, 675 {}, 676 m(Button, { 677 label: 'Zoom', 678 onclick: () => { 679 this.zoomRegion = node.source; 680 scheduleFullRedraw(); 681 }, 682 }), 683 m(Button, { 684 label: 'Show Stack', 685 onclick: () => { 686 filterButtonClick( 687 addFilter(this.attrs.state, { 688 kind: 'SHOW_STACK', 689 filter: `^${name}$`, 690 }), 691 ); 692 }, 693 }), 694 m(Button, { 695 label: 'Hide Stack', 696 onclick: () => { 697 filterButtonClick( 698 addFilter(this.attrs.state, { 699 kind: 'HIDE_STACK', 700 filter: `^${name}$`, 701 }), 702 ); 703 }, 704 }), 705 m(Button, { 706 label: 'Hide Frame', 707 onclick: () => { 708 filterButtonClick( 709 addFilter(this.attrs.state, { 710 kind: 'HIDE_FRAME', 711 filter: `^${name}$`, 712 }), 713 ); 714 }, 715 }), 716 m(Button, { 717 label: 'Show From Frame', 718 onclick: () => { 719 filterButtonClick( 720 addFilter(this.attrs.state, { 721 kind: 'SHOW_FROM_FRAME', 722 filter: `^${name}$`, 723 }), 724 ); 725 }, 726 }), 727 m(Button, { 728 label: 'Pivot', 729 onclick: () => { 730 filterButtonClick({ 731 ...this.attrs.state, 732 view: {kind: 'PIVOT', pivot: name}, 733 }); 734 }, 735 }), 736 ), 737 ); 738 } 739 740 private get selectedMetric() { 741 return this.attrs.metrics.find( 742 (x) => x.name === this.attrs.state.selectedMetricName, 743 ); 744 } 745} 746 747function computeRenderNodes( 748 {nodes, allRootsCumulativeValue, minDepth}: FlamegraphQueryData, 749 zoomRegion: ZoomRegion, 750 canvasWidth: number, 751): ReadonlyArray<RenderNode> { 752 const renderNodes: RenderNode[] = []; 753 754 const mergedKeyToX = new Map<string, number>(); 755 const keyToChildMergedIdx = new Map<string, number>(); 756 renderNodes.push({ 757 x: 0, 758 y: -minDepth * NODE_HEIGHT, 759 width: canvasWidth, 760 source: { 761 kind: 'ROOT', 762 queryXStart: 0, 763 queryXEnd: allRootsCumulativeValue, 764 type: 'ROOT', 765 }, 766 state: 767 zoomRegion.queryXStart === 0 && 768 zoomRegion.queryXEnd === allRootsCumulativeValue 769 ? 'NORMAL' 770 : 'PARTIAL', 771 }); 772 773 const zoomQueryWidth = zoomRegion.queryXEnd - zoomRegion.queryXStart; 774 for (let i = 0; i < nodes.length; i++) { 775 const {id, parentId, depth, xStart: qXStart, xEnd: qXEnd} = nodes[i]; 776 assertTrue(depth !== 0); 777 778 const depthMatchingZoom = isDepthMatchingZoom(depth, zoomRegion); 779 if ( 780 depthMatchingZoom && 781 (qXEnd <= zoomRegion.queryXStart || qXStart >= zoomRegion.queryXEnd) 782 ) { 783 continue; 784 } 785 const queryXPerPx = depthMatchingZoom 786 ? zoomQueryWidth / canvasWidth 787 : allRootsCumulativeValue / canvasWidth; 788 const relativeXStart = depthMatchingZoom 789 ? qXStart - zoomRegion.queryXStart 790 : qXStart; 791 const relativeXEnd = depthMatchingZoom 792 ? qXEnd - zoomRegion.queryXStart 793 : qXEnd; 794 const relativeWidth = relativeXEnd - relativeXStart; 795 796 const x = Math.max(0, relativeXStart) / queryXPerPx; 797 const y = NODE_HEIGHT * (depth - minDepth); 798 const width = depthMatchingZoom 799 ? Math.min(relativeWidth, zoomQueryWidth) / queryXPerPx 800 : relativeWidth / queryXPerPx; 801 const state = computeState(qXStart, qXEnd, zoomRegion, depthMatchingZoom); 802 803 if (width < MIN_PIXEL_DISPLAYED) { 804 const parentChildMergeKey = `${parentId}_${depth}`; 805 const mergedXKey = `${id}_${depth > 0 ? depth + 1 : depth - 1}`; 806 const childMergedIdx = keyToChildMergedIdx.get(parentChildMergeKey); 807 if (childMergedIdx !== undefined) { 808 const r = renderNodes[childMergedIdx]; 809 const mergedWidth = isDepthMatchingZoom(depth, zoomRegion) 810 ? Math.min(qXEnd - r.source.queryXStart, zoomQueryWidth) / queryXPerPx 811 : (qXEnd - r.source.queryXStart) / queryXPerPx; 812 renderNodes[childMergedIdx] = { 813 ...r, 814 width: Math.max(mergedWidth, MIN_PIXEL_DISPLAYED), 815 source: { 816 ...(r.source as MergedSource), 817 queryXEnd: qXEnd, 818 }, 819 }; 820 mergedKeyToX.set(mergedXKey, r.x); 821 continue; 822 } 823 const mergedX = mergedKeyToX.get(`${parentId}_${depth}`) ?? x; 824 renderNodes.push({ 825 x: mergedX, 826 y, 827 width: Math.max(width, MIN_PIXEL_DISPLAYED), 828 source: { 829 kind: 'MERGED', 830 queryXStart: qXStart, 831 queryXEnd: qXEnd, 832 type: depth > 0 ? 'BELOW_ROOT' : 'ABOVE_ROOT', 833 }, 834 state, 835 }); 836 keyToChildMergedIdx.set(parentChildMergeKey, renderNodes.length - 1); 837 mergedKeyToX.set(mergedXKey, mergedX); 838 continue; 839 } 840 renderNodes.push({ 841 x, 842 y, 843 width, 844 source: { 845 kind: 'NODE', 846 queryXStart: qXStart, 847 queryXEnd: qXEnd, 848 queryIdx: i, 849 type: depth > 0 ? 'BELOW_ROOT' : 'ABOVE_ROOT', 850 }, 851 state, 852 }); 853 } 854 return renderNodes; 855} 856 857function isDepthMatchingZoom(depth: number, zoomRegion: ZoomRegion): boolean { 858 assertTrue( 859 depth !== 0, 860 'Handling zooming root not possible in this function', 861 ); 862 return ( 863 (depth > 0 && zoomRegion.type === 'BELOW_ROOT') || 864 (depth < 0 && zoomRegion.type === 'ABOVE_ROOT') 865 ); 866} 867 868function computeState( 869 qXStart: number, 870 qXEnd: number, 871 zoomRegion: ZoomRegion, 872 isDepthMatchingZoom: boolean, 873) { 874 if (!isDepthMatchingZoom) { 875 return 'NORMAL'; 876 } 877 if (qXStart === zoomRegion.queryXStart && qXEnd === zoomRegion.queryXEnd) { 878 return 'SELECTED'; 879 } 880 if (qXStart < zoomRegion.queryXStart || qXEnd > zoomRegion.queryXEnd) { 881 return 'PARTIAL'; 882 } 883 return 'NORMAL'; 884} 885 886function isIntersecting( 887 needleX: number | undefined, 888 needleY: number | undefined, 889 {x, y, width}: RenderNode, 890) { 891 if (needleX === undefined || needleY === undefined) { 892 return false; 893 } 894 return ( 895 needleX >= x && 896 needleX < x + width && 897 needleY >= y && 898 needleY < y + NODE_HEIGHT 899 ); 900} 901 902function displaySize(totalSize: number, unit: string): string { 903 if (unit === '') return totalSize.toLocaleString(); 904 if (totalSize === 0) return `0 ${unit}`; 905 let step: number; 906 let units: string[]; 907 switch (unit) { 908 case 'B': 909 step = 1024; 910 units = ['B', 'KiB', 'MiB', 'GiB']; 911 break; 912 case 'ns': 913 step = 1000; 914 units = ['ns', 'us', 'ms', 's']; 915 break; 916 default: 917 step = 1000; 918 units = [unit, `K${unit}`, `M${unit}`, `G${unit}`]; 919 break; 920 } 921 const unitsIndex = Math.min( 922 Math.trunc(Math.log(totalSize) / Math.log(step)), 923 units.length - 1, 924 ); 925 const pow = Math.pow(step, unitsIndex); 926 const result = totalSize / pow; 927 const resultString = 928 totalSize % pow === 0 ? result.toString() : result.toFixed(2); 929 return `${resultString} ${units[unitsIndex]}`; 930} 931 932function displayPercentage(size: number, totalSize: number): string { 933 if (totalSize === 0) { 934 return `[NULL]%`; 935 } 936 return `${((size / totalSize) * 100.0).toFixed(2)}%`; 937} 938 939function updateState(state: FlamegraphState, filter: string): FlamegraphState { 940 const lwr = filter.toLowerCase(); 941 if (lwr.startsWith('ss: ') || lwr.startsWith('show stack: ')) { 942 return addFilter(state, { 943 kind: 'SHOW_STACK', 944 filter: filter.split(': ', 2)[1], 945 }); 946 } else if (lwr.startsWith('hs: ') || lwr.startsWith('hide stack: ')) { 947 return addFilter(state, { 948 kind: 'HIDE_STACK', 949 filter: filter.split(': ', 2)[1], 950 }); 951 } else if (lwr.startsWith('sff: ') || lwr.startsWith('show from frame: ')) { 952 return addFilter(state, { 953 kind: 'SHOW_FROM_FRAME', 954 filter: filter.split(': ', 2)[1], 955 }); 956 } else if (lwr.startsWith('hf: ') || lwr.startsWith('hide frame: ')) { 957 return addFilter(state, { 958 kind: 'HIDE_FRAME', 959 filter: filter.split(': ', 2)[1], 960 }); 961 } else if (lwr.startsWith('p:') || lwr.startsWith('pivot: ')) { 962 return { 963 ...state, 964 view: {kind: 'PIVOT', pivot: filter.split(': ', 2)[1]}, 965 }; 966 } 967 return addFilter(state, { 968 kind: 'SHOW_STACK', 969 filter: filter, 970 }); 971} 972 973function toTags(state: FlamegraphState): ReadonlyArray<string> { 974 const toString = (x: FlamegraphFilter) => { 975 switch (x.kind) { 976 case 'HIDE_FRAME': 977 return 'Hide Frame: ' + x.filter; 978 case 'HIDE_STACK': 979 return 'Hide Stack: ' + x.filter; 980 case 'SHOW_FROM_FRAME': 981 return 'Show From Frame: ' + x.filter; 982 case 'SHOW_STACK': 983 return 'Show Stack: ' + x.filter; 984 } 985 }; 986 const filters = state.filters.map((x) => toString(x)); 987 return filters.concat( 988 state.view.kind === 'PIVOT' ? ['Pivot: ' + state.view.pivot] : [], 989 ); 990} 991 992function addFilter( 993 state: FlamegraphState, 994 filter: FlamegraphFilter, 995): FlamegraphState { 996 return { 997 ...state, 998 filters: state.filters.concat([filter]), 999 }; 1000} 1001 1002function generateColor(name: string, greyed: boolean, hovered: boolean) { 1003 if (greyed) { 1004 return `hsl(0deg, 0%, ${hovered ? 85 : 80}%)`; 1005 } 1006 if (name === 'unknown' || name === 'root') { 1007 return `hsl(0deg, 0%, ${hovered ? 78 : 73}%)`; 1008 } 1009 let x = 0; 1010 for (let i = 0; i < name.length; ++i) { 1011 x += name.charCodeAt(i) % 64; 1012 } 1013 return `hsl(${x % 360}deg, 45%, ${hovered ? 78 : 73}%)`; 1014} 1015