1use std::collections::BTreeSet;
2
3use serde::{Deserialize, Serialize};
4use thiserror::Error;
5
6use crate::{ContextSource, MemoryStatus, SCHEMA_VERSION, hash_json};
7
8pub const COMPACTION_ALGORITHM_VERSION: &str = "proofborne.compaction.v1";
10pub const COMPACTION_TOKEN_ESTIMATOR: &str = "utf8_ascii_div_3_plus_non_ascii_scalars.v1";
12
13#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq)]
15#[serde(rename_all = "camelCase")]
16pub struct CompactionBudget {
17 pub context_tokens: u64,
19 pub reserved_output_tokens: u64,
21 pub max_input_tokens: u64,
23 pub max_input_bytes: u64,
25}
26
27impl CompactionBudget {
28 pub fn new(
30 context_tokens: u64,
31 reserved_output_tokens: u64,
32 max_input_bytes: u64,
33 ) -> Result<Self, CompactionError> {
34 let max_input_tokens = context_tokens
35 .checked_sub(reserved_output_tokens)
36 .filter(|available| *available > 0)
37 .ok_or(CompactionError::InvalidBudget)?;
38 let budget = Self {
39 context_tokens,
40 reserved_output_tokens,
41 max_input_tokens,
42 max_input_bytes,
43 };
44 budget.validate()?;
45 Ok(budget)
46 }
47
48 pub fn validate(&self) -> Result<(), CompactionError> {
50 if self.context_tokens == 0
51 || self.reserved_output_tokens == 0
52 || self.max_input_tokens == 0
53 || self.max_input_bytes == 0
54 || self
55 .reserved_output_tokens
56 .checked_add(self.max_input_tokens)
57 != Some(self.context_tokens)
58 {
59 return Err(CompactionError::InvalidBudget);
60 }
61 Ok(())
62 }
63}
64
65#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq)]
67#[serde(rename_all = "camelCase")]
68pub struct CompactionUsage {
69 pub token_estimator: String,
71 pub instruction_tokens: u64,
73 pub tool_tokens: u64,
75 pub contract_tokens: u64,
77 pub evidence_tokens: u64,
79 pub memory_tokens: u64,
81 pub history_tokens: u64,
83 pub input_tokens: u64,
85 pub input_bytes: u64,
87}
88impl Default for CompactionUsage {
89 fn default() -> Self {
90 Self {
91 token_estimator: COMPACTION_TOKEN_ESTIMATOR.to_owned(),
92 instruction_tokens: 0,
93 tool_tokens: 0,
94 contract_tokens: 0,
95 evidence_tokens: 0,
96 memory_tokens: 0,
97 history_tokens: 0,
98 input_tokens: 0,
99 input_bytes: 0,
100 }
101 }
102}
103
104impl CompactionUsage {
105 pub fn category_total(&self) -> Option<u64> {
107 self.instruction_tokens
108 .checked_add(self.tool_tokens)?
109 .checked_add(self.contract_tokens)?
110 .checked_add(self.evidence_tokens)?
111 .checked_add(self.memory_tokens)?
112 .checked_add(self.history_tokens)
113 }
114
115 pub fn validate(&self, budget: &CompactionBudget) -> Result<(), CompactionError> {
117 if self.token_estimator != COMPACTION_TOKEN_ESTIMATOR {
118 return Err(CompactionError::UnsupportedTokenEstimator(
119 self.token_estimator.clone(),
120 ));
121 }
122 budget.validate()?;
123 if self.category_total() != Some(self.input_tokens) {
124 return Err(CompactionError::UsageAccounting);
125 }
126 if self.input_tokens > budget.max_input_tokens || self.input_bytes > budget.max_input_bytes
127 {
128 return Err(CompactionError::BudgetExceeded);
129 }
130 Ok(())
131 }
132}
133
134#[derive(Debug, Clone, Copy, Serialize, Deserialize, PartialEq, Eq, PartialOrd, Ord)]
136#[serde(rename_all = "snake_case")]
137pub enum CompactionContextKind {
138 Contract,
140 Criterion,
142 Evidence,
144 Memory,
146 History,
148 Workspace,
150 SideEffect,
152 Recovery,
154 Authority,
156 SecretTaint,
158}
159
160#[derive(Debug, Clone, Copy, Serialize, Deserialize, PartialEq, Eq, PartialOrd, Ord)]
162#[serde(rename_all = "snake_case")]
163pub enum CompactionPriority {
164 Pinned,
166 Proof,
168 Retrieved,
170 Recent,
172}
173
174#[derive(Debug, Clone, Copy, Serialize, Deserialize, PartialEq, Eq)]
176#[serde(rename_all = "snake_case")]
177pub enum CompactionDecision {
178 Retained,
180 Omitted,
182}
183
184#[derive(Debug, Clone, Copy, Serialize, Deserialize, PartialEq, Eq, PartialOrd, Ord)]
186#[serde(rename_all = "snake_case")]
187pub enum CompactionSelectionReason {
188 TaskContract,
190 ClaimScope,
192 RequiredCriterion,
194 OpenObligation,
196 UnresolvedCounterevidence,
198 ActiveEvidence,
200 Waiver,
202 Supersession,
204 WorkspaceBinding,
206 SideEffectBinding,
208 RecoveryBinding,
210 AuthorityBinding,
212 SecretTaint,
214 TaskScopeMatch,
216 PathScopeMatch,
218 SymbolScopeMatch,
220 ProducerMatch,
222 RetrievalMatch,
224 RecentHistory,
226 BudgetExhausted,
228 HistoricalMemoryExcluded,
230 Superseded,
232}
233
234#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq)]
236#[serde(rename_all = "camelCase")]
237pub struct ContextSelection {
238 pub id: String,
240 pub kind: CompactionContextKind,
242 pub content_hash: String,
244 pub decision: CompactionDecision,
246 pub reason: CompactionSelectionReason,
248 pub priority: CompactionPriority,
250 pub required: bool,
252 pub rank: u64,
254 pub estimated_tokens: u64,
256 pub byte_count: u64,
258 #[serde(skip_serializing_if = "Option::is_none")]
260 pub source: Option<ContextSource>,
261 #[serde(skip_serializing_if = "Option::is_none")]
263 pub memory_status: Option<MemoryStatus>,
264}
265
266impl ContextSelection {
267 fn validate(&self) -> Result<(), CompactionError> {
268 if self.id.trim().is_empty() {
269 return Err(CompactionError::EmptySelectionId);
270 }
271 if !valid_digest(&self.content_hash) {
272 return Err(CompactionError::InvalidDigest(self.content_hash.clone()));
273 }
274 if self.estimated_tokens == 0 || self.byte_count == 0 {
275 return Err(CompactionError::EmptySelection(self.id.clone()));
276 }
277 if self.required && self.decision != CompactionDecision::Retained {
278 return Err(CompactionError::RequiredSelectionOmitted(self.id.clone()));
279 }
280 if self.kind == CompactionContextKind::Memory && self.memory_status.is_none() {
281 return Err(CompactionError::MemoryLifecycleMissing(self.id.clone()));
282 }
283 if self.kind != CompactionContextKind::Memory && self.memory_status.is_some() {
284 return Err(CompactionError::UnexpectedMemoryLifecycle(self.id.clone()));
285 }
286 Ok(())
287 }
288}
289
290#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq)]
292#[serde(rename_all = "camelCase")]
293pub struct CompactionPlan {
294 pub schema_version: String,
296 pub algorithm_version: String,
298 pub input_hash: String,
300 pub contract_hash: String,
302 pub workspace_generation: u64,
304 pub state_binding: String,
306 pub side_effect_watermark: u64,
308 #[serde(skip_serializing_if = "Option::is_none")]
310 pub authority_hash: Option<String>,
311 pub budget: CompactionBudget,
313 pub selections: Vec<ContextSelection>,
315}
316
317impl CompactionPlan {
318 pub fn digest(&self) -> Result<String, CompactionError> {
320 let value = serde_json::to_value(self).map_err(|_| CompactionError::Serialization)?;
321 Ok(hash_json(&value))
322 }
323
324 pub fn validate(&self) -> Result<(), CompactionError> {
326 if self.schema_version != SCHEMA_VERSION {
327 return Err(CompactionError::UnsupportedSchema(
328 self.schema_version.clone(),
329 ));
330 }
331 if self.algorithm_version != COMPACTION_ALGORITHM_VERSION {
332 return Err(CompactionError::UnsupportedAlgorithm(
333 self.algorithm_version.clone(),
334 ));
335 }
336 for digest in [&self.input_hash, &self.contract_hash, &self.state_binding] {
337 if !valid_digest(digest) {
338 return Err(CompactionError::InvalidDigest((*digest).clone()));
339 }
340 }
341 if self
342 .authority_hash
343 .as_deref()
344 .is_some_and(|digest| !valid_digest(digest))
345 {
346 return Err(CompactionError::InvalidDigest(
347 self.authority_hash.clone().unwrap_or_default(),
348 ));
349 }
350 self.budget.validate()?;
351 if self.selections.is_empty() {
352 return Err(CompactionError::EmptyPlan);
353 }
354
355 let mut identifiers = BTreeSet::new();
356 let mut previous = None;
357 for selection in &self.selections {
358 selection.validate()?;
359 if !identifiers.insert(selection.id.as_str()) {
360 return Err(CompactionError::DuplicateSelection(selection.id.clone()));
361 }
362 let key = (selection.priority, selection.rank, selection.id.as_str());
363 if previous.is_some_and(|previous| previous > key) {
364 return Err(CompactionError::SelectionOrder);
365 }
366 previous = Some(key);
367 }
368 Ok(())
369 }
370}
371
372#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq)]
374#[serde(rename_all = "camelCase")]
375pub struct CompactionReceipt {
376 pub schema_version: String,
378 pub algorithm_version: String,
380 pub plan_hash: String,
382 pub input_hash: String,
384 pub output_hash: String,
386 pub output_history_hash: String,
388 pub output_history_items: u64,
390 pub workspace_generation: u64,
392 pub state_binding: String,
394 pub plan: CompactionPlan,
396 pub usage: CompactionUsage,
398 pub retained_ids: Vec<String>,
400 pub omitted_ids: Vec<String>,
402}
403
404impl CompactionReceipt {
405 pub fn validate(&self) -> Result<(), CompactionError> {
407 if self.schema_version != SCHEMA_VERSION {
408 return Err(CompactionError::UnsupportedSchema(
409 self.schema_version.clone(),
410 ));
411 }
412 if self.algorithm_version != COMPACTION_ALGORITHM_VERSION {
413 return Err(CompactionError::UnsupportedAlgorithm(
414 self.algorithm_version.clone(),
415 ));
416 }
417 self.plan.validate()?;
418 if self.plan_hash != self.plan.digest()? {
419 return Err(CompactionError::PlanDigest);
420 }
421 if self.input_hash != self.plan.input_hash
422 || self.workspace_generation != self.plan.workspace_generation
423 || self.state_binding != self.plan.state_binding
424 {
425 return Err(CompactionError::PlanBinding);
426 }
427 for digest in [&self.output_hash, &self.output_history_hash] {
428 if !valid_digest(digest) {
429 return Err(CompactionError::InvalidDigest((*digest).clone()));
430 }
431 }
432 if self.output_history_items == 0 {
433 return Err(CompactionError::PlanBinding);
434 }
435 self.usage.validate(&self.plan.budget)?;
436
437 let mut retained = self
438 .plan
439 .selections
440 .iter()
441 .filter(|selection| selection.decision == CompactionDecision::Retained)
442 .map(|selection| selection.id.clone())
443 .collect::<Vec<_>>();
444 let mut omitted = self
445 .plan
446 .selections
447 .iter()
448 .filter(|selection| selection.decision == CompactionDecision::Omitted)
449 .map(|selection| selection.id.clone())
450 .collect::<Vec<_>>();
451 retained.sort();
452 omitted.sort();
453 if retained != self.retained_ids || omitted != self.omitted_ids {
454 return Err(CompactionError::SelectionSets);
455 }
456 Ok(())
457 }
458}
459
460fn valid_digest(value: &str) -> bool {
461 value.len() == 64
462 && value
463 .bytes()
464 .all(|byte| byte.is_ascii_digit() || (b'a'..=b'f').contains(&byte))
465}
466
467#[derive(Debug, Clone, Error, PartialEq, Eq)]
469pub enum CompactionError {
470 #[error("unsupported compaction schema: {0}")]
472 UnsupportedSchema(String),
473 #[error("unsupported compaction algorithm: {0}")]
475 UnsupportedAlgorithm(String),
476 #[error("compaction budget is invalid")]
478 InvalidBudget,
479 #[error("unsupported compaction token estimator: {0}")]
481 UnsupportedTokenEstimator(String),
482 #[error("compaction usage accounting is inconsistent")]
484 UsageAccounting,
485 #[error("compacted context exceeds its hard budget")]
487 BudgetExceeded,
488 #[error("compaction contract serialization failed")]
490 Serialization,
491 #[error("invalid compaction digest: {0}")]
493 InvalidDigest(String),
494 #[error("compaction plan must contain at least one selection")]
496 EmptyPlan,
497 #[error("compaction selection identifier must not be empty")]
499 EmptySelectionId,
500 #[error("compaction selection has empty content: {0}")]
502 EmptySelection(String),
503 #[error("duplicate compaction selection: {0}")]
505 DuplicateSelection(String),
506 #[error("compaction selections are not deterministically ordered")]
508 SelectionOrder,
509 #[error("required compaction selection was omitted: {0}")]
511 RequiredSelectionOmitted(String),
512 #[error("memory selection lacks lifecycle state: {0}")]
514 MemoryLifecycleMissing(String),
515 #[error("non-memory selection carries a memory lifecycle state: {0}")]
517 UnexpectedMemoryLifecycle(String),
518 #[error("compaction receipt plan digest is invalid")]
520 PlanDigest,
521 #[error("compaction receipt does not match its plan bindings")]
523 PlanBinding,
524 #[error("compaction receipt selection sets are inconsistent")]
526 SelectionSets,
527}
528
529#[cfg(test)]
530mod tests {
531 use serde_json::json;
532
533 use super::*;
534 use crate::hash_bytes;
535
536 fn valid_plan() -> CompactionPlan {
537 CompactionPlan {
538 schema_version: SCHEMA_VERSION.to_owned(),
539 algorithm_version: COMPACTION_ALGORITHM_VERSION.to_owned(),
540 input_hash: hash_bytes(b"input"),
541 contract_hash: hash_bytes(b"contract"),
542 workspace_generation: 4,
543 state_binding: hash_bytes(b"workspace"),
544 side_effect_watermark: 0,
545 authority_hash: Some(hash_bytes(b"authority")),
546 budget: CompactionBudget::new(100, 10, 1_000).unwrap(),
547 selections: vec![ContextSelection {
548 id: "contract:task".to_owned(),
549 kind: CompactionContextKind::Contract,
550 content_hash: hash_bytes(b"selection"),
551 decision: CompactionDecision::Retained,
552 reason: CompactionSelectionReason::TaskContract,
553 priority: CompactionPriority::Pinned,
554 required: true,
555 rank: 0,
556 estimated_tokens: 4,
557 byte_count: 9,
558 source: None,
559 memory_status: None,
560 }],
561 }
562 }
563
564 fn valid_receipt() -> CompactionReceipt {
565 let plan = valid_plan();
566 CompactionReceipt {
567 schema_version: SCHEMA_VERSION.to_owned(),
568 algorithm_version: COMPACTION_ALGORITHM_VERSION.to_owned(),
569 plan_hash: plan.digest().unwrap(),
570 input_hash: plan.input_hash.clone(),
571 output_hash: hash_bytes(b"provider-input"),
572 output_history_hash: hash_bytes(b"history"),
573 output_history_items: 1,
574 workspace_generation: plan.workspace_generation,
575 state_binding: plan.state_binding.clone(),
576 plan,
577 usage: CompactionUsage {
578 token_estimator: COMPACTION_TOKEN_ESTIMATOR.to_owned(),
579 instruction_tokens: 1,
580 tool_tokens: 1,
581 contract_tokens: 1,
582 evidence_tokens: 1,
583 memory_tokens: 1,
584 history_tokens: 1,
585 input_tokens: 6,
586 input_bytes: 18,
587 },
588 retained_ids: vec!["contract:task".to_owned()],
589 omitted_ids: Vec::new(),
590 }
591 }
592
593 #[test]
594 fn required_selection_cannot_be_omitted() {
595 let mut plan = valid_plan();
596 plan.selections[0].decision = CompactionDecision::Omitted;
597 assert_eq!(
598 plan.validate(),
599 Err(CompactionError::RequiredSelectionOmitted(
600 "contract:task".to_owned()
601 ))
602 );
603 }
604
605 #[test]
606 fn receipt_rejects_plan_tampering_and_commits_history_digest() {
607 let mut plan_tampered = valid_receipt();
608 plan_tampered.plan.side_effect_watermark = 1;
609 assert_eq!(plan_tampered.validate(), Err(CompactionError::PlanDigest));
610
611 let mut history_tampered = valid_receipt();
612 history_tampered.output_history_hash = "0".repeat(64);
613 assert!(history_tampered.validate().is_ok());
614 assert_ne!(
615 history_tampered.output_history_hash,
616 hash_bytes(b"history"),
617 "checkpoint recovery must compare this digest to the persisted history"
618 );
619 }
620
621 #[test]
622 fn default_usage_names_the_versioned_estimator() {
623 let usage = CompactionUsage::default();
624 assert_eq!(usage.token_estimator, COMPACTION_TOKEN_ESTIMATOR);
625 usage.validate(&valid_plan().budget).unwrap();
626 }
627
628 #[test]
629 fn public_receipt_shape_is_camel_case_and_versioned() {
630 let receipt = valid_receipt();
631 receipt.validate().unwrap();
632 let value = serde_json::to_value(receipt).unwrap();
633 assert_eq!(value["schemaVersion"], json!(SCHEMA_VERSION));
634 assert_eq!(
635 value["algorithmVersion"],
636 json!(COMPACTION_ALGORITHM_VERSION)
637 );
638 assert_eq!(
639 value["usage"]["tokenEstimator"],
640 json!(COMPACTION_TOKEN_ESTIMATOR)
641 );
642 assert!(value.get("outputHistoryHash").is_some());
643 assert!(value.get("retainedIds").is_some());
644 assert!(value.get("output_history_hash").is_none());
645 }
646}