Cache Breakpoint Planner — Java source

// Cache Breakpoint Planner — find the blocks a set of prompts share and
// place cache breakpoints where they pay.
//
// Language: Java (17+, 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

import java.util.ArrayList;
import java.util.List;

public final class CacheBreakpointPlanner {

    /** Cached reads bill at ~0.1x — the saving on the cached share is ~90%. */
    public static final double CACHE_READ_DISCOUNT = 0.1;

    /** One prompt session: an id plus its ordered blocks. */
    public record PromptSession(String id, List<String> blocks) {}

    /** Place the cache breakpoint AFTER this block index (0-based); -1 = terminal. */
    public record Breakpoint(long afterBlock, String label, String reason, long cachedTokens) {}

    public record PerSessionRow(String id, long totalTokens, long uniqueTokens, double cachedRatio) {}

    /** The full plan: shared blocks, breakpoints, rows, savings. */
    public record BreakpointPlan(
            List<String> prefixBlocks,
            long prefixTokens,
            List<String> suffixBlocks,
            long suffixTokens,
            List<Breakpoint> breakpoints,
            List<PerSessionRow> perSession,
            /** Estimated cost saving across the sessions vs no caching (0-1). */
            double estimatedSavings,
            List<String> warnings) {}

    /**
     * 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.
     */
    public static BreakpointPlan planBreakpoints(List<PromptSession> sessions) {
        List<String> warnings = new ArrayList<>();
        List<PromptSession> valid = new ArrayList<>();
        for (PromptSession s : sessions) {
            if (s.blocks() != null) valid.add(s);
        }

        if (valid.isEmpty()) {
            return new BreakpointPlan(new ArrayList<>(), 0, new ArrayList<>(), 0,
                    new ArrayList<>(), new ArrayList<>(), 0.0,
                    List.of("No sessions given — paste at least two prompts to compare."));
        }
        if (valid.size() == 1) {
            warnings.add("Only one session — a prefix needs at least two prompts to detect.");
        }

        // Common leading blocks by position.
        int shortest = Integer.MAX_VALUE;
        for (PromptSession s : valid) shortest = Math.min(shortest, s.blocks().size());
        int prefixEnd = 0;
        while (prefixEnd < shortest) {
            boolean shared = true;
            for (PromptSession s : valid) {
                if (!s.blocks().get(prefixEnd).equals(valid.get(0).blocks().get(prefixEnd))) {
                    shared = false;
                    break;
                }
            }
            if (!shared) break;
            prefixEnd++;
        }

        // Common trailing blocks, matched from each session's own tail, never
        // overlapping the prefix.
        int suffixLen = 0;
        while (suffixLen < shortest - prefixEnd) {
            boolean shared = true;
            for (PromptSession s : valid) {
                String a = s.blocks().get(s.blocks().size() - 1 - suffixLen);
                String b = valid.get(0).blocks().get(
                        valid.get(0).blocks().size() - 1 - suffixLen);
                if (!a.equals(b)) {
                    shared = false;
                    break;
                }
            }
            if (!shared) break;
            suffixLen++;
        }

        List<String> prefixBlocks = new ArrayList<>(
                valid.get(0).blocks().subList(0, prefixEnd));
        List<String> suffixBlocks = suffixLen > 0
                ? new ArrayList<>(valid.get(0).blocks().subList(
                      valid.get(0).blocks().size() - suffixLen, valid.get(0).blocks().size()))
                : new ArrayList<>();
        long prefixTokens = tok(String.join("\n", prefixBlocks));
        long suffixTokens = tok(String.join("\n", suffixBlocks));

        List<Breakpoint> breakpoints = new ArrayList<>();
        if (!prefixBlocks.isEmpty()) {
            breakpoints.add(new Breakpoint(
                    prefixEnd - 1,
                    "after the shared prefix",
                    prefixBlocks.size() + " 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.isEmpty()) {
            warnings.add("No shared leading or trailing blocks — nothing to cache "
                    + "across these sessions.");
        }

        List<PerSessionRow> perSession = new ArrayList<>();
        for (PromptSession s : valid) {
            long totalTokens = tok(String.join("\n", s.blocks()));
            long unique = Math.max(totalTokens - prefixTokens - suffixTokens, 0);
            double cachedRatio = totalTokens > 0
                    ? Math.min(1.0, (double) (prefixTokens + suffixTokens) / totalTokens)
                    : 0.0;
            perSession.add(new PerSessionRow(s.id(), totalTokens, unique, cachedRatio));
        }

        double sum = 0.0;
        for (PerSessionRow p : perSession) sum += p.totalTokens();
        double avgTotal = perSession.isEmpty() ? 0.0 : sum / perSession.size();
        double cachedShare = avgTotal > 0
                ? Math.min(1.0, (prefixTokens + suffixTokens) / avgTotal)
                : 0.0;
        double estimatedSavings = cachedShare * (1.0 - CACHE_READ_DISCOUNT);

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

    /**
     * The {@code type: 'prose'} path of the tokenEstimator, inlined: every
     * non-empty line costs max(1, round(length / 4)) tokens; empty text is 0.
     */
    private static long tok(String text) {
        if (text == null || text.isEmpty()) return 0;
        long tokens = 0;
        for (String line : text.split("\n", -1)) {
            if (!line.isEmpty()) {
                tokens += Math.max(1, Math.round(line.length() / 4.0));
            }
        }
        return tokens;
    }

    private CacheBreakpointPlanner() {}
}