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