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            })
397            .collect::<std::result::Result<Vec<_>, _>>()
398            .unwrap();
399        ObjectStore::put_tree(store, &Tree::from_entries(entries)).unwrap()
400    }
401
402    struct Fixture {
403        store: InMemoryStore,
404        root: ContentHash,
405        blob_hash: ContentHash,
406        symlink_hash: ContentHash,
407        nested_blob_hash: ContentHash,
408        missing_subtree_hash: ContentHash,
409    }
410
411    fn fixture() -> Fixture {
412        let store = InMemoryStore::new();
413        let blob_hash = create_blob(&store, b"blob content");
414        let symlink_hash = create_blob(&store, b"target.txt");
415        let nested_blob_hash = create_blob(&store, b"nested content");
416
417        let nested_tree = create_tree(
418            &store,
419            vec![("inner.txt", nested_blob_hash, EntryType::Blob)],
420        );
421        let missing_subtree_hash = ContentHash::compute(b"not-in-store");
422        let missing_subtree_parent = create_tree(
423            &store,
424            vec![("ghost", missing_subtree_hash, EntryType::Tree)],
425        );
426        let root = create_tree(
427            &store,
428            vec![
429                ("file.txt", blob_hash, EntryType::Blob),
430                ("link", symlink_hash, EntryType::Symlink),
431                ("dir", nested_tree, EntryType::Tree),
432                ("missing", missing_subtree_parent, EntryType::Tree),
433            ],
434        );
435
436        Fixture {
437            store,
438            root,
439            blob_hash,
440            symlink_hash,
441            nested_blob_hash,
442            missing_subtree_hash,
443        }
444    }
445
446    #[test]
447    fn leaf_content_blob_resolves_symlinks_and_nested_paths() {
448        let fx = fixture();
449
450        let file = resolve_tree_path(
451            &fx.store,
452            &fx.root,
453            Path::new("file.txt"),
454            LeafPolicy::LeafContentBlob,
455        )
456        .unwrap()
457        .unwrap();
458        assert_eq!(file.content_hash, Some(fx.blob_hash));
459        assert_eq!(file.blob.as_ref().unwrap().content(), b"blob content");
460
461        let link = resolve_tree_path(
462            &fx.store,
463            &fx.root,
464            Path::new("link"),
465            LeafPolicy::LeafContentBlob,
466        )
467        .unwrap()
468        .unwrap();
469        assert_eq!(link.content_hash, Some(fx.symlink_hash));
470        assert_eq!(link.blob.as_ref().unwrap().content(), b"target.txt");
471
472        let nested = resolve_tree_path(
473            &fx.store,
474            &fx.root,
475            Path::new("dir/inner.txt"),
476            LeafPolicy::LeafContentBlob,
477        )
478        .unwrap()
479        .unwrap();
480        assert_eq!(nested.content_hash, Some(fx.nested_blob_hash));
481
482        assert!(
483            resolve_tree_path(
484                &fx.store,
485                &fx.root,
486                Path::new("dir"),
487                LeafPolicy::LeafContentBlob,
488            )
489            .unwrap()
490            .is_none()
491        );
492        assert!(
493            resolve_tree_path(
494                &fx.store,
495                &fx.root,
496                Path::new("nope.txt"),
497                LeafPolicy::LeafContentBlob,
498            )
499            .unwrap()
500            .is_none()
501        );
502        assert!(
503            resolve_tree_path(
504                &fx.store,
505                &fx.root,
506                Path::new("missing/ghost/inner.txt"),
507                LeafPolicy::LeafContentBlob,
508            )
509            .unwrap()
510            .is_none()
511        );
512    }
513
514    #[test]
515    fn entry_policy_returns_terminal_entry_for_any_leaf_type() {
516        let fx = fixture();
517
518        let file = resolve_tree_path(&fx.store, &fx.root, Path::new("file.txt"), LeafPolicy::Entry)
519            .unwrap()
520            .unwrap();
521        assert_eq!(file.entry.blob_hash(), Some(fx.blob_hash));
522
523        let link = resolve_tree_path(&fx.store, &fx.root, Path::new("link"), LeafPolicy::Entry)
524            .unwrap()
525            .unwrap();
526        assert!(link.entry.is_symlink());
527        assert_eq!(link.entry.leaf_content_hash(), Some(fx.symlink_hash));
528
529        let dir = resolve_tree_path(&fx.store, &fx.root, Path::new("dir"), LeafPolicy::Entry)
530            .unwrap()
531            .unwrap();
532        assert!(dir.entry.is_tree());
533
534        assert!(
535            resolve_tree_path(&fx.store, &fx.root, Path::new("dir/missing"), LeafPolicy::Entry)
536                .unwrap()
537                .is_none()
538        );
539        assert!(
540            resolve_tree_path(
541                &fx.store,
542                &fx.root,
543                Path::new("missing/ghost/inner.txt"),
544                LeafPolicy::Entry,
545            )
546            .unwrap()
547            .is_none()
548        );
549    }
550
551    #[test]
552    fn blob_only_excludes_symlinks_and_errors_on_missing_subtree() {
553        let fx = fixture();
554
555        let file = resolve_tree_path(
556            &fx.store,
557            &fx.root,
558            Path::new("file.txt"),
559            LeafPolicy::BlobOnly,
560        )
561        .unwrap()
562        .unwrap();
563        assert_eq!(file.content_hash, Some(fx.blob_hash));
564
565        assert!(
566            resolve_tree_path(&fx.store, &fx.root, Path::new("link"), LeafPolicy::BlobOnly)
567                .unwrap()
568                .is_none()
569        );
570
571        let nested = resolve_tree_path(
572            &fx.store,
573            &fx.root,
574            Path::new("dir/inner.txt"),
575            LeafPolicy::BlobOnly,
576        )
577        .unwrap()
578        .unwrap();
579        assert_eq!(nested.content_hash, Some(fx.nested_blob_hash));
580
581        assert!(
582            resolve_tree_path(&fx.store, &fx.root, Path::new("dir"), LeafPolicy::BlobOnly)
583                .unwrap()
584                .is_none()
585        );
586
587        let err = resolve_tree_path(
588            &fx.store,
589            &fx.root,
590            Path::new("missing/ghost/inner.txt"),
591            LeafPolicy::BlobOnly,
592        )
593        .unwrap_err();
594        assert!(matches!(
595            err,
596            TreePathResolveError::SubtreeMissing(hash) if hash == fx.missing_subtree_hash
597        ));
598    }
599}
objects/object/tree_path.rs

objects/object/
tree_path.rs
