commit - 3f64e350370dd21067666d57867a764e16479365
commit + d0921318c8b295fe262375179490705dec1c5bd8
blob - 2ff2caa01bbf79cd0afb7e9e32e39d4fd23b33a5
blob + 38db374e68b9925165da2b2333d11acd7c32bf34
--- regress/compaction/compaction_test.c
+++ regress/compaction/compaction_test.c
}
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,
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)
{
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
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
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[];
/*
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 */
