perspt_sdk/search/
forest.rs

1//! The bounded search forest (PSP-10 system 19, Definitions 2–3).
2//!
3//! `AcceptedTrajectory` remains the sole owner of accepted state; a forest
4//! cannot mutate it. Branch previews use the pure gate evaluator; after
5//! selection the runtime submits exactly one candidate through the
6//! ordinary trajectory method. Internal branch states are never promoted;
7//! a partial checkpoint is private search state, neither accepted nor
8//! evidence of progress.
9
10use serde::{Deserialize, Serialize};
11
12use super::budget::{SearchLimits, SearchUsage};
13use super::domain_types::{BranchMeasurement, SearchStrategy};
14use crate::model::ModelId;
15
16/// A witness that one content-addressed state descends from another
17/// through the recorded branch and partial-checkpoint chain.
18#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
19pub struct WitnessRef {
20    /// The accepted root the chain must reach.
21    pub accepted_root: String,
22    /// State roots from the seed back to the accepted root, oldest last.
23    pub chain: Vec<String>,
24}
25
26impl WitnessRef {
27    /// A root branch's trivial witness: the seed is the accepted root.
28    pub fn root(accepted_root: impl Into<String>) -> Self {
29        let accepted_root = accepted_root.into();
30        Self {
31            chain: vec![accepted_root.clone()],
32            accepted_root,
33        }
34    }
35
36    /// Whether the chain reaches the given accepted root.
37    pub fn reaches(&self, accepted_root: &str) -> bool {
38        self.accepted_root == accepted_root
39            && self.chain.last().map(String::as_str) == Some(accepted_root)
40    }
41
42    /// Extend the chain with a child checkpoint root.
43    pub fn extend(&self, child_root: impl Into<String>) -> Self {
44        let mut chain = vec![child_root.into()];
45        chain.extend(self.chain.iter().cloned());
46        Self {
47            accepted_root: self.accepted_root.clone(),
48            chain,
49        }
50    }
51}
52
53/// A typed obligation reference carried by partial checkpoints and pages.
54#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
55pub struct ObligationRef(pub String);
56
57/// The digest of a compiled prompt program a branch runs under.
58#[derive(Debug, Clone, PartialEq, Eq, Default, Serialize, Deserialize)]
59pub struct PromptProgramDigest(pub String);
60
61/// A private, content-addressed partial checkpoint (Definition 2). Never
62/// an accepted state; a child branch may seed from it only through a
63/// witness chain that reaches the forest's accepted root.
64#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
65pub struct PartialCheckpointRef {
66    pub state_root: String,
67    pub accepted_ancestor: String,
68    pub parent_witness: WitnessRef,
69    #[serde(default, skip_serializing_if = "Option::is_none")]
70    pub correction: Option<crate::residual::CorrectionPacketRef>,
71    #[serde(default, skip_serializing_if = "Vec::is_empty")]
72    pub remaining_obligations: Vec<ObligationRef>,
73    pub evidence_digest: String,
74}
75
76/// A branch's lifecycle state (system 19's diagram).
77#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
78#[serde(rename_all = "snake_case", tag = "state")]
79pub enum SearchBranchState {
80    Ready,
81    Running,
82    PartialCheckpointed { checkpoint: PartialCheckpointRef },
83    CandidateMeasured { measurement: BranchMeasurement },
84    Selected,
85    Rejected { reason: String },
86    Abandoned { reason: String },
87    Contained { certificate_id: String },
88}
89
90/// One isolated branch of the forest.
91#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
92pub struct SearchBranch {
93    pub branch_id: String,
94    #[serde(default, skip_serializing_if = "Option::is_none")]
95    pub parent_branch: Option<String>,
96    /// Must equal the forest's accepted root.
97    pub accepted_ancestor: String,
98    /// The accepted root, or a parent's partial-checkpoint root.
99    pub seed_checkpoint: String,
100    /// Proof the seed descends from the accepted ancestor.
101    pub seed_witness: WitnessRef,
102    pub strategy: SearchStrategy,
103    pub route: ModelId,
104    pub prompt_program: PromptProgramDigest,
105    pub state: SearchBranchState,
106    pub usage: SearchUsage,
107}
108
109/// The forest rooted at one accepted state (Definition 2).
110#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
111pub struct SearchForest {
112    pub forest_id: String,
113    pub task_id: String,
114    pub node_id: String,
115    pub generation: u32,
116    /// State root of the immutable accepted root `x_k`.
117    pub accepted_root: String,
118    pub branches: Vec<SearchBranch>,
119    pub limits: SearchLimits,
120    pub usage: SearchUsage,
121}
122
123impl SearchForest {
124    /// Validate the structural invariants: every branch's accepted ancestor
125    /// is the forest root and every seed witness reaches it.
126    pub fn validate(&self) -> crate::error::Result<()> {
127        for branch in &self.branches {
128            if branch.accepted_ancestor != self.accepted_root {
129                return Err(crate::error::SdkError::Domain(format!(
130                    "branch {} does not share the forest's accepted root",
131                    branch.branch_id
132                )));
133            }
134            if !branch.seed_witness.reaches(&self.accepted_root) {
135                return Err(crate::error::SdkError::Domain(format!(
136                    "branch {} seed witness does not reach the accepted root",
137                    branch.branch_id
138                )));
139            }
140        }
141        Ok(())
142    }
143}
144
145/// Bounded cross-branch context (system 21). Never another branch's raw
146/// conversation.
147#[derive(Debug, Clone, PartialEq, Default, Serialize, Deserialize)]
148pub struct SearchEvidenceDigest {
149    pub residual_clusters: Vec<String>,
150    pub no_good_refs: Vec<String>,
151    pub tried_strategies: Vec<String>,
152}
153
154#[cfg(test)]
155mod tests {
156    use super::*;
157
158    #[test]
159    fn witness_chains_reach_or_are_refused() {
160        let root = WitnessRef::root("root-a");
161        assert!(root.reaches("root-a"));
162        assert!(!root.reaches("root-b"));
163        let child = root.extend("partial-1");
164        assert!(child.reaches("root-a"));
165        assert_eq!(child.chain, vec!["partial-1", "root-a"]);
166        let broken = WitnessRef {
167            accepted_root: "root-a".into(),
168            chain: vec!["partial-1".into()],
169        };
170        assert!(!broken.reaches("root-a"), "chain must end at the root");
171    }
172}
perspt_sdk/search/forest.rs

perspt_sdk/search/
forest.rs
