Cache Breakpoint Planner — C# source

// Cache Breakpoint Planner — find the blocks a set of prompts share and
// place cache breakpoints where they pay.
//
// Language: C# (.NET 8, zero dependencies)
// Port of src/lib/cacheBreakpointPlanner.ts (the canonical TypeScript
// implementation). Field names stay camelCase to match the TS surface.
// Tool page: https://dev.cosmolabs.org/tools/cache-breakpoint-planner

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CosmoDev.CacheBreakpointPlanner;

public sealed record PromptSession(string Id, IReadOnlyList<string> Blocks);

/// <summary>Place the cache breakpoint AFTER this block index (0-based); -1 = terminal.</summary>
public sealed record Breakpoint(
    long AfterBlock,
    string Label,
    string Reason,
    long CachedTokens);

public sealed record PerSessionRow(
    string Id,
    long TotalTokens,
    long UniqueTokens,
    double CachedRatio);

/// <summary>The full plan: shared blocks, breakpoints, rows, savings.</summary>
public sealed record BreakpointPlan(
    IReadOnlyList<string> PrefixBlocks,
    long PrefixTokens,
    IReadOnlyList<string> SuffixBlocks,
    long SuffixTokens,
    IReadOnlyList<Breakpoint> Breakpoints,
    IReadOnlyList<PerSessionRow> PerSession,
    /// Estimated cost saving across the sessions vs no caching (0-1).
    double EstimatedSavings,
    IReadOnlyList<string> Warnings);

public static class CacheBreakpointPlanner
{
    /// <summary>Cached reads bill at ~0.1x — the saving on the cached share is ~90%.</summary>
    public const double CACHE_READ_DISCOUNT = 0.1;

    /// <summary>
    /// Plan cache breakpoints for a set of prompt sessions: find the common
    /// leading/trailing blocks across every session and place breakpoints
    /// where the cache pays.
    /// </summary>
    public static BreakpointPlan PlanBreakpoints(IReadOnlyList<PromptSession> sessions)
    {
        var warnings = new List<string>();
        var valid = sessions.Where(s => s.Blocks != null).ToList();

        if (valid.Count == 0)
        {
            return new BreakpointPlan(
                Array.Empty<string>(), 0, Array.Empty<string>(), 0,
                Array.Empty<Breakpoint>(), Array.Empty<PerSessionRow>(), 0.0,
                new[] { "No sessions given — paste at least two prompts to compare." });
        }
        if (valid.Count == 1)
        {
            warnings.Add("Only one session — a prefix needs at least two prompts to detect.");
        }

        // Common leading blocks by position.
        int shortest = valid.Min(s => s.Blocks.Count);
        int prefixEnd = 0;
        while (prefixEnd < shortest
               && valid.All(s => s.Blocks[prefixEnd] == valid[0].Blocks[prefixEnd]))
        {
            prefixEnd++;
        }

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

        var prefixBlocks = valid[0].Blocks.Take(prefixEnd).ToList();
        var suffixBlocks = suffixLen > 0
            ? valid[0].Blocks.Skip(valid[0].Blocks.Count - suffixLen).ToList()
            : new List<string>();
        long prefixTokens = Tok(string.Join("\n", prefixBlocks));
        long suffixTokens = Tok(string.Join("\n", suffixBlocks));

        var breakpoints = new List<Breakpoint>();
        if (prefixBlocks.Count > 0)
        {
            breakpoints.Add(new Breakpoint(
                prefixEnd - 1,
                "after the shared prefix",
                $"{prefixBlocks.Count} block(s) identical across every session — cache once, hit on every request.",
                prefixTokens));
        }
        if (suffixLen > 0)
        {
            breakpoints.Add(new Breakpoint(
                -1, // terminal: the shared tail sits at the end of each request
                "shared tail",
                $"{suffixLen} trailing block(s) also identical — extend the cache segment or accept the re-read.",
                suffixTokens));
        }
        if (breakpoints.Count == 0)
        {
            warnings.Add("No shared leading or trailing blocks — nothing to cache across these sessions.");
        }

        var perSession = valid.Select(s =>
        {
            long totalTokens = Tok(string.Join("\n", s.Blocks));
            long unique = Math.Max(totalTokens - prefixTokens - suffixTokens, 0);
            double cachedRatio = totalTokens > 0
                ? Math.Min((double)(prefixTokens + suffixTokens) / totalTokens, 1.0)
                : 0.0;
            return new PerSessionRow(s.Id, totalTokens, unique, cachedRatio);
        }).ToList();

        double avgTotal = perSession.Sum(p => (double)p.TotalTokens) / perSession.Count;
        double cachedShare = avgTotal > 0
            ? Math.Min((prefixTokens + suffixTokens) / avgTotal, 1.0)
            : 0.0;
        double estimatedSavings = cachedShare * (1 - CACHE_READ_DISCOUNT);

        return new BreakpointPlan(
            prefixBlocks, prefixTokens, suffixBlocks, suffixTokens,
            breakpoints, perSession, estimatedSavings, warnings);
    }

    /// <summary>
    /// The <c>type: 'prose'</c> path of the tokenEstimator, inlined: every
    /// non-empty line costs max(1, round(length / 4)) tokens; empty text is 0.
    /// </summary>
    private static long Tok(string text)
    {
        if (string.IsNullOrEmpty(text)) return 0;
        long tokens = 0;
        foreach (var line in text.Split('\n'))
        {
            if (line.Length > 0)
            {
                tokens += Math.Max(1, (long)Math.Round(line.Length / 4.0, MidpointRounding.AwayFromZero));
            }
        }
        return tokens;
    }
}