火焰图是怎么画出来的？Pyroscope源码解析之火焰图

--- src
 |--- convert                            ->  一些工具、转换方法，包含diff两个Profile，flamebearer转换为树的方法等
 |--- fitMode                            ->  火焰图搭配的Table每一行的行内排序模式，分为Head First和Tail First两种
 |--- FlameGraph                         ->  火焰图主要文件夹
 | |--- FlameGraphComponent              ->  火焰图组件主要文件夹
 | | |--- ...
 | | |--- color.ts                       ->  火焰图配色哈希策略以及Diff线性渐变配色逻辑
 | | |--- colorPalette.ts                ->  火焰图配色调色盘
 | | |--- constants.ts                   ->  火焰图canvas显示全局配置，比如每一个bar的宽度、之间的间距等
 | | |--- ContextMenu.tsx                ->  右键火焰图弹出的Menu组件
 | | |--- ContextMenuHighlight.tsx       ->  为火焰图中被右键点中（呼出ContextMenu）的bar提供高亮效果
 | | |--- DiffLegend.tsx                 ->  火焰图Diff的调色盘配置（默认和色盲模式）中间的色条组件
 | | |--- DiffLegendPaletteDropdown.tsx  ->  火焰图Diff的调色盘配置的下拉框组件
 | | |--- Flamegraph_render.ts           ->  火焰图核心绘图渲染代码，基于flamebarear，包含canvas的绘图逻辑、聚焦逻辑（zoom）、折叠逻辑（collapse）、高亮联动逻辑
 | | |--- Flamegraph.ts                  ->  火焰图核心类，驱动Flamegraph_render，并且包含所有的组件操作逻辑实现，适配flamebarear数据结构在调用Stack中的二分搜索（xyToBarIndex），实现了与canvas配合紧密的数据可控组件
 | | |--- Header.tsx                     ->  火焰图标题组件，主要是根据unit换title，如果是Diff则展示DiffLegendPaletteDropdown
 | | |--- Highlight.tsx                  ->  火焰图高亮润色，为canvas设置EventListener监听鼠标事件并添加/移除火焰图bar高亮
 | | |--- index.tsx                      ->  火焰图入口组件，将其他相关组件接入（ContextMenu、Tooltip、Header等），封装调用Flamegraph的xyToData逻辑，传给其他子组件
 | | |--- LogoLink.tsx                   ->  Pyroscope的svg logo组件
 | | |--- murmur3.ts                     ->  MurmurHash3 哈希算法，可以将任意长度的数据映射为固定长度的哈希值，用于火焰图中相似调用栈层的相近颜色显示
 | | |--- testData.ts                    ->  火焰图样例数据格式，包含SimpleTree、ComplexTree、DiffTree
 | | |--- utils.ts                       ->  计算Diff时的两部分占比比率的辅助方法
 | | |--- viewTypes.ts                   ->  火焰图的显示模式，包含'flamegraph' | 'both' | 'table' | 'sandwich'
 | |--- decode.ts                        ->  在火焰图挂载/改变/covert的时候执行其中的decode方法，将原始数据结构的level进行二次运算
 | |--- FlameGraphRenderer.tsx           ->  火焰图全功能的入口，包含Toolbar、3种形态（表格、火焰图、三明治）
 |--- format                             ->  单位格式化工具文件夹
 | |--- format.ts                        ->  不同unit的Formatter也不一样，大致分为Duration、Objects、Bytes、Nanoseconds这几种Formatter，在Tooltip和表格中会用到
 |--- Tooltip                            ->  hover时出现的框
 | |--- ...
 | |--- FlamegraphTooltip.tsx            ->  用于火焰图的Tooltip组件，通过xyToData获取bar数据，并通过Formatter展示
 | |--- TableTooltip.tsx                 ->  用于表格的Tooltip组件，通过表格的数据回调方法获取数据，并通过Formatter展示
 | |--- Tooltip.tsx                      ->  Tooltip组件具体实现，通过baselineDataExpression判断hover类型是火焰图还是表格
 |--- FlamegraphRenderer.tsx             ->  FlameGraph/FlameGraphRenderer.tsx的包装
 |--- index.tsx                          ->  暴露Flamegraph等组件
 |--- ProfilerTable.tsx                  ->  火焰图表格的实现，包括singleRow和DoubleRow（Diff视图）的两种展现
 |--- search.ts                          ->  搜索工具类，判断bar名称是否和搜索内容一致
 |--- SharedQueryInput.tsx               ->  搜索框功能实现
 |--- Toolbar.tsx                        ->  火焰图控制bar的实现，可以切换视图和排序等

--- src
 |--- decode.ts        ->  TODO:理想情况下，这应该被移动到 FlamegraphRenderer 组件中，但是因为现在它需要太多的改变
 |--- flamebearer.ts   ->  老版本的火焰图数据结构
 |--- groups.ts        ->  火焰图主要文件夹
 |--- index.ts         ->  暴露索引文件
 |--- profile.ts       ->  新版本的火焰图数据结构（实际上本质是一样的，新版本用zod驱动）
 |--- spyName.ts       ->  不同语言的spy的相关常量与数据结构定义
 |--- trace.ts         ->  Trace相关的Schema定义
 |--- units.ts         ->  unit相关常量与数据结构定义

const SimpleTree = {
  version: 1,
  flamebearer: {
    names: [
      'total',
      'runtime.mcall',
      'runtime.park_m',
      'runtime.schedule',
      'runtime.resetspinning',
      'runtime.wakep',
      'runtime.startm',
      'runtime.notewakeup',
      'runtime.semawakeup',
      'runtime.pthread_cond_signal',
      'runtime.findrunnable',
      'runtime.netpoll',
      'runtime.kevent',
      'runtime.main',
      'main.main',
      'github.com/pyroscope-io/client/pyroscope.TagWrapper',
      'runtime/pprof.Do',
      'github.com/pyroscope-io/client/pyroscope.TagWrapper.func1',
      'main.main.func1',
      'main.slowFunction',
      'main.slowFunction.func1',
      'main.work',
      'runtime.asyncPreempt',
      'main.fastFunction',
      'main.fastFunction.func1',
    ],
    levels: [
      [0, 609, 0, 0],
      [0, 606, 0, 13, 0, 3, 0, 1],
      [0, 606, 0, 14, 0, 3, 0, 2],
      [0, 606, 0, 15, 0, 3, 0, 3],
      [0, 606, 0, 16, 0, 1, 0, 10, 0, 2, 0, 4],
      [0, 606, 0, 17, 0, 1, 0, 11, 0, 2, 0, 5],
      [0, 606, 0, 18, 0, 1, 1, 12, 0, 2, 0, 6],
      [0, 100, 0, 23, 0, 506, 0, 19, 1, 2, 0, 7],
      [0, 100, 0, 15, 0, 506, 0, 16, 1, 2, 0, 8],
      [0, 100, 0, 16, 0, 506, 0, 20, 1, 2, 2, 9],
      [0, 100, 0, 17, 0, 506, 493, 21],
      [0, 100, 0, 24, 493, 13, 13, 22],
      [0, 100, 97, 21],
      [97, 3, 3, 22],
    ],
    numTicks: 609,
    maxSelf: 493,
  },
  metadata: {
    appName: 'simple.golang.app.cpu',
    name: 'simple.golang.app.cpu 2022-09-06T12:16:31Z',
    startTime: 1662466591,
    endTime: 1662470191,
    query: 'simple.golang.app.cpu{}',
    maxNodes: 1024,
    format: 'single' as const,
    sampleRate: 100,
    spyName: 'gospy' as const,
    units: 'samples' as const,
  }
};

"levels": [
  [0, 20464695, 0, 0, 22639351, 0, 0],
  [
    0, 1573488, 0, 0, 0, 0, 1, 0, 524336, 0, 0, 524336, 0, 2, 0, 1049728, 0,
    0, 524864, 0, 3, 0, 3149185, 0, 0, 3674049, 0, 4, 0, 13643094, 0, 0,
    17391238, 0, 5, 0, 524864, 0, 0, 524864, 0, 6
  ],
  [
    0, 1573488, 0, 0, 0, 0, 7, 0, 524336, 524336, 0, 524336, 524336, 8, 0,
    1049728, 0, 0, 524864, 0, 9, 0, 3149185, 0, 0, 3674049, 0, 10, 0,
    13643094, 0, 0, 17391238, 0, 11, 0, 524864, 0, 0, 524864, 0, 12
  ],
  [
    0, 1573488, 0, 0, 0, 0, 13, 524336, 1049728, 0, 524336, 524864, 0, 14,
    0, 3149185, 0, 0, 3674049, 0, 15, 0, 524361, 524361, 0, 524360, 524360,
    16, 0, 2146687, 0, 0, 5366719, 0, 17, 0, 528394, 528394, 0, 528394,
    528394, 18, 0, 0, 0, 0, 524292, 0, 19, 0, 9387757, 0, 0, 9397105, 0, 20,
    0, 525440, 0, 0, 525440, 0, 21, 0, 0, 0, 0, 524928, 0, 22, 0, 530455, 0,
    0, 0, 0, 23, 0, 524864, 0, 0, 524864, 0, 24
  ],
  [
    0, 1573488, 1573488, 0, 0, 0, 25, 524336, 1049728, 0, 524336, 524864, 0,
    26, 0, 3149185, 0, 0, 3674049, 0, 14, 524361, 2146687, 0, 524360,
    5366719, 0, 27, 528394, 0, 0, 528394, 524292, 0, 28, 0, 9387757, 695248,
    0, 9397105, 695248, 29, 0, 525440, 0, 0, 525440, 0, 30, 0, 0, 0, 0,
    524928, 0, 31, 0, 530455, 0, 0, 0, 0, 32, 0, 524864, 0, 0, 524864, 0, 33
  ],
  [
    2097824, 1049728, 0, 524336, 524864, 0, 34, 0, 3149185, 0, 0, 3674049,
    0, 26, 524361, 2146687, 0, 524360, 5366719, 0, 35, 528394, 0, 0, 528394,
    524292, 0, 36, 695248, 8692509, 789507, 695248, 8701857, 526338, 37, 0,
    525440, 0, 0, 525440, 0, 38, 0, 0, 0, 0, 524928, 0, 39, 0, 530455, 0, 0,
    0, 0, 40, 0, 524864, 0, 0, 524864, 0, 14
  ],
  [
    2097824, 1049728, 0, 524336, 524864, 0, 41, 0, 3149185, 0, 0, 3674049,
    0, 34, 524361, 2146687, 0, 524360, 5366719, 0, 42, 528394, 0, 0, 528394,
    524292, 0, 43, 1484755, 7903001, 7903001, 1221586, 8175519, 8175519, 44,
    0, 525440, 525440, 0, 525440, 525440, 45, 0, 0, 0, 0, 524928, 0, 46, 0,
    530455, 0, 0, 0, 0, 47, 0, 524864, 0, 0, 524864, 0, 48
  ],
  [
    2097824, 1049728, 0, 524336, 524864, 0, 49, 0, 3149185, 0, 0, 3674049,
    0, 41, 524361, 2146687, 0, 524360, 5366719, 0, 50, 528394, 0, 0, 528394,
    524292, 0, 51, 9913197, 0, 0, 9922545, 524928, 0, 52, 0, 530455, 0, 0,
    0, 0, 53, 0, 524864, 0, 0, 524864, 0, 54
  ],
  [
    2097824, 1049728, 1049728, 524336, 524864, 524864, 55, 0, 3149185, 0, 0,
    3674049, 0, 49, 524361, 2146687, 2146687, 524360, 5366719, 5366719, 56,
    528394, 0, 0, 528394, 524292, 524292, 57, 9913197, 0, 0, 9922545,
    524928, 0, 58, 0, 530455, 530455, 0, 0, 0, 59, 0, 524864, 0, 0, 524864,
    0, 41
  ],
  [
    3147552, 3149185, 3149185, 1049200, 3674049, 3674049, 55, 13112639, 0,
    0, 16866310, 524928, 0, 60, 530455, 524864, 0, 0, 524864, 0, 49
  ],
  [
    19409376, 0, 0, 21589559, 524928, 524928, 61, 530455, 524864, 524864, 0,
    524864, 524864, 55
  ]
]

export type Flamebearer = {
  /**
   * List of names
   */
  names: string[];
  /**
   * List of level
   *
   * This is NOT the same as in the flamebearer
   * that we receive from the server.
   * As in there are some transformations required
   * (see deltaDiffWrapper)
   */
  levels: number[][];
  numTicks: number;
  maxSelf: number;

  /**
   * Sample Rate, used in text information
   */
  sampleRate: number;
  units: Units;

  spyName: SpyName;
  // format: 'double' | 'single';
  //  leftTicks?: number;
  //  rightTicks?: number;
} & addTicks;

export type addTicks =
  | { format: 'double'; leftTicks: number; rightTicks: number }
  | { format: 'single' };

export const singleFF = {
  format: 'single' as const,
  jStep: 4,
  jName: 3,
  getBarOffset: (level: number[], j: number) => level[j],
  getBarTotal: (level: number[], j: number) => level[j + 1],
  getBarTotalDiff: (level: number[], j: number) => 0,
  getBarSelf: (level: number[], j: number) => level[j + 2],
  getBarSelfDiff: (level: number[], j: number) => 0,
  getBarName: (level: number[], j: number) => level[j + 3],
};

export const doubleFF = {
  format: 'double' as const,
  jStep: 7,
  jName: 6,
  getBarOffset: (level: number[], j: number) => level[j] + level[j + 3],
  getBarTotal: (level: number[], j: number) => level[j + 4] + level[j + 1],
  getBarTotalLeft: (level: number[], j: number) => level[j + 1],
  getBarTotalRght: (level: number[], j: number) => level[j + 4],
  getBarTotalDiff: (level: number[], j: number) => {
    return level[j + 4] - level[j + 1];
  },
  getBarSelf: (level: number[], j: number) => level[j + 5] + level[j + 2],
  getBarSelfLeft: (level: number[], j: number) => level[j + 2],
  getBarSelfRght: (level: number[], j: number) => level[j + 5],
  getBarSelfDiff: (level: number[], j: number) => level[j + 5] - level[j + 2],
  getBarName: (level: number[], j: number) => level[j + 6],
};

import Maybe from 'true-myth/maybe';

// Construct a `Just` where you have a value to use, and the function accepts
// a `Maybe`.
const aKnownNumber = Maybe.just(12);

// Construct a `Nothing` where you don't have a value to use, but the
// function requires a value (and accepts a `Maybe`).
const aKnownNothing = Maybe.nothing<string>();

// Construct a `Maybe` where you don't know whether the value will exist or
// not, using `of`.
type WhoKnows = { mightBeAThing?: boolean[] };

const whoKnows: WhoKnows = {};
const wrappedWhoKnows = Maybe.of(whoKnows.mightBeAThing);
console.log(toString(wrappedWhoKnows)); // Nothing

const whoElseKnows: WhoKnows = { mightBeAThing: [true, false] };
const wrappedWhoElseKnows = Maybe.of(whoElseKnows.mightBeAThing);
console.log(toString(wrappedWhoElseKnows)); // "Just(true,false)"
import { isVoid } from 'true-myth/utils';
import Maybe, { Just, Nothing } from 'true-myth/maybe';

// Construct a `Just` where you have a value to use, and the function accepts
// a `Maybe`.
const aKnownNumber = new Just(12);

// Once the item is constructed, you can apply methods directly on it.
const fromMappedJust = aKnownNumber.map((x) => x * 2).unwrapOr(0);
console.log(fromMappedJust); // 24

// Construct a `Nothing` where you don't have a value to use, but the
// function requires a value (and accepts a `Maybe<string>`).
const aKnownNothing = new Nothing();

// The same operations will behave safely on a `Nothing` as on a `Just`:
const fromMappedNothing = aKnownNothing.map((x) => x * 2).unwrapOr(0);
console.log(fromMappedNothing); // 0

// Construct a `Maybe` where you don't know whether the value will exist or
// not, using `isVoid` to decide which to construct.
type WhoKnows = { mightBeAThing?: boolean[] };

const whoKnows: WhoKnows = {};
const wrappedWhoKnows = !isVoid(whoKnows.mightBeAThing)
  ? new Just(whoKnows.mightBeAThing)
  : new Nothing();

console.log(wrappedWhoKnows.toString()); // Nothing

const whoElseKnows: WhoKnows = { mightBeAThing: [true, false] };
const wrappedWhoElseKnows = !isVoid(whoElseKnows.mightBeAThing)
  ? new Just(whoElseKnows.mightBeAThing)
  : new Nothing();

console.log(wrappedWhoElseKnows.toString()); // "Just(true,false)"

const onClick = (e: React.MouseEvent<HTMLCanvasElement>) => {
  const opt = getFlamegraph().xyToBar(
    e.nativeEvent.offsetX,
    e.nativeEvent.offsetY
  );
  // opt 是根据xy位置取出的 Maybe<XYWithinBounds> 对象后，再根据一系列xyToData方法（后文详细介绍）构造了包含index、position、data的bar
  opt.match({
    // 点击在canvas中不合理的位置，就什么都不做
    Nothing: () => {},
    //  如果是合理的位置，则取出bar数据（信息包含index、position、data）
    Just: (bar) => {
      // zoom是当前已经被放大的 Maybe<Node> 对象（不一定是opt），放大的意思是左键点击火焰图的那个操作带来的效果
      zoom.match({
        // 如果当前不存在zoom，则在当前位置（opt处）执行zoom
        Nothing: () => {
          onZoom(opt);
        },
        // 如果当前存在已经被放大的节点z，则取出bar数据
        Just: (z) => {
          // 判断opt和zoom是否是相同的index
          if (bar.i === z.i && bar.j === z.j) {
            // 如果是，则取消被放大，复原
            onZoom(Maybe.nothing());
          } else {
            // 如果不是，则对这个当前被点击的opt进行zoom操作
            onZoom(opt);
          }
        },
      });
    },
  });
};

private xyToBarIndex(x: number, y: number) {
  if (x < 0 || y < 0) {
    throw new Error(`x and y must be bigger than 0. x = ${x}, y = ${y}`);
  }

  // 意思是点击了聚焦模式下的顶上的bar，或者是非聚焦模式下的Total，则返回{ i: 0, j: 0 }
  if (this.isFocused() && y <= BAR_HEIGHT) {
    return { i: 0, j: 0 };
  }

  // 当进行collapse的时候（聚焦操作），最顶上会有一个虚拟collapsed节点，因此这里需要减一下
  const computedY = this.isFocused() ? y - BAR_HEIGHT : y;

  const compensatedFocusedY = this.focusedNode.mapOrElse(
    () => 0,
    (node) => {
      return node.i <= 0 ? 0 : node.i;
    }
  );

  // 把它当做一组if-else即可
  const compensation = this.zoom.match({
    Just: () => {
      return this.focusedNode.match({
        Just: () => {
          // 有focus、也有zoom，以focus为主
          return compensatedFocusedY;
        },
        Nothing: () => {
          // 只有zoom
          return 0;
        },
      });
    },

    Nothing: () => {
      return this.focusedNode.match({
        Just: () => {
          // 只有focus
          return compensatedFocusedY;
        },
        Nothing: () => {
          // 既没有focus，也没有zoom
          return 0;
        },
      });
    },
  });

  // 可以根据以上信息，定位i的位置
  const i = Math.floor(computedY / PX_PER_LEVEL) + compensation;
  if (i >= 0 && i < this.flamebearer.levels.length) {
    const level = this.flamebearer.levels[i];
    if (!level) {
      throw new Error(`Could not find level: '${i}'`);
    }
    // j的位置，用到了一个二分查找的算法去找
    const j = this.binarySearchLevel(x, level);
    return { i, j };
  }
  return { i: 0, j: 0 };
}

// binary search of a block in a stack level
private binarySearchLevel(x: number, level: number[]) {
  const { ff } = this;
  let i = 0;
  let j = level.length - ff.jStep;

  while (i <= j) {
    /* eslint-disable-next-line no-bitwise */
    const m = ff.jStep * ((i / ff.jStep + j / ff.jStep) >> 1);
    const x0 = this.tickToX(ff.getBarOffset(level, m));
    const x1 = this.tickToX(
      ff.getBarOffset(level, m) + ff.getBarTotal(level, m)
    );

    if (x0 <= x && x1 >= x) {
      return x1 - x0 > COLLAPSE_THRESHOLD ? m : -1;
    }
    if (x0 > x) {
      j = m - ff.jStep;
    } else {
      i = m + ff.jStep;
    }
  }
  return -1;
}

private xyToBarPosition = (xy: XYWithinBounds) => {
    const { ff } = this;
    const { i, j } = this.xyToBarIndex(xy.x, xy.y);

    const topLevel = this.focusedNode.mapOrElse(
      () => 0,
      (node) => (node.i < 0 ? 0 : node.i - 1)
    );

    const level = this.flamebearer.levels[i];
    if (!level) {
      throw new Error(`Could not find level: '${i}'`);
    }
    const posX = Math.max(this.tickToX(ff.getBarOffset(level, j)), 0);

    // lower bound is 0
    const posY = Math.max((i - topLevel) * PX_PER_LEVEL, 0);

    const sw = Math.min(
      this.tickToX(ff.getBarOffset(level, j) + ff.getBarTotal(level, j)) - posX,
      this.getCanvasWidth()
    );

    return {
      x: posX,
      y: posY,
      width: sw,
    };
  };

  private xyToBarData = (xy: XYWithinBounds) => {
    const { i, j } = this.xyToBarIndex(xy.x, xy.y);
    const level = this.flamebearer.levels[i];
    if (!level) {
      throw new Error(`Could not find level: '${i}'`);
    }

    switch (this.flamebearer.format) {
      case 'single': {
        const ff = singleFF;

        return {
          format: 'single' as const,
          name: this.flamebearer.names[ff.getBarName(level, j)],
          self: ff.getBarSelf(level, j),
          offset: ff.getBarOffset(level, j),
          total: ff.getBarTotal(level, j),
        };
      }
      case 'double': {
        const ff = doubleFF;

        return {
          format: 'double' as const,
          barTotal: ff.getBarTotal(level, j),
          totalLeft: ff.getBarTotalLeft(level, j),
          totalRight: ff.getBarTotalRght(level, j),
          totalDiff: ff.getBarTotalDiff(level, j),
          name: this.flamebearer.names[ff.getBarName(level, j)],
        };
      }

      default: {
        throw new Error(`Unsupported type`);
      }
    }
  };