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++ (C++20, standard library only)
// Port of src/lib/cacheBreakpointPlanner.ts (the canonical TypeScript
// implementation). javascript.js in this set carries the same port.
// Tool page: https://dev.cosmolabs.org/tools/cache-breakpoint-planner

#include <algorithm>
#include <cmath>
#include <string>
#include <vector>

namespace cache_breakpoint_planner {

/// Cached reads bill at ~0.1x — the saving on the cached share is ~90%.
inline constexpr double kCacheReadDiscount = 0.1;

/// One prompt session: an id plus its ordered blocks.
struct PromptSession {
    std::string id;
    std::vector<std::string> blocks;
};

/// Place the cache breakpoint AFTER this block index (0-based).
/// -1 = terminal (the shared tail sits at the end of each request).
struct Breakpoint {
    long after_block;
    std::string label;
    std::string reason;
    long cached_tokens;
};

struct PerSessionRow {
    std::string id;
    long total_tokens;
    long unique_tokens;
    double cached_ratio;
};

/// The full plan: shared blocks, breakpoints, per-session rows, savings.
struct BreakpointPlan {
    std::vector<std::string> prefix_blocks;
    long prefix_tokens = 0;
    std::vector<std::string> suffix_blocks;
    long suffix_tokens = 0;
    std::vector<Breakpoint> breakpoints;
    std::vector<PerSessionRow> per_session;
    /// Estimated cost saving across the sessions vs no caching (0-1).
    double estimated_savings = 0.0;
    std::vector<std::string> warnings;
};

/// The `type: 'prose'` path of the tokenEstimator, inlined: every non-empty
/// line costs max(1, round(length / 4)) tokens; empty text is 0.
inline long tok(const std::string &text) {
    if (text.empty()) return 0;
    long tokens = 0;
    size_t start = 0;
    while (start <= text.size()) {
        size_t end = text.find('\n', start);
        if (end == std::string::npos) end = text.size();
        size_t len = end - start;
        if (len > 0) {
            long per = std::lround(static_cast<double>(len) / 4.0);
            tokens += std::max<long>(1, per);
        }
        if (end == text.size()) break;
        start = end + 1;
    }
    return tokens;
}

/// 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 — everything stable before the breakpoint, everything
/// per-request after it.
inline BreakpointPlan plan_breakpoints(const std::vector<PromptSession> &sessions) {
    BreakpointPlan plan;
    std::vector<const PromptSession *> valid;
    for (const auto &s : sessions) valid.push_back(&s);

    if (valid.empty()) {
        plan.warnings.push_back(
            "No sessions given — paste at least two prompts to compare.");
        return plan;
    }
    if (valid.size() == 1) {
        plan.warnings.push_back(
            "Only one session — a prefix needs at least two prompts to detect.");
    }

    // Common leading blocks by position.
    size_t shortest = valid[0]->blocks.size();
    for (const auto *s : valid) shortest = std::min(shortest, s->blocks.size());
    size_t prefix_end = 0;
    while (prefix_end < shortest) {
        bool shared = std::all_of(valid.begin(), valid.end(), [&](const PromptSession *s) {
            return s->blocks[prefix_end] == valid[0]->blocks[prefix_end];
        });
        if (!shared) break;
        prefix_end++;
    }

    // Common trailing blocks, matched from each session's own tail, never
    // overlapping the prefix.
    size_t suffix_len = 0;
    while (suffix_len < shortest - prefix_end) {
        bool shared = std::all_of(valid.begin(), valid.end(), [&](const PromptSession *s) {
            return s->blocks[s->blocks.size() - 1 - suffix_len]
                == valid[0]->blocks[valid[0]->blocks.size() - 1 - suffix_len];
        });
        if (!shared) break;
        suffix_len++;
    }

    auto join = [](const std::vector<std::string> &parts) {
        std::string out;
        for (size_t i = 0; i < parts.size(); i++) {
            if (i > 0) out += '\n';
            out += parts[i];
        }
        return out;
    };

    plan.prefix_blocks.assign(valid[0]->blocks.begin(),
                              valid[0]->blocks.begin() + prefix_end);
    if (suffix_len > 0) {
        plan.suffix_blocks.assign(valid[0]->blocks.end() - suffix_len,
                                  valid[0]->blocks.end());
    }
    plan.prefix_tokens = tok(join(plan.prefix_blocks));
    plan.suffix_tokens = tok(join(plan.suffix_blocks));

    if (!plan.prefix_blocks.empty()) {
        plan.breakpoints.push_back(Breakpoint{
            static_cast<long>(prefix_end) - 1,
            "after the shared prefix",
            std::to_string(plan.prefix_blocks.size())
                + " block(s) identical across every session — cache once, hit on every request.",
            plan.prefix_tokens,
        });
    }
    if (suffix_len > 0) {
        plan.breakpoints.push_back(Breakpoint{
            -1, // terminal: the shared tail sits at the end of each request
            "shared tail",
            std::to_string(suffix_len)
                + " trailing block(s) also identical — extend the cache segment or accept the re-read.",
            plan.suffix_tokens,
        });
    }
    if (plan.breakpoints.empty()) {
        plan.warnings.push_back(
            "No shared leading or trailing blocks — nothing to cache across these sessions.");
    }

    for (const auto *s : valid) {
        long total_tokens = tok(join(s->blocks));
        long unique = std::max<long>(total_tokens - plan.prefix_tokens - plan.suffix_tokens, 0);
        double cached_ratio = total_tokens > 0
            ? std::min(1.0,
                       static_cast<double>(plan.prefix_tokens + plan.suffix_tokens)
                           / static_cast<double>(total_tokens))
            : 0.0;
        plan.per_session.push_back(
            PerSessionRow{s->id, total_tokens, unique, cached_ratio});
    }

    double sum = 0.0;
    for (const auto &row : plan.per_session) sum += static_cast<double>(row.total_tokens);
    double avg_total = plan.per_session.empty() ? 0.0 : sum / plan.per_session.size();
    double cached_share = avg_total > 0.0
        ? std::min(1.0,
                   static_cast<double>(plan.prefix_tokens + plan.suffix_tokens) / avg_total)
        : 0.0;
    plan.estimated_savings = cached_share * (1.0 - kCacheReadDiscount);

    return plan;
}

} // namespace cache_breakpoint_planner