Canvas-граф коммитов: виртуализация 100k узлов без лагов

Граф коммитов — центральный UI в любом Git-клиенте. Но если репозиторий содержит 50k+ коммитов (а для зрелых проектов это норма), стандартные подходы с DOM или SVG не работают: тысячи DOM-узлов = freezes при скролле.

Почему не DOM

Первая версия GitBor рисовала граф через <div> + абсолютное позиционирование. На 500 коммитах — нормально. На 5000 — скролл начинал тормозить. На 20000 — браузер отказывался рендерить.

Причина: DOM-узлы дорогие. Каждый <div> это объект в памяти, участвующий в layout, paint и composite. Рендерить 20000 div'ов — это просить GPU перерисовывать 20000 слоёв при каждом фрейме скролла.

Canvas 2D + виртуализация

Решение — Canvas 2D с виртуализацией. Рисуем только то, что видно:

class CommitGraphRenderer {
  private visibleRange: { startY: number; endY: number };
  private commitHeight = 32;

  render(ctx: CanvasRenderingContext2D, commits: CommitNode[]) {
    const startIdx = Math.floor(this.visibleRange.startY / this.commitHeight);
    const endIdx = Math.ceil(this.visibleRange.endY / this.commitHeight);

    for (let i = startIdx; i <= Math.min(endIdx, commits.length - 1); i++) {
      this.drawCommit(ctx, commits[i], i);
    }
  }
}

Независимо от общего количества коммитов, на каждом фрейме рисуется максимум 30-40 (то, что помещается в viewport).

Layout-алгоритм

Самая сложная часть — расположение веток по горизонтали. Git-граф это DAG (направленный ациклический граф). Нужно:

Определить «дорожки» (lanes) для каждой ветки
Минимизировать пересечения рёбер
Сохранить компактность

Алгоритм работает инкрементально: при подгрузке новых коммитов пересчитываются только новые lanes, существующие не трогаются.

type CommitNode = {
  hash: string;
  parents: string[];
  lane: number;
  y: number;
  color: string;
};

function assignLanes(commits: CommitNode[]): void {
  const activeLanes: Map<string, number> = new Map();
  let nextLane = 0;

  for (const commit of commits) {
    if (activeLanes.has(commit.hash)) {
      commit.lane = activeLanes.get(commit.hash)!;
      activeLanes.delete(commit.hash);
    } else {
      commit.lane = nextLane++;
    }

    for (let i = 0; i < commit.parents.length; i++) {
      if (!activeLanes.has(commit.parents[i])) {
        activeLanes.set(commit.parents[i], i === 0 ? commit.lane : nextLane++);
      }
    }
  }
}

Hit-testing

Canvas — это пиксели, не DOM-элементы. Клик по коммиту = нужен свой hit-test:

function hitTest(x: number, y: number, commits: CommitNode[]): CommitNode | null {
  const idx = Math.floor(y / COMMIT_HEIGHT);
  if (idx < 0 || idx >= commits.length) return null;

  const commit = commits[idx];
  const cx = LANE_WIDTH * commit.lane + LANE_WIDTH / 2;
  const cy = idx * COMMIT_HEIGHT + COMMIT_HEIGHT / 2;

  const dist = Math.sqrt((x - cx) ** 2 + (y - cy) ** 2);
  return dist <= NODE_RADIUS ? commit : null;
}

Рёбра

Рёбра между коммитами рисуются bezier-кривыми. Merge-коммиты (2+ родителей) рисуют дополнительные линии к побочным родителям. Цвет ребра совпадает с цветом дорожки.

Результат

100k коммитов: скролл 60fps
Первый рендер: <16ms (один фрейм)
Память: ~40MB на 100k (только данные, Canvas буфер фиксирован)
Интерактивность: hover, click, context menu, selection — всё через hit-test

Для сравнения: GitHub Desktop на том же репозитории (Linux kernel, ~1.2M коммитов) показывает только последние 1000 и не рисует граф. GitKraken рисует, но тормозит после 10k.