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

objects/object/
tree_path.rs
