1use 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
20pub 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
37pub 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
63pub 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
102fn 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
198struct 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 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
320pub struct PathCoverage {
323 prefixes: PrefixIndex,
324 #[cfg(any(test, feature = "test-internals"))]
325 build_work: PrefixWorkSnapshot,
326}
327
328#[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 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
400fn 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 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
435fn 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
487pub 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
493pub 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
502pub 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
533pub 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;