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 (C11, 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
 *
 * C shape: a fixed-capacity result struct (caller allocates; blocks are
 * pointers INTO the sessions — no copies, valid while the inputs are).
 */

#include <stdio.h>
#include <string.h>

/* Cached reads bill at ~0.1x — the saving on the cached share is ~90%. */
#define CACHE_READ_DISCOUNT 0.1

/* Raise these caps for larger display examples; the planner saturates. */
#define CBP_MAX_BLOCKS 64
#define CBP_MAX_SESSIONS 32
#define CBP_MAX_BREAKPOINTS 2
#define CBP_MAX_WARNINGS 4

typedef struct {
    const char *id;
    const char *const *blocks; /* ordered prompt blocks */
    size_t block_count;
} cbp_session;

typedef struct {
    long after_block; /* place the breakpoint AFTER this 0-based index; -1 = terminal */
    const char *label;
    char reason[256];
    long cached_tokens;
} cbp_breakpoint;

typedef struct {
    const char *id;
    long total_tokens;
    long unique_tokens;
    double cached_ratio;
} cbp_row;

typedef struct {
    const char *prefix_blocks[CBP_MAX_BLOCKS];
    size_t prefix_count;
    long prefix_tokens;
    const char *suffix_blocks[CBP_MAX_BLOCKS];
    size_t suffix_count;
    long suffix_tokens;
    cbp_breakpoint breakpoints[CBP_MAX_BREAKPOINTS];
    size_t breakpoint_count;
    cbp_row per_session[CBP_MAX_SESSIONS];
    size_t row_count;
    double estimated_savings; /* 0..1 vs no caching */
    char warnings[CBP_MAX_WARNINGS][192];
    size_t warning_count;
} cbp_plan;

/*
 * The `type: 'prose'` path of the tokenEstimator, inlined: every non-empty
 * line costs max(1, round(length / 4)) tokens; empty text is 0.
 */
static long cbp_tok(const char *text) {
    if (text == NULL || text[0] == '\0') return 0;
    long tokens = 0;
    const char *line = text;
    for (const char *p = text;; p++) {
        if (*p == '\n' || *p == '\0') {
            size_t len = (size_t)(p - line);
            if (len > 0) {
                long per = (long)(((double)len / 4.0) + 0.5);
                tokens += per < 1 ? 1 : per;
            }
            if (*p == '\0') break;
            line = p + 1;
        }
    }
    return tokens;
}

/* Joined-token count over a session's blocks (the TS joins with '\n';
 * the joiner newline never adds a line, so a per-block sum is exact). */
static long cbp_tok_blocks(const char *const *blocks, size_t count) {
    long total = 0;
    for (size_t i = 0; i < count; i++) {
        total += cbp_tok(blocks[i]);
    }
    return total;
}

/*
 * 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. Returns the filled plan (pointers reference the inputs).
 */
cbp_plan cbp_plan_breakpoints(const cbp_session *sessions, size_t session_count) {
    cbp_plan plan;
    memset(&plan, 0, sizeof(plan));

    if (session_count == 0) {
        strncpy(plan.warnings[plan.warning_count++],
                "No sessions given — paste at least two prompts to compare.",
                sizeof(plan.warnings[0]) - 1);
        return plan;
    }
    if (session_count == 1) {
        strncpy(plan.warnings[plan.warning_count++],
                "Only one session — a prefix needs at least two prompts to detect.",
                sizeof(plan.warnings[0]) - 1);
    }

    /* Common leading blocks by position. */
    size_t shortest = sessions[0].block_count;
    for (size_t s = 1; s < session_count; s++) {
        if (sessions[s].block_count < shortest) shortest = sessions[s].block_count;
    }
    size_t prefix_end = 0;
    while (prefix_end < shortest) {
        int shared = 1;
        for (size_t s = 1; s < session_count; s++) {
            if (strcmp(sessions[s].blocks[prefix_end],
                       sessions[0].blocks[prefix_end]) != 0) {
                shared = 0;
                break;
            }
        }
        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) {
        int shared = 1;
        for (size_t s = 1; s < session_count; s++) {
            const char *a = sessions[s].blocks[sessions[s].block_count - 1 - suffix_len];
            const char *b =
                sessions[0].blocks[sessions[0].block_count - 1 - suffix_len];
            if (strcmp(a, b) != 0) {
                shared = 0;
                break;
            }
        }
        if (!shared) break;
        suffix_len++;
    }

    for (size_t i = 0; i < prefix_end && i < CBP_MAX_BLOCKS; i++) {
        plan.prefix_blocks[plan.prefix_count++] = sessions[0].blocks[i];
    }
    if (suffix_len > 0) {
        for (size_t i = sessions[0].block_count - suffix_len;
             i < sessions[0].block_count && plan.suffix_count < CBP_MAX_BLOCKS; i++) {
            plan.suffix_blocks[plan.suffix_count++] = sessions[0].blocks[i];
        }
    }
    plan.prefix_tokens = cbp_tok_blocks(sessions[0].blocks, prefix_end);
    plan.suffix_tokens = suffix_len > 0
        ? cbp_tok_blocks(sessions[0].blocks + (sessions[0].block_count - suffix_len), suffix_len)
        : 0;

    if (plan.prefix_count > 0) {
        cbp_breakpoint *bp = &plan.breakpoints[plan.breakpoint_count++];
        bp->after_block = (long)prefix_end - 1;
        bp->label = "after the shared prefix";
        snprintf(bp->reason, sizeof(bp->reason),
                 "%zu block(s) identical across every session — cache once, hit on every request.",
                 plan.prefix_count);
        bp->cached_tokens = plan.prefix_tokens;
    }
    if (suffix_len > 0) {
        cbp_breakpoint *bp = &plan.breakpoints[plan.breakpoint_count++];
        bp->after_block = -1; /* terminal: the shared tail sits at the end */
        bp->label = "shared tail";
        snprintf(bp->reason, sizeof(bp->reason),
                 "%zu trailing block(s) also identical — extend the cache segment or accept the re-read.",
                 suffix_len);
        bp->cached_tokens = plan.suffix_tokens;
    }
    if (plan.breakpoint_count == 0) {
        strncpy(plan.warnings[plan.warning_count++],
                "No shared leading or trailing blocks — nothing to cache across these sessions.",
                sizeof(plan.warnings[0]) - 1);
    }

    for (size_t s = 0; s < session_count && plan.row_count < CBP_MAX_SESSIONS; s++) {
        cbp_row *row = &plan.per_session[plan.row_count++];
        row->id = sessions[s].id;
        row->total_tokens = cbp_tok_blocks(sessions[s].blocks, sessions[s].block_count);
        long unique = row->total_tokens - plan.prefix_tokens - plan.suffix_tokens;
        row->unique_tokens = unique > 0 ? unique : 0;
        row->cached_ratio = row->total_tokens > 0
            ? ((double)(plan.prefix_tokens + plan.suffix_tokens) / (double)row->total_tokens)
            : 0.0;
        if (row->cached_ratio > 1.0) row->cached_ratio = 1.0;
    }

    long sum_total = 0;
    for (size_t i = 0; i < plan.row_count; i++) {
        sum_total += plan.per_session[i].total_tokens;
    }
    double avg_total = plan.row_count > 0 ? (double)sum_total / (double)plan.row_count : 0.0;
    double cached_share = avg_total > 0.0
        ? ((double)(plan.prefix_tokens + plan.suffix_tokens) / avg_total)
        : 0.0;
    if (cached_share > 1.0) cached_share = 1.0;
    plan.estimated_savings = cached_share * (1.0 - CACHE_READ_DISCOUNT);

    return plan;
}