Cache Breakpoint Planner — JavaScript source

/**
 * Cache Breakpoint Planner — find the blocks a set of prompts share and place
 * cache breakpoints where they pay.
 * Port of src/lib/cacheBreakpointPlanner.ts
 *
 * Language: JavaScript (ES2022+, ES module; runs unmodified in Node 18+
 *           and modern browsers)
 * Source:   CosmoDev polyglot showcase port of the Cache Breakpoint Planner
 *           tool (slug: cache-breakpoint-planner), ported from
 *           src/lib/cacheBreakpointPlanner.ts (the canonical TypeScript
 *           implementation).
 * Tool page: https://dev.cosmolabs.org/tools/cache-breakpoint-planner
 * License:  display source — part of CosmoDev's polyglot tool pages.
 *
 * A session is a label plus an ordered list of prompt blocks (system, docs,
 * history turns, user ask…). The planner finds the blocks identical across
 * every session — a shared prefix at the front and a shared tail at the end —
 * and places cache breakpoints so everything stable is billed at the
 * cached-read rate on every request after the first. Token figures use the
 * tokenEstimator prose heuristic (4 characters per token, at least one per
 * non-empty line), inlined below so the file stays self-contained.
 */

/**
 * @typedef {{ id: string, blocks: string[] }} PromptSession
 * @typedef {{ afterBlock: number, label: string, reason: string, cachedTokens: number }} Breakpoint
 * @typedef {{ id: string, totalTokens: number, uniqueTokens: number, cachedRatio: number }} SessionTokens
 * @typedef {{
 *   prefixBlocks: string[], prefixTokens: number,
 *   suffixBlocks: string[], suffixTokens: number,
 *   breakpoints: Breakpoint[], perSession: SessionTokens[],
 *   estimatedSavings: number, warnings: string[],
 * }} BreakpointPlan
 */

/** Cached reads bill at ~0.1× — the saving on the cached share is ~90%. */
export const CACHE_READ_DISCOUNT = 0.1;

/**
 * Plan cache breakpoints for a set of prompt sessions.
 *
 * Sessions whose `blocks` is not an array are ignored (the TS lib filters
 * with `Array.isArray`); zero usable sessions yields an empty plan carrying
 * an explanatory warning. `estimatedSavings` is the share of the average
 * session that repeats, times the cached-read discount.
 * @param {readonly PromptSession[]} sessions
 * @returns {BreakpointPlan}
 */
export function planBreakpoints(sessions) {
  const warnings = [];
  const list = Array.isArray(sessions) ? sessions : [];
  const valid = list.filter((s) => s && Array.isArray(s.blocks));

  if (valid.length === 0) {
    return {
      prefixBlocks: [],
      prefixTokens: 0,
      suffixBlocks: [],
      suffixTokens: 0,
      breakpoints: [],
      perSession: [],
      estimatedSavings: 0,
      warnings: ['No sessions given — paste at least two prompts to compare.'],
    };
  }
  if (valid.length === 1) {
    warnings.push('Only one session — a prefix needs at least two prompts to detect.');
  }

  // Common leading blocks by position.
  const shortest = Math.min(...valid.map((s) => s.blocks.length));
  let prefixEnd = 0;
  while (
    prefixEnd < shortest &&
    valid.every((s) => s.blocks[prefixEnd] === valid[0].blocks[prefixEnd])
  ) {
    prefixEnd++;
  }

  // Common trailing blocks, matched from each session's own tail, never
  // overlapping the prefix.
  let suffixLen = 0;
  while (
    suffixLen < shortest - prefixEnd &&
    valid.every(
      (s) =>
        s.blocks[s.blocks.length - 1 - suffixLen] ===
        valid[0].blocks[valid[0].blocks.length - 1 - suffixLen],
    )
  ) {
    suffixLen++;
  }

  const prefixBlocks = valid[0].blocks.slice(0, prefixEnd);
  const suffixBlocks = suffixLen > 0 ? valid[0].blocks.slice(valid[0].blocks.length - suffixLen) : [];
  const prefixTokens = tok(prefixBlocks.join('\n'));
  const suffixTokens = tok(suffixBlocks.join('\n'));

  const breakpoints = [];
  if (prefixBlocks.length > 0) {
    breakpoints.push({
      afterBlock: prefixEnd - 1,
      label: 'after the shared prefix',
      reason: `${prefixBlocks.length} block(s) identical across every session — cache once, hit on every request.`,
      cachedTokens: prefixTokens,
    });
  }
  if (suffixLen > 0) {
    breakpoints.push({
      afterBlock: -1, // terminal: the shared tail sits at the end of each request
      label: 'shared tail',
      reason: `${suffixLen} trailing block(s) also identical — extend the cache segment or accept the re-read.`,
      cachedTokens: suffixTokens,
    });
  }
  if (breakpoints.length === 0) {
    warnings.push('No shared leading or trailing blocks — nothing to cache across these sessions.');
  }

  const perSession = valid.map((s) => {
    const totalTokens = tok(s.blocks.join('\n'));
    const uniqueTokens = Math.max(totalTokens - prefixTokens - suffixTokens, 0);
    return {
      id: s.id,
      totalTokens,
      uniqueTokens,
      cachedRatio: totalTokens > 0 ? Math.min((prefixTokens + suffixTokens) / totalTokens, 1) : 0,
    };
  });

  const avgTotal = perSession.reduce((sum, p) => sum + p.totalTokens, 0) / perSession.length;
  const cachedShare = avgTotal > 0 ? Math.min((prefixTokens + suffixTokens) / avgTotal, 1) : 0;

  return {
    prefixBlocks,
    prefixTokens,
    suffixBlocks,
    suffixTokens,
    breakpoints,
    perSession,
    estimatedSavings: cachedShare * (1 - CACHE_READ_DISCOUNT),
    warnings,
  };
}

/**
 * The `type: 'prose'` path of the tokenEstimator, inlined: every non-empty
 * line costs max(1, round(length / 4)) tokens, where length is JavaScript's
 * UTF-16 code-unit count. Empty text is 0.
 * @param {string} text
 * @returns {number}
 */
function tok(text) {
  if (!text) return 0;
  let tokens = 0;
  for (const line of text.split(/\r?\n/)) {
    if (line.trim() === '') continue;
    tokens += Math.max(1, Math.round(line.length / 4));
  }
  return tokens;
}