Skip to main content

khive_runtime/
blob_tree.rs

1//! Tree manifests: `{"schema":"khive-tree/v1","entries":[{path,ref,mode}]}`.
2//!
3//! A manifest is stored as one blob whose reference is the tree id. The
4//! serialization is canonical (entries sorted by path, compact JSON) so two
5//! runs that leave identical content produce identical tree references.
6
7use std::collections::BTreeMap;
8use std::io::Write;
9use std::ops::Bound::{Included, Unbounded};
10
11use serde::{Deserialize, Serialize};
12use serde_json::{json, Value};
13
14use khive_storage::{BlobStore, ContentRef};
15
16use crate::{KhiveRuntime, RuntimeError};
17
18pub const TREE_SCHEMA: &str = "khive-tree/v1";
19
20/// Largest manifest the shared load path will read back.
21pub const MAX_MANIFEST_BYTES: u64 = 8 * 1024 * 1024;
22
23#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
24pub struct TreeEntry {
25    pub path: String,
26    #[serde(rename = "ref")]
27    pub content_ref: String,
28    pub mode: u32,
29}
30
31#[derive(Debug, Clone, Serialize, Deserialize)]
32struct Manifest {
33    schema: String,
34    entries: Vec<TreeEntry>,
35}
36
37/// Validate a relative path: no empty components, no `.`/`..`, no leading
38/// `/`, no NUL, no backslash. Returns the normalized path.
39pub fn validate_relative_path(path: &str, what: &str) -> Result<String, RuntimeError> {
40    if path.is_empty() {
41        return Err(RuntimeError::InvalidInput(format!("{what} path is empty")));
42    }
43    if path.starts_with('/') {
44        return Err(RuntimeError::InvalidInput(format!(
45            "{what} path {path:?} is absolute; paths are relative to the tree root"
46        )));
47    }
48    if path.contains('\0') || path.contains('\\') {
49        return Err(RuntimeError::InvalidInput(format!(
50            "{what} path {path:?} contains a forbidden character"
51        )));
52    }
53    for component in path.split('/') {
54        if component.is_empty() || component == "." || component == ".." {
55            return Err(RuntimeError::InvalidInput(format!(
56                "{what} path {path:?} is not normalized (empty, '.' or '..' component)"
57            )));
58        }
59    }
60    Ok(path.to_string())
61}
62
63/// Validate wire entries in input order: paths, refs, modes, duplicates, and
64/// file/directory collisions. `exec.tree_put` uses this for candidate manifests.
65pub fn parse_entries(value: &Value) -> Result<Vec<TreeEntry>, RuntimeError> {
66    let items = value.as_array().ok_or_else(|| {
67        RuntimeError::InvalidInput("entries must be an array of {path, ref, mode}".into())
68    })?;
69    let mut seen = EntryIndex::default();
70    for item in items {
71        let path = item
72            .get("path")
73            .and_then(Value::as_str)
74            .ok_or_else(|| RuntimeError::InvalidInput("entry.path must be a string".into()))?;
75        let path = validate_relative_path(path, "entry")?;
76        let content_ref = item
77            .get("ref")
78            .and_then(Value::as_str)
79            .ok_or_else(|| RuntimeError::InvalidInput("entry.ref must be a string".into()))?;
80        ContentRef::from_hex(content_ref)
81            .map_err(|e| RuntimeError::InvalidInput(format!("entry {path:?} ref: {e}")))?;
82        let mode = item.get("mode").and_then(Value::as_u64).ok_or_else(|| {
83            RuntimeError::InvalidInput("entry.mode must be 644, 755 or 120000".into())
84        })?;
85        if !matches!(mode, 644 | 755 | 120000) {
86            return Err(RuntimeError::InvalidInput(format!(
87                "entry {path:?} mode must be 644, 755 or 120000; got {mode}"
88            )));
89        }
90        insert_entry(
91            &mut seen,
92            TreeEntry {
93                path,
94                content_ref: content_ref.to_string(),
95                mode: mode as u32,
96            },
97        )?;
98    }
99    Ok(seen.into_sorted_entries())
100}
101
102/// Validate captured output and loaded manifests with the same rules as wire entries.
103fn validate_entries(entries: &[TreeEntry]) -> Result<Vec<TreeEntry>, RuntimeError> {
104    let mut seen = EntryIndex::default();
105    for entry in entries {
106        let path = validate_relative_path(&entry.path, "entry")?;
107        ContentRef::from_hex(&entry.content_ref)
108            .map_err(|e| RuntimeError::InvalidInput(format!("entry {path:?} ref: {e}")))?;
109        if !matches!(entry.mode, 644 | 755 | 120000) {
110            return Err(RuntimeError::InvalidInput(format!(
111                "entry {path:?} mode must be 644, 755 or 120000; got {}",
112                entry.mode
113            )));
114        }
115        insert_entry(&mut seen, entry.clone())?;
116    }
117    Ok(seen.into_sorted_entries())
118}
119
120#[derive(Default)]
121struct EntryIndex {
122    entries: BTreeMap<String, TreeEntry>,
123    prefixes: PrefixIndex,
124    work: PrefixWork,
125}
126
127impl EntryIndex {
128    fn into_sorted_entries(self) -> Vec<TreeEntry> {
129        self.entries.into_values().collect()
130    }
131}
132
133#[derive(Default)]
134struct PrefixWork {
135    #[cfg(any(test, feature = "test-internals"))]
136    compared_bytes: usize,
137    #[cfg(any(test, feature = "test-internals"))]
138    child_lookups: usize,
139    #[cfg(any(test, feature = "test-internals"))]
140    ordered_probes: usize,
141    #[cfg(any(test, feature = "test-internals"))]
142    copied_label_bytes: usize,
143}
144
145impl PrefixWork {
146    #[inline]
147    fn copied_label(&mut self, bytes: usize) {
148        #[cfg(any(test, feature = "test-internals"))]
149        {
150            self.copied_label_bytes += bytes;
151        }
152        #[cfg(not(any(test, feature = "test-internals")))]
153        let _ = (self, bytes);
154    }
155
156    #[inline]
157    fn comparison(&mut self, bytes: usize) {
158        #[cfg(any(test, feature = "test-internals"))]
159        {
160            self.compared_bytes += bytes;
161        }
162        #[cfg(not(any(test, feature = "test-internals")))]
163        let _ = (self, bytes);
164    }
165
166    #[inline]
167    fn lookup(&mut self) {
168        #[cfg(any(test, feature = "test-internals"))]
169        {
170            self.child_lookups += 1;
171        }
172        #[cfg(not(any(test, feature = "test-internals")))]
173        let _ = self;
174    }
175
176    #[inline]
177    fn ordered_probe(&mut self) {
178        #[cfg(any(test, feature = "test-internals"))]
179        {
180            self.ordered_probes += 1;
181        }
182        #[cfg(not(any(test, feature = "test-internals")))]
183        let _ = self;
184    }
185}
186
187struct PrefixEdge {
188    label: String,
189    child: usize,
190}
191
192#[derive(Default)]
193struct PrefixNode {
194    children: BTreeMap<char, PrefixEdge>,
195    entry: bool,
196}
197
198// Arena nodes keep both memory and destruction bounded for a path with many
199// components. Edge labels compress a long unbranched path into one allocation.
200struct PrefixIndex {
201    nodes: Vec<PrefixNode>,
202}
203
204impl Default for PrefixIndex {
205    fn default() -> Self {
206        Self {
207            nodes: vec![PrefixNode::default()],
208        }
209    }
210}
211
212impl PrefixIndex {
213    fn first_parent<'a>(&self, path: &'a str, work: &mut PrefixWork) -> Option<&'a str> {
214        self.first_prefix(path, false, work)
215    }
216
217    fn first_prefix<'a>(
218        &self,
219        path: &'a str,
220        include_exact: bool,
221        work: &mut PrefixWork,
222    ) -> Option<&'a str> {
223        let mut node = 0;
224        let mut consumed = 0;
225        loop {
226            let remaining = &path[consumed..];
227            if self.nodes[node].entry
228                && (remaining.starts_with('/') || (include_exact && remaining.is_empty()))
229            {
230                return Some(&path[..consumed]);
231            }
232            let first = remaining.chars().next()?;
233            work.lookup();
234            let edge = self.nodes[node].children.get(&first)?;
235            let common = common_prefix_bytes(remaining, &edge.label, work);
236            if common != edge.label.len() {
237                return None;
238            }
239            consumed += common;
240            node = edge.child;
241        }
242    }
243
244    fn insert(&mut self, path: &str, work: &mut PrefixWork) {
245        let mut node = 0;
246        let mut consumed = 0;
247        loop {
248            let remaining = &path[consumed..];
249            let Some(first) = remaining.chars().next() else {
250                self.nodes[node].entry = true;
251                return;
252            };
253            work.lookup();
254            let Some(edge) = self.nodes[node].children.get(&first) else {
255                work.copied_label(remaining.len());
256                let child = self.nodes.len();
257                self.nodes.push(PrefixNode {
258                    entry: true,
259                    ..PrefixNode::default()
260                });
261                self.nodes[node].children.insert(
262                    first,
263                    PrefixEdge {
264                        label: remaining.to_string(),
265                        child,
266                    },
267                );
268                return;
269            };
270            let common = common_prefix_bytes(remaining, &edge.label, work);
271            if common == edge.label.len() {
272                consumed += common;
273                node = edge.child;
274                continue;
275            }
276
277            // Split only at a UTF-8 character boundary. The old path keeps
278            // its child; the new path either ends here or gains a sibling.
279            let mut edge = self.nodes[node]
280                .children
281                .remove(&first)
282                .expect("edge exists");
283            work.copied_label(edge.label.len() - common);
284            let old_suffix = edge.label.split_off(common);
285            let middle = self.nodes.len();
286            let mut middle_node = PrefixNode::default();
287            middle_node.children.insert(
288                old_suffix.chars().next().expect("nonempty suffix"),
289                PrefixEdge {
290                    label: old_suffix,
291                    child: edge.child,
292                },
293            );
294            self.nodes.push(middle_node);
295            edge.child = middle;
296            self.nodes[node].children.insert(first, edge);
297            if common == remaining.len() {
298                self.nodes[middle].entry = true;
299            } else {
300                let suffix = &remaining[common..];
301                work.copied_label(suffix.len());
302                let child = self.nodes.len();
303                self.nodes.push(PrefixNode {
304                    entry: true,
305                    ..PrefixNode::default()
306                });
307                self.nodes[middle].children.insert(
308                    suffix.chars().next().expect("nonempty suffix"),
309                    PrefixEdge {
310                        label: suffix.to_string(),
311                        child,
312                    },
313                );
314            }
315            return;
316        }
317    }
318}
319
320/// Exact-or-directory-prefix coverage, independent of manifest collision rules.
321/// Declarations are used as given; this does not validate or normalize them.
322pub struct PathCoverage {
323    prefixes: PrefixIndex,
324    #[cfg(any(test, feature = "test-internals"))]
325    build_work: PrefixWorkSnapshot,
326}
327
328/// Work performed by the shared prefix index, exposed only for test observers.
329#[cfg(any(test, feature = "test-internals"))]
330#[doc(hidden)]
331#[derive(Clone, Copy, Debug, Default)]
332pub struct PrefixWorkSnapshot {
333    pub compared_bytes: usize,
334    pub child_lookups: usize,
335    pub copied_label_bytes: usize,
336}
337
338#[cfg(any(test, feature = "test-internals"))]
339impl PrefixWork {
340    fn snapshot(&self) -> PrefixWorkSnapshot {
341        PrefixWorkSnapshot {
342            compared_bytes: self.compared_bytes,
343            child_lookups: self.child_lookups,
344            copied_label_bytes: self.copied_label_bytes,
345        }
346    }
347}
348
349impl PathCoverage {
350    pub fn new(paths: &[String]) -> Self {
351        let mut ordered: Vec<&str> = paths.iter().map(String::as_str).collect();
352        // Insertion only affects representation, never the boolean predicate.
353        // A later split cannot copy an older suffix longer than its input.
354        ordered.sort_by_key(|path| path.len());
355        let mut prefixes = PrefixIndex::default();
356        let mut build = PrefixWork::default();
357        for path in ordered {
358            prefixes.insert(path, &mut build);
359        }
360        Self {
361            prefixes,
362            #[cfg(any(test, feature = "test-internals"))]
363            build_work: build.snapshot(),
364        }
365    }
366
367    pub fn covers(&self, path: &str) -> bool {
368        self.prefixes
369            .first_prefix(path, true, &mut PrefixWork::default())
370            .is_some()
371    }
372
373    #[cfg(any(test, feature = "test-internals"))]
374    #[doc(hidden)]
375    pub fn build_work(&self) -> PrefixWorkSnapshot {
376        self.build_work
377    }
378
379    #[cfg(any(test, feature = "test-internals"))]
380    #[doc(hidden)]
381    pub fn covers_with_work(&self, path: &str) -> (bool, PrefixWorkSnapshot) {
382        let mut query = PrefixWork::default();
383        let covered = self.prefixes.first_prefix(path, true, &mut query).is_some();
384        (covered, query.snapshot())
385    }
386}
387
388fn common_prefix_bytes(left: &str, right: &str, work: &mut PrefixWork) -> usize {
389    let mut common = 0;
390    for (a, b) in left.chars().zip(right.chars()) {
391        work.comparison(a.len_utf8().max(b.len_utf8()));
392        if a != b {
393            break;
394        }
395        common += a.len_utf8();
396    }
397    common
398}
399
400/// Insert an already validated entry. Its parents and first ordered descendant
401/// find every file/directory collision without scanning all prior entries.
402fn insert_entry(seen: &mut EntryIndex, entry: TreeEntry) -> Result<(), RuntimeError> {
403    let path = &entry.path;
404    seen.work.ordered_probe();
405    if seen.entries.contains_key(path) {
406        return Err(RuntimeError::InvalidInput(format!(
407            "duplicate entry path {path:?}"
408        )));
409    }
410    // Neither a file nor a symlink can be a directory prefix of another entry.
411    if let Some(existing) = seen.prefixes.first_parent(path, &mut seen.work) {
412        return Err(RuntimeError::InvalidInput(format!(
413            "entry {path:?} conflicts with entry {existing:?} (file and directory at one path)"
414        )));
415    }
416    let prefix = format!("{path}/");
417    seen.work.ordered_probe();
418    if let Some((existing, _)) = seen
419        .entries
420        .range::<str, _>((Included(prefix.as_str()), Unbounded))
421        .next()
422    {
423        if existing.starts_with(&prefix) {
424            return Err(RuntimeError::InvalidInput(format!(
425                "entry {path:?} conflicts with entry {existing:?} (file and directory at one path)"
426            )));
427        }
428    }
429    seen.prefixes.insert(path, &mut seen.work);
430    seen.work.ordered_probe();
431    seen.entries.insert(entry.path.clone(), entry);
432    Ok(())
433}
434
435/// Serialize only a manifest that the load path can read back. The writer
436/// refuses as soon as the 8 MiB budget is crossed, before retaining more.
437fn canonical_bytes(entries: &[TreeEntry]) -> Result<Vec<u8>, RuntimeError> {
438    let mut sorted: Vec<TreeEntry> = entries.to_vec();
439    sorted.sort_by(|a, b| a.path.cmp(&b.path));
440    let manifest = Manifest {
441        schema: TREE_SCHEMA.to_string(),
442        entries: sorted,
443    };
444    struct BoundedWriter {
445        bytes: Vec<u8>,
446        exceeded: bool,
447    }
448    impl Write for BoundedWriter {
449        fn write(&mut self, buf: &[u8]) -> std::io::Result<usize> {
450            if self.bytes.len().saturating_add(buf.len()) > MAX_MANIFEST_BYTES as usize {
451                self.exceeded = true;
452                return Err(std::io::Error::new(
453                    std::io::ErrorKind::InvalidData,
454                    "tree manifest exceeds load limit",
455                ));
456            }
457            self.bytes.extend_from_slice(buf);
458            Ok(buf.len())
459        }
460
461        fn flush(&mut self) -> std::io::Result<()> {
462            Ok(())
463        }
464    }
465    let mut writer = BoundedWriter {
466        bytes: Vec::new(),
467        exceeded: false,
468    };
469    serde_json::to_writer(&mut writer, &manifest).map_err(|error| {
470        if writer.exceeded {
471            RuntimeError::InvalidInput(format!(
472                "tree manifest exceeds {MAX_MANIFEST_BYTES}-byte load limit"
473            ))
474        } else {
475            RuntimeError::InvalidInput(format!("tree manifest serialization failed: {error}"))
476        }
477    })?;
478    Ok(writer.bytes)
479}
480
481pub fn blob_store(rt: &KhiveRuntime) -> Result<std::sync::Arc<dyn BlobStore>, RuntimeError> {
482    rt.blob_store().ok_or_else(|| {
483        RuntimeError::Unconfigured("no blob store is configured for this runtime".into())
484    })
485}
486
487/// Validate and store a manifest built from wire entries; returns the tree ref.
488pub async fn store_from_value(rt: &KhiveRuntime, entries: &Value) -> Result<String, RuntimeError> {
489    let entries = parse_entries(entries)?;
490    store(rt, &entries).await
491}
492
493/// Validate and store entries from any producer; returns a loadable tree ref.
494pub async fn store(rt: &KhiveRuntime, entries: &[TreeEntry]) -> Result<String, RuntimeError> {
495    let entries = validate_entries(entries)?;
496    let bytes = canonical_bytes(&entries)?;
497    let store = blob_store(rt)?;
498    let content_ref = store.put(bytes).await?;
499    Ok(content_ref.as_str().to_string())
500}
501
502/// Load a manifest by reference. An unknown reference or a non-manifest
503/// object is an error naming the reference.
504pub async fn load(rt: &KhiveRuntime, tree_ref: &str) -> Result<Vec<TreeEntry>, RuntimeError> {
505    let content_ref = ContentRef::from_hex(tree_ref)
506        .map_err(|e| RuntimeError::InvalidInput(format!("tree ref {tree_ref:?}: {e}")))?;
507    let store = blob_store(rt)?;
508    if !store.exists(&content_ref).await? {
509        return Err(RuntimeError::NotFound(format!(
510            "tree {tree_ref} is not in the blob store"
511        )));
512    }
513    let hydrator = rt
514        .blob_hydrator()
515        .ok_or_else(|| RuntimeError::Unconfigured("exec blob hydrator is not installed".into()))?;
516    let bytes = hydrator
517        .hydrate_verified(&content_ref, MAX_MANIFEST_BYTES)
518        .await?;
519    let manifest: Manifest = serde_json::from_slice(bytes.bytes()).map_err(|e| {
520        RuntimeError::InvalidInput(format!("tree {tree_ref} is not a khive-tree manifest: {e}"))
521    })?;
522    drop(bytes);
523    if manifest.schema != TREE_SCHEMA {
524        return Err(RuntimeError::InvalidInput(format!(
525            "tree {tree_ref} has schema {:?}; expected {TREE_SCHEMA:?}",
526            manifest.schema
527        )));
528    }
529    let entries = validate_entries(&manifest.entries)?;
530    Ok(entries)
531}
532
533/// Every entry's blob must exist before materialization starts.
534pub async fn verify_blobs(rt: &KhiveRuntime, entries: &[TreeEntry]) -> Result<(), RuntimeError> {
535    let store = blob_store(rt)?;
536    for entry in entries {
537        let content_ref = ContentRef::from_hex(&entry.content_ref)
538            .map_err(|e| RuntimeError::InvalidInput(format!("entry {:?} ref: {e}", entry.path)))?;
539        if !store.exists(&content_ref).await? {
540            return Err(RuntimeError::NotFound(format!(
541                "entry {:?} references blob {} which is not in the store",
542                entry.path, entry.content_ref
543            )));
544        }
545    }
546    Ok(())
547}
548
549pub fn entries_json(entries: &[TreeEntry]) -> Value {
550    Value::Array(
551        entries
552            .iter()
553            .map(|e| json!({"path": e.path, "ref": e.content_ref, "mode": e.mode}))
554            .collect(),
555    )
556}
557
558#[cfg(test)]
559#[path = "blob_tree/tests.rs"]
560mod tests;