perspt_sdk/prompt/
context.rs

1//! Resident context as paged memory (PSP-10 Definition 6, system 24).
2//!
3//! The conversation projection is the backing store, not the prompt. Pages
4//! are immutable and content-addressed; the mandatory dependency closure is
5//! pinned; optional synopsis frames are chosen by deterministic greedy
6//! weighted coverage (submodular, so greedy earns the `1 - 1/e` factor on
7//! the declared labels — a claim about labels, never about sufficiency).
8//! An infeasible mandatory closure makes no model call.
9
10use std::collections::{BTreeMap, BTreeSet};
11
12use serde::{Deserialize, Serialize};
13
14use crate::canon::CanonicalEncoder;
15use crate::error::{Result, SdkError};
16
17use super::section::PROMPT_DIGEST_TAG;
18
19/// The explicit state a page depends on. The assembler checks it against
20/// the current branch before making the page resident; a state change
21/// invalidates the page, it never silently rewrites it.
22#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
23#[serde(rename_all = "snake_case")]
24pub enum StateDependency {
25    SessionInvariant,
26    AcceptedRoot(String),
27    PartialCheckpointRoot(String),
28    PathBlob { path: String, blob_hash: String },
29}
30
31/// One immutable, content-addressed context page.
32#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
33pub struct ContextPage {
34    /// Content address of the page bytes.
35    pub page_id: String,
36    /// Page kind (task contract, tool pair, synopsis, source excerpt, …).
37    pub kind: String,
38    /// Hashes of the exact sources a summary names; empty for exact pages.
39    pub source_hashes: Vec<String>,
40    pub dependency: StateDependency,
41    pub bytes: u64,
42    /// Token cost under the route's named accountant.
43    pub tokens: u64,
44    /// Typed obligation labels this page covers. Labels derive from typed
45    /// task/path/symbol/diagnostic/test/capability/provenance fields —
46    /// never from model prose.
47    pub obligations: Vec<String>,
48    /// The turn this page was last referenced (working-set recency).
49    pub freshness_turn: u64,
50    /// Pages this page requires resident with it (e.g. a tool call and its
51    /// result form one atomic pair).
52    pub depends_on: Vec<String>,
53}
54
55/// The live state pages are validated against.
56#[derive(Debug, Clone, Default)]
57pub struct DependencyEnv {
58    pub accepted_root: String,
59    pub partial_root: Option<String>,
60    /// Current blob hash per path.
61    pub path_blobs: BTreeMap<String, String>,
62}
63
64impl StateDependency {
65    /// Whether this dependency still holds against the live state.
66    pub fn holds(&self, env: &DependencyEnv) -> bool {
67        match self {
68            StateDependency::SessionInvariant => true,
69            StateDependency::AcceptedRoot(root) => *root == env.accepted_root,
70            StateDependency::PartialCheckpointRoot(root) => {
71                env.partial_root.as_deref() == Some(root.as_str())
72            }
73            StateDependency::PathBlob { path, blob_hash } => {
74                env.path_blobs.get(path) == Some(blob_hash)
75            }
76        }
77    }
78}
79
80impl ContextPage {
81    /// Whether this page's declared dependency still holds.
82    pub fn dependency_holds(&self, env: &DependencyEnv) -> bool {
83        self.dependency.holds(env)
84    }
85}
86
87/// Definition 6's reserves over one route's context window.
88#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
89pub struct ContextBudget {
90    pub window_tokens: u64,
91    pub output_reserve: u64,
92    pub tool_reserve: u64,
93    pub guard_reserve: u64,
94}
95
96impl ContextBudget {
97    /// `β_in = β_win − β_out − β_tool − β_guard`; fails when the reserves
98    /// alone exceed the window.
99    pub fn input_allowance(&self) -> Result<u64> {
100        self.window_tokens
101            .checked_sub(self.output_reserve)
102            .and_then(|rest| rest.checked_sub(self.tool_reserve))
103            .and_then(|rest| rest.checked_sub(self.guard_reserve))
104            .ok_or_else(|| SdkError::Domain("context reserves exceed the window".into()))
105    }
106}
107
108/// The assembled resident set for one model request, or the recorded
109/// refusal when the mandatory closure cannot fit.
110#[derive(Debug, Clone, PartialEq)]
111pub enum ResidentOutcome {
112    Assembled(ResidentContext),
113    /// `ContextBudgetInfeasible`: no model call is made.
114    Infeasible {
115        required: u64,
116        allowance: u64,
117    },
118}
119
120/// The resident pages of one request, in their ledgered order.
121#[derive(Debug, Clone, PartialEq)]
122pub struct ResidentContext {
123    /// Mandatory closure first, then selected optional frames.
124    pub pages: Vec<ContextPage>,
125    /// Count of mandatory pages at the head of `pages`.
126    pub mandatory_len: usize,
127    pub resident_digest: String,
128}
129
130/// Compute the mandatory dependency closure over `pages` starting from the
131/// `mandatory` ids, following `depends_on` transitively. Order: the input
132/// page order, restricted to closure members (deterministic).
133pub fn mandatory_closure(pages: &[ContextPage], mandatory: &[String]) -> Vec<ContextPage> {
134    let by_id: BTreeMap<&str, &ContextPage> = pages
135        .iter()
136        .map(|page| (page.page_id.as_str(), page))
137        .collect();
138    let mut wanted: BTreeSet<String> = mandatory.iter().cloned().collect();
139    let mut frontier: Vec<String> = mandatory.to_vec();
140    while let Some(id) = frontier.pop() {
141        if let Some(page) = by_id.get(id.as_str()) {
142            for dependency in &page.depends_on {
143                if wanted.insert(dependency.clone()) {
144                    frontier.push(dependency.clone());
145                }
146            }
147        }
148    }
149    pages
150        .iter()
151        .filter(|page| wanted.contains(&page.page_id))
152        .cloned()
153        .collect()
154}
155
156/// Deterministic greedy weighted-coverage selection of at most `slots`
157/// synopsis frames. Ties break by page id (the content hash), so identical
158/// inputs select identically.
159pub fn select_working_set(
160    candidates: &[ContextPage],
161    weights: &BTreeMap<String, f64>,
162    slots: usize,
163) -> Vec<ContextPage> {
164    let mut covered: BTreeSet<&str> = BTreeSet::new();
165    let mut chosen_ids: BTreeSet<&str> = BTreeSet::new();
166    let mut chosen = Vec::new();
167    for _ in 0..slots {
168        let mut best: Option<(&ContextPage, f64)> = None;
169        for page in candidates {
170            if chosen_ids.contains(page.page_id.as_str()) {
171                continue;
172            }
173            let gain: f64 = page
174                .obligations
175                .iter()
176                .filter(|label| !covered.contains(label.as_str()))
177                .map(|label| weights.get(label).copied().unwrap_or(0.0))
178                .sum();
179            let better = match &best {
180                None => true,
181                Some((current, current_gain)) => {
182                    gain > *current_gain
183                        || (gain == *current_gain && page.page_id < current.page_id)
184                }
185            };
186            if better {
187                best = Some((page, gain));
188            }
189        }
190        let Some((page, gain)) = best else { break };
191        if gain <= 0.0 {
192            // No remaining frame improves declared coverage; unused space
193            // is allowed.
194            break;
195        }
196        chosen_ids.insert(page.page_id.as_str());
197        covered.extend(page.obligations.iter().map(String::as_str));
198        chosen.push(page.clone());
199    }
200    chosen
201}
202
203/// The canonical digest over a resident page-id sequence — the single rule
204/// shared by assembly and any post-assembly refit, so a fitted set and an
205/// assembled set with the same pages carry the same digest.
206pub fn resident_page_digest<'a>(ids: impl Iterator<Item = &'a str>) -> String {
207    let ids: Vec<&str> = ids.collect();
208    let mut encoder = CanonicalEncoder::new(PROMPT_DIGEST_TAG);
209    encoder.text("resident-context");
210    encoder.list(ids.into_iter());
211    encoder.digest()
212}
213
214/// Assemble the resident context per Definition 6.
215///
216/// `instruction_tokens` is `c(I_t)` for the compiled programs; `frame_tokens`
217/// is the synopsis frame bound `q`. Every candidate offered for selection
218/// must already respect `q`; pages whose dependency fails are excluded
219/// before selection.
220pub fn assemble_resident(
221    pages: &[ContextPage],
222    mandatory_ids: &[String],
223    env: &DependencyEnv,
224    budget: &ContextBudget,
225    instruction_tokens: u64,
226    frame_tokens: u64,
227    weights: &BTreeMap<String, f64>,
228) -> Result<ResidentOutcome> {
229    let allowance = budget.input_allowance()?;
230    let mandatory = mandatory_closure(pages, mandatory_ids);
231    // Gate AF fail-closed tripwire: a stale root-dependent page must never
232    // be admitted — mandatory status is no exemption. Producers demote
233    // stale pages before nominating the closure; reaching this branch is a
234    // producer defect, so the assembly refuses rather than transmits.
235    if let Some(stale) = mandatory.iter().find(|page| !page.dependency_holds(env)) {
236        return Err(SdkError::Domain(format!(
237            "gate-af: mandatory page {} depends on a state that no longer holds; \
238             a stale root-dependent page cannot be admitted",
239            stale.page_id
240        )));
241    }
242    let mandatory_cost: u64 = mandatory.iter().map(|page| page.tokens).sum();
243    if instruction_tokens + mandatory_cost > allowance {
244        return Ok(ResidentOutcome::Infeasible {
245            required: instruction_tokens + mandatory_cost,
246            allowance,
247        });
248    }
249    let remaining = allowance - instruction_tokens - mandatory_cost;
250    let slots = remaining.checked_div(frame_tokens).unwrap_or(0) as usize;
251    let mandatory_ids_set: BTreeSet<&str> =
252        mandatory.iter().map(|page| page.page_id.as_str()).collect();
253    let candidates: Vec<ContextPage> = pages
254        .iter()
255        .filter(|page| {
256            !mandatory_ids_set.contains(page.page_id.as_str())
257                && page.dependency_holds(env)
258                && page.tokens <= frame_tokens
259        })
260        .cloned()
261        .collect();
262    let selected = select_working_set(&candidates, weights, slots);
263    let mut resident = mandatory;
264    let mandatory_len = resident.len();
265    resident.extend(selected);
266    let resident_digest = resident_page_digest(resident.iter().map(|page| page.page_id.as_str()));
267    Ok(ResidentOutcome::Assembled(ResidentContext {
268        pages: resident,
269        mandatory_len,
270        resident_digest,
271    }))
272}
273
274#[cfg(test)]
275mod tests {
276    use super::*;
277
278    /// Deterministic SplitMix64 for seeded property tests (no external
279    /// dependency; failing seeds print for reproduction).
280    struct SplitMix64(u64);
281
282    impl SplitMix64 {
283        fn next(&mut self) -> u64 {
284            self.0 = self.0.wrapping_add(0x9E37_79B9_7F4A_7C15);
285            let mut z = self.0;
286            z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
287            z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
288            z ^ (z >> 31)
289        }
290    }
291
292    fn page(id: &str, tokens: u64, labels: &[&str], dependency: StateDependency) -> ContextPage {
293        ContextPage {
294            page_id: id.into(),
295            kind: "synopsis".into(),
296            source_hashes: vec![],
297            dependency,
298            bytes: tokens * 3,
299            tokens,
300            obligations: labels.iter().map(|label| label.to_string()).collect(),
301            freshness_turn: 0,
302            depends_on: vec![],
303        }
304    }
305
306    fn env() -> DependencyEnv {
307        DependencyEnv {
308            accepted_root: "root-a".into(),
309            partial_root: None,
310            path_blobs: BTreeMap::new(),
311        }
312    }
313
314    /// Gate AF fail-closed tripwire: a mandatory page whose dependency no
315    /// longer holds refuses the assembly outright — mandatory status never
316    /// admits a stale root-dependent page. Producers demote stale pages
317    /// before nominating the closure; this branch firing is a producer
318    /// defect surfaced loudly, not a silent transmission.
319    #[test]
320    fn a_stale_mandatory_page_refuses_assembly() {
321        let budget = ContextBudget {
322            window_tokens: 2_000,
323            output_reserve: 400,
324            tool_reserve: 100,
325            guard_reserve: 100,
326        };
327        let pages = vec![page(
328            "m0",
329            10,
330            &["task"],
331            StateDependency::AcceptedRoot("old-root".into()),
332        )];
333        let outcome = assemble_resident(
334            &pages,
335            &["m0".to_string()],
336            &env(),
337            &budget,
338            0,
339            64,
340            &BTreeMap::new(),
341        );
342        let error = outcome.expect_err("a stale mandatory page must refuse");
343        assert!(error.to_string().contains("gate-af"), "{error}");
344    }
345
346    #[test]
347    fn randomized_page_sets_never_exceed_the_input_allowance() {
348        for seed in 0..64u64 {
349            let mut rng = SplitMix64(seed);
350            let budget = ContextBudget {
351                window_tokens: 2_000,
352                output_reserve: 400,
353                tool_reserve: 100,
354                guard_reserve: 100,
355            };
356            let allowance = budget.input_allowance().unwrap();
357            let frame = 64;
358            let mut pages = vec![page(
359                "m0",
360                (rng.next() % 300) + 1,
361                &["task"],
362                StateDependency::SessionInvariant,
363            )];
364            for index in 0..(rng.next() % 20) {
365                pages.push(page(
366                    &format!("p{index}"),
367                    (rng.next() % frame) + 1,
368                    &["a", "b"],
369                    StateDependency::AcceptedRoot("root-a".into()),
370                ));
371            }
372            let weights: BTreeMap<String, f64> =
373                [("a".to_string(), 1.0), ("b".to_string(), 0.5)].into();
374            let instruction = rng.next() % 500;
375            let outcome = assemble_resident(
376                &pages,
377                &["m0".to_string()],
378                &env(),
379                &budget,
380                instruction,
381                frame,
382                &weights,
383            )
384            .unwrap();
385            if let ResidentOutcome::Assembled(resident) = outcome {
386                let total: u64 = resident.pages.iter().map(|p| p.tokens).sum();
387                assert!(
388                    instruction + total <= allowance,
389                    "seed {seed}: {instruction} + {total} > {allowance}"
390                );
391            }
392        }
393    }
394
395    #[test]
396    fn infeasible_mandatory_closure_refuses_before_any_call() {
397        let budget = ContextBudget {
398            window_tokens: 500,
399            output_reserve: 100,
400            tool_reserve: 50,
401            guard_reserve: 50,
402        };
403        let pages = vec![page(
404            "m0",
405            400,
406            &["task"],
407            StateDependency::SessionInvariant,
408        )];
409        let outcome = assemble_resident(
410            &pages,
411            &["m0".to_string()],
412            &env(),
413            &budget,
414            0,
415            64,
416            &BTreeMap::new(),
417        )
418        .unwrap();
419        assert!(matches!(outcome, ResidentOutcome::Infeasible { .. }));
420    }
421
422    #[test]
423    fn root_dependent_pages_invalidate_on_root_change() {
424        let stale = page(
425            "p1",
426            10,
427            &["a"],
428            StateDependency::AcceptedRoot("old".into()),
429        );
430        let fresh = page(
431            "p2",
432            10,
433            &["a"],
434            StateDependency::AcceptedRoot("root-a".into()),
435        );
436        let blob = page(
437            "p3",
438            10,
439            &["b"],
440            StateDependency::PathBlob {
441                path: "src/lib.rs".into(),
442                blob_hash: "h1".into(),
443            },
444        );
445        let mut environment = env();
446        assert!(!stale.dependency_holds(&environment));
447        assert!(fresh.dependency_holds(&environment));
448        assert!(!blob.dependency_holds(&environment));
449        environment
450            .path_blobs
451            .insert("src/lib.rs".into(), "h1".into());
452        assert!(blob.dependency_holds(&environment));
453        environment
454            .path_blobs
455            .insert("src/lib.rs".into(), "h2".into());
456        assert!(!blob.dependency_holds(&environment));
457    }
458
459    #[test]
460    fn greedy_selection_matches_exhaustive_optimum_on_small_fixtures() {
461        // Coverage is submodular; on tiny instances greedy must equal the
462        // exhaustive optimum for K = 1 and be within the guarantee for
463        // K = 2. We assert exact equality on a fixture where greedy is
464        // optimal by construction.
465        let weights: BTreeMap<String, f64> = [
466            ("a".to_string(), 3.0),
467            ("b".to_string(), 2.0),
468            ("c".to_string(), 2.0),
469        ]
470        .into();
471        let candidates = vec![
472            page("p1", 10, &["a"], StateDependency::SessionInvariant),
473            page("p2", 10, &["b", "c"], StateDependency::SessionInvariant),
474            page("p3", 10, &["b"], StateDependency::SessionInvariant),
475        ];
476        let one = select_working_set(&candidates, &weights, 1);
477        assert_eq!(one[0].page_id, "p2", "gain 4.0 beats 3.0");
478        let two = select_working_set(&candidates, &weights, 2);
479        let ids: Vec<&str> = two.iter().map(|p| p.page_id.as_str()).collect();
480        assert_eq!(ids, ["p2", "p1"], "optimum coverage 7.0");
481        // Determinism.
482        assert_eq!(select_working_set(&candidates, &weights, 2), two);
483    }
484
485    #[test]
486    fn tool_pairs_stay_atomic_through_the_mandatory_closure() {
487        let mut call = page("call1", 10, &[], StateDependency::SessionInvariant);
488        call.depends_on = vec!["result1".to_string()];
489        let result = page("result1", 10, &[], StateDependency::SessionInvariant);
490        let closure = mandatory_closure(&[call, result], &["call1".to_string()]);
491        let ids: Vec<&str> = closure.iter().map(|p| p.page_id.as_str()).collect();
492        assert_eq!(ids, ["call1", "result1"]);
493    }
494
495    #[test]
496    fn resident_digest_is_deterministic_over_page_order() {
497        let pages = vec![
498            page("m0", 10, &["task"], StateDependency::SessionInvariant),
499            page(
500                "p1",
501                10,
502                &["a"],
503                StateDependency::AcceptedRoot("root-a".into()),
504            ),
505        ];
506        let weights: BTreeMap<String, f64> = [("a".to_string(), 1.0)].into();
507        let budget = ContextBudget {
508            window_tokens: 1_000,
509            output_reserve: 100,
510            tool_reserve: 50,
511            guard_reserve: 50,
512        };
513        let run = || {
514            assemble_resident(
515                &pages,
516                &["m0".to_string()],
517                &env(),
518                &budget,
519                0,
520                64,
521                &weights,
522            )
523            .unwrap()
524        };
525        assert_eq!(run(), run());
526    }
527}
perspt_sdk/prompt/context.rs

perspt_sdk/prompt/
context.rs
