salamander/
branch.rs

1//! Engine-owned branch metadata and ancestry catalog.
2
3use std::collections::{BTreeMap, HashMap};
4
5use serde::{Deserialize, Serialize};
6
7use crate::format::{BranchId, Metadata, OwnedStoredRecord};
8use crate::{Result, SalamanderError};
9
10/// Name of the default branch every database has.
11pub const DEFAULT_BRANCH_NAME: &str = "main";
12/// Maximum number of branch nodes accepted in one ancestry chain.
13pub const MAX_LINEAGE_DEPTH: usize = 64;
14
15/// Validated, stable human-readable branch label.
16#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
17pub struct BranchName(String);
18
19impl BranchName {
20    /// Maximum length of a branch name, in bytes.
21    pub const MAX_BYTES: usize = 255;
22
23    /// Validates and constructs a branch name, rejecting empty, oversized,
24    /// or NUL-containing input.
25    pub fn new(value: impl Into<String>) -> Result<Self> {
26        let value = value.into();
27        if value.is_empty() || value.as_bytes().contains(&0) {
28            return Err(SalamanderError::InvalidArgument(
29                "branch name must be nonempty and contain no NUL".into(),
30            ));
31        }
32        if value.len() > Self::MAX_BYTES {
33            return Err(SalamanderError::ResourceLimit {
34                resource: "branch name bytes",
35                actual: value.len() as u64,
36                maximum: Self::MAX_BYTES as u64,
37            });
38        }
39        Ok(Self(value))
40    }
41
42    /// The name as a string slice.
43    pub fn as_str(&self) -> &str {
44        &self.0
45    }
46}
47
48/// Whether a branch accepts new writes.
49#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
50pub enum BranchStatus {
51    /// Accepts reads and writes.
52    Active,
53    /// Retains readable history but rejects new writes.
54    Archived,
55}
56
57/// Durable identity and immutable ancestry for one branch.
58#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
59pub struct BranchInfo {
60    /// Permanent machine identity.
61    pub id: BranchId,
62    /// Permanent human-readable label.
63    pub name: BranchName,
64    /// Immediate ancestor, or `None` for the default branch.
65    pub parent: Option<BranchId>,
66    /// Exclusive upper position inherited from `parent`.
67    pub fork_position: Option<u64>,
68    /// Creation wall-clock time for diagnostics, not ordering.
69    pub created_at_unix_nanos: i64,
70    /// Caller-supplied opaque branch metadata.
71    pub metadata: BTreeMap<String, Vec<u8>>,
72    /// Current non-destructive lifecycle state.
73    pub status: BranchStatus,
74}
75
76#[derive(Clone)]
77pub(crate) struct BranchCatalog {
78    by_id: HashMap<BranchId, BranchInfo>,
79    by_name: HashMap<String, BranchId>,
80}
81
82impl BranchCatalog {
83    pub(crate) fn rebuild(
84        system_records: impl Iterator<Item = Result<OwnedStoredRecord>>,
85    ) -> Result<Self> {
86        let default = BranchInfo {
87            id: BranchId::ZERO,
88            name: BranchName::new(DEFAULT_BRANCH_NAME)?,
89            parent: None,
90            fork_position: None,
91            created_at_unix_nanos: 0,
92            metadata: Metadata::new(),
93            status: BranchStatus::Active,
94        };
95        let mut catalog = Self {
96            by_id: HashMap::from([(default.id, default.clone())]),
97            by_name: HashMap::from([(default.name.as_str().to_string(), default.id)]),
98        };
99        for item in system_records {
100            let record = item?;
101            let event_type = record.envelope.event_type.as_str();
102            if event_type != "salamander.branch.created"
103                && event_type != "salamander.branch.archived"
104            {
105                continue;
106            }
107            let info: BranchInfo = serde_json::from_slice(&record.payload).map_err(|error| {
108                SalamanderError::Corrupt {
109                    offset: record.position,
110                    reason: format!("branch metadata decode: {error}"),
111                }
112            })?;
113            if event_type == "salamander.branch.created" {
114                catalog.insert(info)?;
115            } else {
116                catalog.archive(info)?;
117            }
118        }
119        Ok(catalog)
120    }
121
122    pub(crate) fn insert(&mut self, info: BranchInfo) -> Result<()> {
123        if self.by_id.contains_key(&info.id) {
124            return Err(SalamanderError::BranchExists(
125                info.name.as_str().to_string(),
126            ));
127        }
128        if self.by_name.contains_key(info.name.as_str()) {
129            return Err(SalamanderError::BranchExists(
130                info.name.as_str().to_string(),
131            ));
132        }
133        if let Some(parent) = info.parent {
134            if !self.by_id.contains_key(&parent) {
135                return Err(SalamanderError::BranchNotFound(format!("{parent:?}")));
136            }
137        }
138        self.validate_depth(&info)?;
139        self.by_name.insert(info.name.as_str().to_string(), info.id);
140        self.by_id.insert(info.id, info);
141        Ok(())
142    }
143
144    pub(crate) fn archive(&mut self, archived: BranchInfo) -> Result<()> {
145        let current = self
146            .by_id
147            .get_mut(&archived.id)
148            .ok_or_else(|| SalamanderError::BranchNotFound(format!("{:?}", archived.id)))?;
149        if current.id == BranchId::ZERO {
150            return Err(SalamanderError::InvalidArgument(
151                "the default branch cannot be archived".into(),
152            ));
153        }
154        let mut expected = current.clone();
155        expected.status = BranchStatus::Archived;
156        if archived != expected {
157            return Err(SalamanderError::InvalidBranchAncestry(
158                "archive metadata may only change branch status".into(),
159            ));
160        }
161        *current = archived;
162        Ok(())
163    }
164
165    fn validate_depth(&self, info: &BranchInfo) -> Result<()> {
166        let mut parent = info.parent;
167        for _ in 0..MAX_LINEAGE_DEPTH {
168            let Some(id) = parent else {
169                return Ok(());
170            };
171            if id == info.id {
172                return Err(SalamanderError::InvalidBranchAncestry(
173                    "cycle detected".into(),
174                ));
175            }
176            parent = self.by_id.get(&id).and_then(|branch| branch.parent);
177        }
178        Err(SalamanderError::InvalidBranchAncestry(format!(
179            "lineage exceeds maximum depth {MAX_LINEAGE_DEPTH}"
180        )))
181    }
182
183    pub(crate) fn get(&self, id: BranchId) -> Option<&BranchInfo> {
184        self.by_id.get(&id)
185    }
186
187    pub(crate) fn named(&self, name: &str) -> Option<&BranchInfo> {
188        self.by_name.get(name).and_then(|id| self.by_id.get(id))
189    }
190
191    pub(crate) fn ancestry(&self, id: BranchId) -> Result<Vec<BranchInfo>> {
192        let mut result = Vec::new();
193        let mut current = Some(id);
194        while let Some(branch_id) = current {
195            let branch = self
196                .by_id
197                .get(&branch_id)
198                .ok_or_else(|| SalamanderError::BranchNotFound(format!("{branch_id:?}")))?;
199            result.push(branch.clone());
200            current = branch.parent;
201            if result.len() > MAX_LINEAGE_DEPTH {
202                return Err(SalamanderError::InvalidBranchAncestry(
203                    "lineage depth exceeded".into(),
204                ));
205            }
206        }
207        result.reverse();
208        Ok(result)
209    }
210
211    pub(crate) fn children(&self, id: BranchId) -> Vec<BranchInfo> {
212        let mut children: Vec<_> = self
213            .by_id
214            .values()
215            .filter(|branch| branch.parent == Some(id))
216            .cloned()
217            .collect();
218        children.sort_by(|left, right| left.name.cmp(&right.name));
219        children
220    }
221
222    pub(crate) fn replay_scopes(&self, id: BranchId, upto: u64) -> Result<Vec<(BranchId, u64)>> {
223        let ancestry = self.ancestry(id)?;
224        let mut scopes = Vec::with_capacity(ancestry.len());
225        for (index, branch) in ancestry.iter().enumerate() {
226            let upper = ancestry
227                .get(index + 1)
228                .and_then(|child| child.fork_position)
229                .unwrap_or(upto)
230                .min(upto);
231            scopes.push((branch.id, upper));
232        }
233        Ok(scopes)
234    }
235
236    pub(crate) fn common_ancestor(&self, left: BranchId, right: BranchId) -> Result<BranchInfo> {
237        let left = self.ancestry(left)?;
238        let right = self.ancestry(right)?;
239        left.into_iter()
240            .zip(right)
241            .take_while(|(a, b)| a.id == b.id)
242            .map(|(branch, _)| branch)
243            .last()
244            .ok_or_else(|| {
245                SalamanderError::InvalidBranchAncestry("branches have no common root".into())
246            })
247    }
248}
salamander/branch.rs

salamander/
branch.rs
