commit d0921318c8b295fe262375179490705dec1c5bd8 from: Isaac Meerleo date: Fri Jul 17 21:40:42 2026 UTC Plan automatic Compaction cuts commit - 3f64e350370dd21067666d57867a764e16479365 commit + d0921318c8b295fe262375179490705dec1c5bd8 blob - 2ff2caa01bbf79cd0afb7e9e32e39d4fd23b33a5 blob + 38db374e68b9925165da2b2333d11acd7c32bf34 --- regress/compaction/compaction_test.c +++ regress/compaction/compaction_test.c @@ -42,6 +42,17 @@ append_message(struct msglist *messages, struct msg *m } static void +append_text_message(struct msglist *messages, enum msg_role role, + const char *text, size_t len) +{ + struct msg *message; + + message = msg_new(role); + msg_add_text(message, text, len); + append_message(messages, message); +} + +static void test_system_prompt(void) { CHECK(strstr(compaction_system_prompt, @@ -636,6 +647,229 @@ test_file_safety_and_transactions(void) compaction_files_free(files); } +static void +test_request_estimator(void) +{ + static const u_char system[] = { 's', '\0', 'y' }; + static const struct tool_def tools[] = { + { "read", "Read file", "{}" } + }; + struct msglist messages; + struct msg *message; + size_t tokens; + + TAILQ_INIT(&messages); + message = msg_new(ROLE_USER); + msg_add_text(message, "abcde", 5); + append_message(&messages, message); + message = msg_new(ROLE_ASSISTANT); + msg_add_tool_use(message, "id", "read", "{}", 2); + append_message(&messages, message); + message = msg_new(ROLE_USER); + msg_add_tool_result(message, "id", "body", 4, 0); + append_message(&messages, message); + + /* + * 256 request + 3 System + 3*32 messages + 3*64 blocks + + * 19 canonical block bytes + 64 tool + 15 tool bytes = 645; + * ceil(645 / 4) is 162 tokens. + */ + tokens = 0; + CHECK(compaction_estimate_request(system, sizeof(system), &messages, + tools, 1, &tokens) == 0); + CHECK(tokens == 162); + msglist_free(&messages); + + TAILQ_INIT(&messages); + CHECK(compaction_estimate_request(NULL, 0, &messages, NULL, 0, + &tokens) == 0); + CHECK(tokens == 64); + CHECK(compaction_estimate_request("x", 1, &messages, NULL, 0, + &tokens) == 0); + CHECK(tokens == 65); + CHECK(compaction_estimate_request("xxxx", 4, &messages, NULL, 0, + &tokens) == 0); + CHECK(tokens == 65); +} + +static void +test_compaction_threshold(void) +{ + /* Unknown Effective window always skips automatic Compaction. */ + CHECK(compaction_threshold_exceeded(SIZE_MAX, 0, SIZE_MAX) == 0); + /* The comparison is strict at window - reserve. */ + CHECK(compaction_threshold_exceeded(80, 100, 20) == 0); + CHECK(compaction_threshold_exceeded(81, 100, 20) == 1); + CHECK(compaction_threshold_exceeded(SIZE_MAX - 1, SIZE_MAX, 1) == 0); + CHECK(compaction_threshold_exceeded(SIZE_MAX, SIZE_MAX, 1) == 1); + /* A known window with no usable budget is a configuration error. */ + CHECK(compaction_threshold_exceeded(0, 100, 100) == -1); + CHECK(compaction_threshold_exceeded(0, 100, 101) == -1); +} + +static void +test_cut_plan_turn_boundaries(void) +{ + struct compaction_cut_plan plan; + struct msglist messages; + + /* Each message is 32 + 64 + 4 = 100 bytes, or 25 tokens. */ + TAILQ_INIT(&messages); + append_text_message(&messages, ROLE_USER, "u001", 4); + append_text_message(&messages, ROLE_ASSISTANT, "a001", 4); + append_text_message(&messages, ROLE_USER, "u002", 4); + append_text_message(&messages, ROLE_ASSISTANT, "a002", 4); + append_text_message(&messages, ROLE_USER, "u003", 4); + append_text_message(&messages, ROLE_ASSISTANT, "a003", 4); + + CHECK(compaction_plan_cut(&messages, 100, 0, 0, &plan) == 0); + CHECK(plan.history_prefix == 2); + CHECK(plan.current_turn_prefix == 0); + CHECK(plan.retain_first == 2); + CHECK(plan.split_turn == 0); + CHECK(plan.retained_tokens == 100); + + /* Whole recent Turns are retained; an older partial Turn is not. */ + CHECK(compaction_plan_cut(&messages, 99, 0, 0, &plan) == 0); + CHECK(plan.history_prefix == 4); + CHECK(plan.retain_first == 4); + CHECK(plan.split_turn == 0); + CHECK(plan.retained_tokens == 50); + + CHECK(compaction_plan_cut(&messages, 150, 0, 0, &plan) == 0); + CHECK(plan.history_prefix == 0); + CHECK(plan.retain_first == 0); + CHECK(plan.retained_tokens == 150); + + /* The last inferred Turn is the Pending Projection when active. */ + CHECK(compaction_plan_cut(&messages, 40, 1, 0, &plan) == 0); + CHECK(plan.history_prefix == 4); + CHECK(plan.current_turn_prefix == 1); + CHECK(plan.retain_first == 5); + CHECK(plan.split_turn == 1); + CHECK(plan.retained_tokens == 25); + + /* No safe non-empty suffix fits, so the complete Turn survives. */ + CHECK(compaction_plan_cut(&messages, 24, 1, 0, &plan) == 0); + CHECK(plan.history_prefix == 4); + CHECK(plan.current_turn_prefix == 0); + CHECK(plan.retain_first == 4); + CHECK(plan.split_turn == 0); + CHECK(plan.retained_tokens == 50); + + /* Manual force may summarize everything and retain an empty suffix. */ + CHECK(compaction_plan_cut(&messages, 0, 1, 1, &plan) == 0); + CHECK(plan.history_prefix == 4); + CHECK(plan.current_turn_prefix == 2); + CHECK(plan.retain_first == 6); + CHECK(plan.split_turn == 0); + CHECK(plan.retained_tokens == 0); + + msglist_free(&messages); +} + +static void +test_cut_plan_tool_pairs_and_steers(void) +{ + struct compaction_cut_plan plan; + struct msglist messages; + struct msg *message; + + TAILQ_INIT(&messages); + append_text_message(&messages, ROLE_USER, "hist", 4); + append_text_message(&messages, ROLE_ASSISTANT, "done", 4); + append_text_message(&messages, ROLE_USER, "work", 4); + message = msg_new(ROLE_ASSISTANT); + msg_add_tool_use(message, "c1", "read", "{}", 2); + msg_add_tool_use(message, "c2", "read", "{}", 2); + append_message(&messages, message); + message = msg_new(ROLE_USER); + /* Result order is immaterial; the set must be complete. */ + msg_add_tool_result(message, "c2", "ok", 2, 0); + msg_add_tool_result(message, "c1", "ok", 2, 0); + msg_add_text(message, "next", 4); /* Steer, not a new Turn. */ + append_message(&messages, message); + append_text_message(&messages, ROLE_ASSISTANT, "tail", 4); + + /* + * The paired suffix is 176 tool-call + 236 result/steer + + * 100 final Assistant = 512 bytes, or 128 tokens. + */ + CHECK(compaction_plan_cut(&messages, 130, 1, 0, &plan) == 0); + CHECK(plan.history_prefix == 2); + CHECK(plan.current_turn_prefix == 1); + CHECK(plan.retain_first == 3); + CHECK(plan.split_turn == 1); + CHECK(plan.retained_tokens == 128); + + /* The result/steer User at index 4 is never a retained start. */ + CHECK(compaction_plan_cut(&messages, 100, 1, 0, &plan) == 0); + CHECK(plan.history_prefix == 2); + CHECK(plan.current_turn_prefix == 3); + CHECK(plan.retain_first == 5); + CHECK(plan.retained_tokens == 25); + msglist_free(&messages); + + /* An incomplete result set makes the Tool-use boundary unsafe. */ + TAILQ_INIT(&messages); + append_text_message(&messages, ROLE_USER, "work", 4); + message = msg_new(ROLE_ASSISTANT); + msg_add_tool_use(message, "c1", "read", "{}", 2); + msg_add_tool_use(message, "c2", "read", "{}", 2); + append_message(&messages, message); + message = msg_new(ROLE_USER); + msg_add_tool_result(message, "c1", "ok", 2, 0); + msg_add_text(message, "next", 4); + append_message(&messages, message); + CHECK(compaction_plan_cut(&messages, 100, 1, 0, &plan) == 0); + CHECK(plan.history_prefix == 0); + CHECK(plan.current_turn_prefix == 0); + CHECK(plan.retain_first == 0); + CHECK(plan.split_turn == 0); + CHECK(plan.retained_tokens == 111); + msglist_free(&messages); +} + +static void +test_compaction_estimate_overflow(void) +{ + static const struct tool_def tool = { "x", "x", "{}" }; + static const struct compaction_cut_plan sentinel = { + 11, 22, 33, 44, 1 + }; + struct compaction_cut_plan plan; + struct msglist messages; + struct msg *message; + struct block *block; + size_t tokens; + + TAILQ_INIT(&messages); + tokens = 777; + CHECK(compaction_estimate_request("x", SIZE_MAX, &messages, NULL, 0, + &tokens) == -1); + CHECK(tokens == 777); + CHECK(compaction_estimate_request(NULL, 0, &messages, &tool, SIZE_MAX, + &tokens) == -1); + CHECK(tokens == 777); + + /* Each message fits alone; their combined prospective span does not. */ + message = msg_new(ROLE_USER); + block = msg_add_text(message, "x", 1); + block->textlen = SIZE_MAX / 2 - 64; + append_message(&messages, message); + message = msg_new(ROLE_ASSISTANT); + block = msg_add_text(message, "x", 1); + block->textlen = SIZE_MAX / 2 - 64; + append_message(&messages, message); + CHECK(compaction_estimate_request(NULL, 0, &messages, NULL, 0, + &tokens) == -1); + CHECK(tokens == 777); + plan = sentinel; + CHECK(compaction_plan_cut(&messages, SIZE_MAX, 0, 0, &plan) == -1); + CHECK(memcmp(&plan, &sentinel, sizeof(plan)) == 0); + msglist_free(&messages); +} + int main(void) { @@ -652,6 +886,11 @@ main(void) test_file_collection_and_rendering(); test_file_cumulative_merge(); test_file_safety_and_transactions(); + test_request_estimator(); + test_compaction_threshold(); + test_cut_plan_turn_boundaries(); + test_cut_plan_tool_pairs_and_steers(); + test_compaction_estimate_overflow(); REGRESS_END(); } blob - ef442a546e46c57af45ba8512f9ea51db50de6a0 blob + d86e575a5889aa233decc07d323cecaff0f5f369 --- src/common/compaction.c +++ src/common/compaction.c @@ -68,6 +68,325 @@ struct compaction_files { size_t bytes; }; +static int +size_add(size_t *total, size_t add) +{ + if (add > SIZE_MAX - *total) + return (-1); + *total += add; + return (0); +} + +static int +size_add_product(size_t *total, size_t count, size_t each) +{ + if (count != 0 && each > SIZE_MAX / count) + return (-1); + return (size_add(total, count * each)); +} + +static size_t +bytes_to_tokens(size_t bytes) +{ + return (bytes / 4 + (bytes % 4 != 0)); +} + +static int +message_estimate_bytes(const struct msg *message, size_t *out) +{ + const struct block *block; + size_t bytes; + + if (message == NULL || out == NULL || + (message->role != ROLE_USER && message->role != ROLE_ASSISTANT)) + return (-1); + bytes = COMPACTION_ESTIMATE_MESSAGE_BYTES; + TAILQ_FOREACH(block, &message->blocks, entry) { + if (size_add(&bytes, COMPACTION_ESTIMATE_BLOCK_BYTES) == -1) + return (-1); + switch (block->type) { + case BLOCK_TEXT: + if ((block->textlen > 0 && block->text == NULL) || + size_add(&bytes, block->textlen) == -1) + return (-1); + break; + case BLOCK_TOOL_USE: + if (message->role != ROLE_ASSISTANT || + block->tool_id == NULL || block->tool_name == NULL || + (block->tool_input_len > 0 && + block->tool_input == NULL) || + size_add(&bytes, strlen(block->tool_id)) == -1 || + size_add(&bytes, strlen(block->tool_name)) == -1 || + size_add(&bytes, block->tool_input_len) == -1) + return (-1); + break; + case BLOCK_TOOL_RESULT: + if (message->role != ROLE_USER || + block->tool_use_id == NULL || + (block->result_len > 0 && block->result == NULL) || + size_add(&bytes, strlen(block->tool_use_id)) == -1 || + size_add(&bytes, block->result_len) == -1) + return (-1); + break; + default: + return (-1); + } + } + *out = bytes; + return (0); +} + +/* + * Provider codecs differ in their exact JSON envelope. The public fixed + * allowances cover that unmaterialized structure; every selected byte whose + * length is known here is then counted exactly. This intentionally errs on + * the high side without building three provider-specific requests. + */ +int +compaction_estimate_request(const void *system, size_t system_len, + const struct msglist *messages, const struct tool_def *tools, + size_t ntools, size_t *tokens) +{ + const struct msg *message; + size_t bytes, item_bytes, i; + + if (messages == NULL || tokens == NULL || + (system_len > 0 && system == NULL) || + (ntools > 0 && tools == NULL)) + return (-1); + bytes = COMPACTION_ESTIMATE_REQUEST_BYTES; + if (size_add(&bytes, system_len) == -1 || + size_add_product(&bytes, ntools, + COMPACTION_ESTIMATE_TOOL_BYTES) == -1) + return (-1); + for (i = 0; i < ntools; i++) { + if (tools[i].name == NULL || tools[i].description == NULL || + tools[i].schema == NULL || + size_add(&bytes, strlen(tools[i].name)) == -1 || + size_add(&bytes, strlen(tools[i].description)) == -1 || + size_add(&bytes, strlen(tools[i].schema)) == -1) + return (-1); + } + TAILQ_FOREACH(message, messages, entry) { + if (message_estimate_bytes(message, &item_bytes) == -1 || + size_add(&bytes, item_bytes) == -1) + return (-1); + } + *tokens = bytes_to_tokens(bytes); + return (0); +} + +int +compaction_threshold_exceeded(size_t estimate, size_t window, size_t reserve) +{ + if (window == 0) + return (0); + if (reserve >= window) + return (-1); + return (estimate > window - reserve); +} + +static int +message_has_tool_result(const struct msg *message) +{ + const struct block *block; + + TAILQ_FOREACH(block, &message->blocks, entry) { + if (block->type == BLOCK_TOOL_RESULT) + return (1); + } + return (0); +} + +static int +message_starts_turn(const struct msg *message) +{ + return (message->role == ROLE_USER && + !message_has_tool_result(message)); +} + +static int +assistant_results_complete(const struct msg *assistant, + const struct msg *results) +{ + const struct block *call, *result; + size_t calls, matches, nresults; + + calls = 0; + TAILQ_FOREACH(call, &assistant->blocks, entry) { + if (call->type == BLOCK_TOOL_USE) + calls++; + } + if (calls == 0) + return (1); + if (results == NULL || results->role != ROLE_USER) + return (0); + nresults = 0; + TAILQ_FOREACH(result, &results->blocks, entry) { + if (result->type == BLOCK_TOOL_RESULT) + nresults++; + } + if (calls != nresults) + return (0); + TAILQ_FOREACH(call, &assistant->blocks, entry) { + if (call->type != BLOCK_TOOL_USE) + continue; + if (call->tool_id == NULL) + return (0); + matches = 0; + TAILQ_FOREACH(result, &results->blocks, entry) { + if (result->type == BLOCK_TOOL_RESULT && + result->tool_use_id != NULL && + strcmp(call->tool_id, result->tool_use_id) == 0) + matches++; + } + if (matches != 1) + return (0); + } + return (1); +} + +static int +safe_split_start(const struct msg *message) +{ + const struct msg *previous, *next; + + if (message->role != ROLE_ASSISTANT) + return (0); + previous = TAILQ_PREV(message, msglist, entry); + if (previous == NULL || previous->role != ROLE_USER) + return (0); + next = TAILQ_NEXT(message, entry); + return (assistant_results_complete(message, next)); +} + +static int +plan_giant_turn(const struct msglist *messages, size_t turn_first, + size_t message_count, size_t turn_bytes, size_t keep_tokens, + size_t *retain_first, size_t *retained_bytes, int *split) +{ + const struct msg *message; + size_t best, best_bytes, bytes, index, message_bytes; + + best = SIZE_MAX; + best_bytes = 0; + bytes = 0; + index = message_count; + TAILQ_FOREACH_REVERSE(message, messages, msglist, entry) { + index--; + if (index < turn_first) + break; + if (message_estimate_bytes(message, &message_bytes) == -1 || + size_add(&bytes, message_bytes) == -1) + return (-1); + if (index == turn_first) + break; + if (bytes_to_tokens(bytes) > keep_tokens) + break; + if (safe_split_start(message)) { + best = index; + best_bytes = bytes; + } + } + if (best == SIZE_MAX) { + *retain_first = turn_first; + *retained_bytes = turn_bytes; + *split = 0; + } else { + *retain_first = best; + *retained_bytes = best_bytes; + *split = 1; + } + return (0); +} + +int +compaction_plan_cut(const struct msglist *messages, size_t keep_tokens, + int current_turn_active, int force, struct compaction_cut_plan *plan) +{ + const struct msg *message; + struct compaction_cut_plan candidate; + size_t combined, index, last_turn, message_bytes; + size_t message_count, retained_bytes, total_bytes; + size_t turn_bytes; + int have_turn, split; + + if (messages == NULL || plan == NULL || + (current_turn_active != 0 && current_turn_active != 1) || + (force != 0 && force != 1)) + return (-1); + memset(&candidate, 0, sizeof(candidate)); + message_count = 0; + total_bytes = 0; + last_turn = 0; + have_turn = 0; + TAILQ_FOREACH(message, messages, entry) { + if (message_estimate_bytes(message, &message_bytes) == -1 || + size_add(&total_bytes, message_bytes) == -1) + return (-1); + if (message_starts_turn(message)) { + last_turn = message_count; + have_turn = 1; + } + if (message_count == SIZE_MAX) + return (-1); + message_count++; + } + if (!have_turn) + last_turn = 0; + if (force) { + candidate.retain_first = message_count; + if (current_turn_active && message_count > 0) { + candidate.history_prefix = last_turn; + candidate.current_turn_prefix = + message_count - last_turn; + } else + candidate.history_prefix = message_count; + *plan = candidate; + return (0); + } + + retained_bytes = 0; + turn_bytes = 0; + candidate.retain_first = message_count; + index = message_count; + split = 0; + TAILQ_FOREACH_REVERSE(message, messages, msglist, entry) { + index--; + if (message_estimate_bytes(message, &message_bytes) == -1 || + size_add(&turn_bytes, message_bytes) == -1) + return (-1); + if (!message_starts_turn(message) && index != 0) + continue; + combined = retained_bytes; + if (size_add(&combined, turn_bytes) == -1) + return (-1); + if (bytes_to_tokens(combined) <= keep_tokens) { + retained_bytes = combined; + candidate.retain_first = index; + turn_bytes = 0; + continue; + } + if (candidate.retain_first == message_count && + plan_giant_turn(messages, index, message_count, turn_bytes, + keep_tokens, &candidate.retain_first, &retained_bytes, + &split) == -1) + return (-1); + break; + } + candidate.retained_tokens = bytes_to_tokens(retained_bytes); + candidate.split_turn = split; + if (current_turn_active && message_count > 0 && + candidate.retain_first > last_turn) { + candidate.history_prefix = last_turn; + candidate.current_turn_prefix = + candidate.retain_first - last_turn; + } else + candidate.history_prefix = candidate.retain_first; + *plan = candidate; + return (0); +} + static void file_set_free(struct compaction_file_set *set) { blob - 62c4147f7e26c32d7ff9b860a4bdabea7274fd7d blob + 1a1dcb3f90a212c532121fd68ee6704ce75fea67 --- src/common/compaction.h +++ src/common/compaction.h @@ -22,17 +22,36 @@ struct buf; struct compaction_files; struct msglist; +struct tool_def; #define COMPACTION_TOOL_RESULT_MAX 2000 #define COMPACTION_FILE_PATH_MAX 4096 #define COMPACTION_FILE_COUNT_MAX 4096 #define COMPACTION_FILE_BYTES_MAX (1024 * 1024) +/* + * Conservative provider-wire structural allowances, in bytes. Exact + * selected System, canonical block, and offered-tool bytes are added to + * these allowances before applying ceil(bytes / 4). + */ +#define COMPACTION_ESTIMATE_REQUEST_BYTES 256 +#define COMPACTION_ESTIMATE_MESSAGE_BYTES 32 +#define COMPACTION_ESTIMATE_BLOCK_BYTES 64 +#define COMPACTION_ESTIMATE_TOOL_BYTES 64 + enum compaction_file_kind { COMPACTION_FILE_READ, COMPACTION_FILE_MODIFIED }; +struct compaction_cut_plan { + size_t history_prefix; /* complete leading history messages */ + size_t current_turn_prefix; /* leading Pending Projection messages */ + size_t retain_first; /* global first retained message index */ + size_t retained_tokens; /* conservative suffix estimate */ + int split_turn; +}; + extern const char compaction_system_prompt[]; /* @@ -67,4 +86,18 @@ int compaction_files_get(const struct compaction_files int compaction_files_append(struct buf *, const struct compaction_files *, size_t); +/* Estimate one prospective provider request without provider-wire encoding. */ +int compaction_estimate_request(const void *, size_t, + const struct msglist *, const struct tool_def *, size_t, size_t *); + +/* -1 invalid known window, 0 skip/not exceeded, 1 strictly exceeded. */ +int compaction_threshold_exceeded(size_t, size_t, size_t); + +/* + * Plan a retained Projection suffix. The final inferred Turn is current + * when current_turn_active is true. force may retain an empty suffix. + */ +int compaction_plan_cut(const struct msglist *, size_t, int, int, + struct compaction_cut_plan *); + #endif /* COMPACTION_H */