objects/object/
tree_path.rs

1// SPDX-License-Identifier: Apache-2.0
2//! Typed tree path resolution with per-caller leaf policies.
3
4use std::path::{Component, Path};
5
6use super::{Blob, ContentHash, Tree, TreeEntry};
7use crate::error::HeddleError;
8use crate::store::ObjectSource;
9
10/// How a tree-path walk classifies and materializes the terminal entry.
11#[derive(Debug, Clone, Copy, PartialEq, Eq)]
12pub enum LeafPolicy {
13    /// Return the terminal [`TreeEntry`] regardless of entry type (provenance).
14    Entry,
15    /// Return the blob content hash at the terminal path; symlinks are excluded (redact).
16    BlobOnly,
17    /// Load the terminal blob via [`TreeEntry::leaf_content_hash`], including symlinks
18    /// (staleness).
19    LeafContentBlob,
20}
21
22/// Successful resolution of a path within a tree.
23#[derive(Debug, Clone, PartialEq, Eq)]
24pub struct ResolvedTreeTarget {
25    pub entry: TreeEntry,
26    pub content_hash: Option<ContentHash>,
27    pub blob: Option<Blob>,
28}
29
30/// Errors surfaced by [`resolve_tree_path`] that callers map to their own messages.
31#[derive(Debug)]
32pub enum TreePathResolveError {
33    Store {
34        hash: ContentHash,
35        source: Box<HeddleError>,
36    },
37    SubtreeMissing(ContentHash),
38}
39
40impl std::error::Error for TreePathResolveError {
41    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
42        match self {
43            TreePathResolveError::Store { source, .. } => Some(source.as_ref()),
44            TreePathResolveError::SubtreeMissing(_) => None,
45        }
46    }
47}
48
49impl From<TreePathResolveError> for HeddleError {
50    fn from(value: TreePathResolveError) -> Self {
51        match value {
52            TreePathResolveError::Store { source, .. } => *source,
53            TreePathResolveError::SubtreeMissing(hash) => {
54                HeddleError::InvalidObject(format!("subtree {} missing from store", hash.short()))
55            }
56        }
57    }
58}
59
60impl std::fmt::Display for TreePathResolveError {
61    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
62        match self {
63            TreePathResolveError::Store { hash, .. } => {
64                write!(f, "failed to load tree {}", hash.short())
65            }
66            TreePathResolveError::SubtreeMissing(hash) => {
67                write!(f, "subtree {} missing from store", hash.short())
68            }
69        }
70    }
71}
72
73/// Split a repository-relative path into its first component and the remainder.
74pub fn split_path(path: &Path) -> Option<(&str, &Path)> {
75    let mut components = path.components();
76    let first = components.next()?;
77    let Component::Normal(name) = first else {
78        return None;
79    };
80    Some((name.to_str()?, components.as_path()))
81}
82
83/// Walk `path` from `root` through nested subtrees and resolve the terminal entry
84/// according to `policy`.
85///
86/// `Ok(None)` means the path is absent or terminates at the wrong entry type for the
87/// policy. Store failures and missing subtrees are policy-dependent; see
88/// [`TreePathResolveError`].
89pub fn resolve_tree_path<S: ObjectSource>(
90    store: &S,
91    root: &ContentHash,
92    path: &Path,
93    policy: LeafPolicy,
94) -> std::result::Result<Option<ResolvedTreeTarget>, TreePathResolveError> {
95    let Some(segments) = segments_for_policy(path, policy) else {
96        return Ok(None);
97    };
98    if segments.is_empty() {
99        return Ok(None);
100    }
101
102    let Some(tree) = load_subtree(store, root, policy)? else {
103        return Ok(None);
104    };
105    resolve_from_tree(store, &tree, &segments, policy)
106}
107
108#[cfg(feature = "async-source")]
109pub async fn resolve_tree_path_async<S: crate::store::AsyncObjectSource + ?Sized>(
110    store: &S,
111    root: &ContentHash,
112    path: &Path,
113    policy: LeafPolicy,
114) -> std::result::Result<Option<ResolvedTreeTarget>, TreePathResolveError> {
115    let Some(segments) = segments_for_policy(path, policy) else {
116        return Ok(None);
117    };
118    if segments.is_empty() {
119        return Ok(None);
120    }
121
122    let Some(tree) = load_subtree_async(store, root, policy).await? else {
123        return Ok(None);
124    };
125    resolve_from_tree_async(store, &tree, &segments, policy).await
126}
127
128fn segments_for_policy(path: &Path, policy: LeafPolicy) -> Option<Vec<String>> {
129    match policy {
130        LeafPolicy::Entry => path_segments(path),
131        LeafPolicy::BlobOnly => {
132            let path_str = path.to_str()?;
133            Some(
134                path_str
135                    .split('/')
136                    .filter(|part| !part.is_empty())
137                    .map(str::to_string)
138                    .collect(),
139            )
140        }
141        LeafPolicy::LeafContentBlob => Some(
142            path.to_string_lossy()
143                .split('/')
144                .map(str::to_string)
145                .collect(),
146        ),
147    }
148}
149
150fn path_segments(path: &Path) -> Option<Vec<String>> {
151    if path.as_os_str().is_empty() {
152        return None;
153    }
154    let mut segments = Vec::new();
155    for component in path.components() {
156        match component {
157            Component::Normal(name) => segments.push(name.to_str()?.to_string()),
158            _ => return None,
159        }
160    }
161    if segments.is_empty() {
162        return None;
163    }
164    Some(segments)
165}
166
167fn resolve_from_tree<S: ObjectSource>(
168    store: &S,
169    tree: &Tree,
170    segments: &[String],
171    policy: LeafPolicy,
172) -> std::result::Result<Option<ResolvedTreeTarget>, TreePathResolveError> {
173    let name = segments[0].as_str();
174    let Some(entry) = tree.get(name) else {
175        return Ok(None);
176    };
177
178    if segments.len() == 1 {
179        return resolve_leaf(store, entry.clone(), policy);
180    }
181
182    if !entry.is_tree() {
183        return Ok(None);
184    }
185    let Some(tree_hash) = entry.tree_hash() else {
186        return Ok(None);
187    };
188    let Some(subtree) = load_subtree(store, &tree_hash, policy)? else {
189        return Ok(None);
190    };
191    resolve_from_tree(store, &subtree, &segments[1..], policy)
192}
193
194#[cfg(feature = "async-source")]
195async fn resolve_from_tree_async<S: crate::store::AsyncObjectSource + ?Sized>(
196    store: &S,
197    tree: &Tree,
198    segments: &[String],
199    policy: LeafPolicy,
200) -> std::result::Result<Option<ResolvedTreeTarget>, TreePathResolveError> {
201    let name = segments[0].as_str();
202    let Some(entry) = tree.get(name) else {
203        return Ok(None);
204    };
205
206    if segments.len() == 1 {
207        return resolve_leaf_async(store, entry.clone(), policy).await;
208    }
209
210    if !entry.is_tree() {
211        return Ok(None);
212    }
213    let Some(tree_hash) = entry.tree_hash() else {
214        return Ok(None);
215    };
216    let Some(subtree) = load_subtree_async(store, &tree_hash, policy).await? else {
217        return Ok(None);
218    };
219    Box::pin(resolve_from_tree_async(store, &subtree, &segments[1..], policy)).await
220}
221
222fn resolve_leaf<S: ObjectSource>(
223    store: &S,
224    entry: TreeEntry,
225    policy: LeafPolicy,
226) -> std::result::Result<Option<ResolvedTreeTarget>, TreePathResolveError> {
227    match policy {
228        LeafPolicy::Entry => {
229            let content_hash = entry_content_hash(&entry);
230            Ok(Some(ResolvedTreeTarget {
231                entry,
232                content_hash,
233                blob: None,
234            }))
235        }
236        LeafPolicy::BlobOnly => {
237            let Some(content_hash) = entry.blob_hash() else {
238                return Ok(None);
239            };
240            Ok(Some(ResolvedTreeTarget {
241                entry,
242                content_hash: Some(content_hash),
243                blob: None,
244            }))
245        }
246        LeafPolicy::LeafContentBlob => {
247            let Some(content_hash) = entry.leaf_content_hash() else {
248                return Ok(None);
249            };
250            let blob = match store.get_blob(&content_hash) {
251                Ok(Some(blob)) => Some(blob),
252                Ok(None) => None,
253                Err(source) => {
254                    return Err(TreePathResolveError::Store {
255                        hash: content_hash,
256                        source: Box::new(source),
257                    });
258                }
259            };
260            Ok(blob.map(|blob| ResolvedTreeTarget {
261                entry,
262                content_hash: Some(content_hash),
263                blob: Some(blob),
264            }))
265        }
266    }
267}
268
269#[cfg(feature = "async-source")]
270async fn resolve_leaf_async<S: crate::store::AsyncObjectSource + ?Sized>(
271    store: &S,
272    entry: TreeEntry,
273    policy: LeafPolicy,
274) -> std::result::Result<Option<ResolvedTreeTarget>, TreePathResolveError> {
275    match policy {
276        LeafPolicy::Entry => {
277            let content_hash = entry_content_hash(&entry);
278            Ok(Some(ResolvedTreeTarget {
279                entry,
280                content_hash,
281                blob: None,
282            }))
283        }
284        LeafPolicy::BlobOnly => {
285            let Some(content_hash) = entry.blob_hash() else {
286                return Ok(None);
287            };
288            Ok(Some(ResolvedTreeTarget {
289                entry,
290                content_hash: Some(content_hash),
291                blob: None,
292            }))
293        }
294        LeafPolicy::LeafContentBlob => {
295            let Some(content_hash) = entry.leaf_content_hash() else {
296                return Ok(None);
297            };
298            let blob = match store.get_blob(&content_hash).await {
299                Ok(Some(blob)) => Some(blob),
300                Ok(None) => None,
301                Err(source) => {
302                    return Err(TreePathResolveError::Store {
303                        hash: content_hash,
304                        source: Box::new(source),
305                    });
306                }
307            };
308            Ok(blob.map(|blob| ResolvedTreeTarget {
309                entry,
310                content_hash: Some(content_hash),
311                blob: Some(blob),
312            }))
313        }
314    }
315}
316
317fn entry_content_hash(entry: &TreeEntry) -> Option<ContentHash> {
318    entry
319        .content_hash()
320        .or_else(|| entry.tree_hash())
321        .or_else(|| entry.leaf_content_hash())
322}
323
324fn load_subtree<S: ObjectSource>(
325    store: &S,
326    hash: &ContentHash,
327    policy: LeafPolicy,
328) -> std::result::Result<Option<Tree>, TreePathResolveError> {
329    match policy {
330        LeafPolicy::Entry => Ok(store.get_tree(hash).ok().flatten()),
331        LeafPolicy::LeafContentBlob => match store.get_tree(hash) {
332            Ok(tree) => Ok(tree),
333            Err(source) => Err(TreePathResolveError::Store {
334                hash: *hash,
335                source: Box::new(source),
336            }),
337        },
338        LeafPolicy::BlobOnly => match store.get_tree(hash) {
339            Ok(Some(tree)) => Ok(Some(tree)),
340            Ok(None) => Err(TreePathResolveError::SubtreeMissing(*hash)),
341            Err(source) => Err(TreePathResolveError::Store {
342                hash: *hash,
343                source: Box::new(source),
344            }),
345        },
346    }
347}
348
349#[cfg(feature = "async-source")]
350async fn load_subtree_async<S: crate::store::AsyncObjectSource + ?Sized>(
351    store: &S,
352    hash: &ContentHash,
353    policy: LeafPolicy,
354) -> std::result::Result<Option<Tree>, TreePathResolveError> {
355    match policy {
356        LeafPolicy::Entry => Ok(store.get_tree(hash).await.ok().flatten()),
357        LeafPolicy::LeafContentBlob => match store.get_tree(hash).await {
358            Ok(tree) => Ok(tree),
359            Err(source) => Err(TreePathResolveError::Store {
360                hash: *hash,
361                source: Box::new(source),
362            }),
363        },
364        LeafPolicy::BlobOnly => match store.get_tree(hash).await {
365            Ok(Some(tree)) => Ok(Some(tree)),
366            Ok(None) => Err(TreePathResolveError::SubtreeMissing(*hash)),
367            Err(source) => Err(TreePathResolveError::Store {
368                hash: *hash,
369                source: Box::new(source),
370            }),
371        },
372    }
373}
374
375#[cfg(test)]
376mod tests {
377    use super::*;
378    use crate::object::{EntryType, TreeEntry};
379    use crate::store::{InMemoryStore, ObjectStore};
380
381    fn create_blob(store: &InMemoryStore, content: &[u8]) -> ContentHash {
382        ObjectStore::put_blob(store, &Blob::from_slice(content)).unwrap()
383    }
384
385    fn create_tree(
386        store: &InMemoryStore,
387        entries: Vec<(&str, ContentHash, EntryType)>,
388    ) -> ContentHash {
389        let entries = entries
390            .into_iter()
391            .map(|(name, hash, entry_type)| match entry_type {
392                EntryType::Blob => TreeEntry::file(name.to_string(), hash, false),
393                EntryType::Tree => TreeEntry::directory(name.to_string(), hash),
394                EntryType::Symlink => TreeEntry::symlink(name.to_string(), hash),
395                EntryType::Gitlink => unreachable!("tree path tests do not build gitlinks"),
396                EntryType::Spoollink => {
397                    unreachable!("tree path tests do not build spoollinks")
398                }
399            })
400            .collect::<std::result::Result<Vec<_>, _>>()
401            .unwrap();
402        ObjectStore::put_tree(store, &Tree::from_entries(entries)).unwrap()
403    }
404
405    struct Fixture {
406        store: InMemoryStore,
407        root: ContentHash,
408        blob_hash: ContentHash,
409        symlink_hash: ContentHash,
410        nested_blob_hash: ContentHash,
411        missing_subtree_hash: ContentHash,
412    }
413
414    fn fixture() -> Fixture {
415        let store = InMemoryStore::new();
416        let blob_hash = create_blob(&store, b"blob content");
417        let symlink_hash = create_blob(&store, b"target.txt");
418        let nested_blob_hash = create_blob(&store, b"nested content");
419
420        let nested_tree = create_tree(
421            &store,
422            vec![("inner.txt", nested_blob_hash, EntryType::Blob)],
423        );
424        let missing_subtree_hash = ContentHash::compute(b"not-in-store");
425        let missing_subtree_parent = create_tree(
426            &store,
427            vec![("ghost", missing_subtree_hash, EntryType::Tree)],
428        );
429        let root = create_tree(
430            &store,
431            vec![
432                ("file.txt", blob_hash, EntryType::Blob),
433                ("link", symlink_hash, EntryType::Symlink),
434                ("dir", nested_tree, EntryType::Tree),
435                ("missing", missing_subtree_parent, EntryType::Tree),
436            ],
437        );
438
439        Fixture {
440            store,
441            root,
442            blob_hash,
443            symlink_hash,
444            nested_blob_hash,
445            missing_subtree_hash,
446        }
447    }
448
449    #[test]
450    fn leaf_content_blob_resolves_symlinks_and_nested_paths() {
451        let fx = fixture();
452
453        let file = resolve_tree_path(
454            &fx.store,
455            &fx.root,
456            Path::new("file.txt"),
457            LeafPolicy::LeafContentBlob,
458        )
459        .unwrap()
460        .unwrap();
461        assert_eq!(file.content_hash, Some(fx.blob_hash));
462        assert_eq!(file.blob.as_ref().unwrap().content(), b"blob content");
463
464        let link = resolve_tree_path(
465            &fx.store,
466            &fx.root,
467            Path::new("link"),
468            LeafPolicy::LeafContentBlob,
469        )
470        .unwrap()
471        .unwrap();
472        assert_eq!(link.content_hash, Some(fx.symlink_hash));
473        assert_eq!(link.blob.as_ref().unwrap().content(), b"target.txt");
474
475        let nested = resolve_tree_path(
476            &fx.store,
477            &fx.root,
478            Path::new("dir/inner.txt"),
479            LeafPolicy::LeafContentBlob,
480        )
481        .unwrap()
482        .unwrap();
483        assert_eq!(nested.content_hash, Some(fx.nested_blob_hash));
484
485        assert!(
486            resolve_tree_path(
487                &fx.store,
488                &fx.root,
489                Path::new("dir"),
490                LeafPolicy::LeafContentBlob,
491            )
492            .unwrap()
493            .is_none()
494        );
495        assert!(
496            resolve_tree_path(
497                &fx.store,
498                &fx.root,
499                Path::new("nope.txt"),
500                LeafPolicy::LeafContentBlob,
501            )
502            .unwrap()
503            .is_none()
504        );
505        assert!(
506            resolve_tree_path(
507                &fx.store,
508                &fx.root,
509                Path::new("missing/ghost/inner.txt"),
510                LeafPolicy::LeafContentBlob,
511            )
512            .unwrap()
513            .is_none()
514        );
515    }
516
517    #[test]
518    fn entry_policy_returns_terminal_entry_for_any_leaf_type() {
519        let fx = fixture();
520
521        let file = resolve_tree_path(&fx.store, &fx.root, Path::new("file.txt"), LeafPolicy::Entry)
522            .unwrap()
523            .unwrap();
524        assert_eq!(file.entry.blob_hash(), Some(fx.blob_hash));
525
526        let link = resolve_tree_path(&fx.store, &fx.root, Path::new("link"), LeafPolicy::Entry)
527            .unwrap()
528            .unwrap();
529        assert!(link.entry.is_symlink());
530        assert_eq!(link.entry.leaf_content_hash(), Some(fx.symlink_hash));
531
532        let dir = resolve_tree_path(&fx.store, &fx.root, Path::new("dir"), LeafPolicy::Entry)
533            .unwrap()
534            .unwrap();
535        assert!(dir.entry.is_tree());
536
537        assert!(
538            resolve_tree_path(&fx.store, &fx.root, Path::new("dir/missing"), LeafPolicy::Entry)
539                .unwrap()
540                .is_none()
541        );
542        assert!(
543            resolve_tree_path(
544                &fx.store,
545                &fx.root,
546                Path::new("missing/ghost/inner.txt"),
547                LeafPolicy::Entry,
548            )
549            .unwrap()
550            .is_none()
551        );
552    }
553
554    #[test]
555    fn blob_only_excludes_symlinks_and_errors_on_missing_subtree() {
556        let fx = fixture();
557
558        let file = resolve_tree_path(
559            &fx.store,
560            &fx.root,
561            Path::new("file.txt"),
562            LeafPolicy::BlobOnly,
563        )
564        .unwrap()
565        .unwrap();
566        assert_eq!(file.content_hash, Some(fx.blob_hash));
567
568        assert!(
569            resolve_tree_path(&fx.store, &fx.root, Path::new("link"), LeafPolicy::BlobOnly)
570                .unwrap()
571                .is_none()
572        );
573
574        let nested = resolve_tree_path(
575            &fx.store,
576            &fx.root,
577            Path::new("dir/inner.txt"),
578            LeafPolicy::BlobOnly,
579        )
580        .unwrap()
581        .unwrap();
582        assert_eq!(nested.content_hash, Some(fx.nested_blob_hash));
583
584        assert!(
585            resolve_tree_path(&fx.store, &fx.root, Path::new("dir"), LeafPolicy::BlobOnly)
586                .unwrap()
587                .is_none()
588        );
589
590        let err = resolve_tree_path(
591            &fx.store,
592            &fx.root,
593            Path::new("missing/ghost/inner.txt"),
594            LeafPolicy::BlobOnly,
595        )
596        .unwrap_err();
597        assert!(matches!(
598            err,
599            TreePathResolveError::SubtreeMissing(hash) if hash == fx.missing_subtree_hash
600        ));
601    }
602}
objects/object/tree_path.rs

objects/object/
tree_path.rs
