gix_pack/cache/delta/traverse/
mod.rs

1use std::{collections::TryReserveError, sync::atomic::AtomicBool};
2
3use gix_features::{
4    progress::{self, DynNestedProgress, Progress},
5    threading,
6    threading::{Mutable, OwnShared},
7};
8
9use crate::{
10    cache::delta::{Tree, traverse::util::ItemSliceSync, tree::Item},
11    data::EntryRange,
12};
13
14mod resolve;
15pub(crate) mod util;
16
17/// Shared access to ref-delta child indices awaiting a resolved base, keyed by its object ID.
18pub(super) type SharedRefDeltaChildren = OwnShared<Mutable<super::tree::RefDeltaChildren>>;
19
20/// Returned by [`Tree::traverse()`]
21#[derive(thiserror::Error, Debug)]
22#[allow(missing_docs)]
23pub enum Error {
24    #[error("{message}")]
25    ZlibInflate {
26        source: gix_zlib::inflate::Error,
27        message: &'static str,
28    },
29    #[error("The resolver failed to obtain the pack entry bytes for the entry at {pack_offset}")]
30    ResolveFailed { pack_offset: u64 },
31    #[error(transparent)]
32    EntryType(#[from] crate::data::entry::decode::Error),
33    #[error("One of the object inspectors failed")]
34    Inspect(#[from] Box<dyn std::error::Error + Send + Sync>),
35    #[error("Interrupted")]
36    Interrupted,
37    #[error("Entry too large to fit in memory")]
38    OutOfMemory,
39    #[error(
40        "The base at {base_pack_offset} was referred to by a ref-delta, but it was never added to the tree as if the pack was still thin."
41    )]
42    OutOfPackRefDelta {
43        /// The base's offset which was from a resolved ref-delta that didn't actually get added to the tree
44        base_pack_offset: crate::data::Offset,
45    },
46    #[error("The ref-delta base object {base_id} could not be found")]
47    UnresolvedRefDelta {
48        /// The id named by one or more unresolved ref-delta entries.
49        base_id: gix_hash::ObjectId,
50    },
51    #[error("Failed to hash an object while resolving in-pack ref-deltas")]
52    ObjectHash(#[from] gix_hash::hasher::Error),
53    #[error("Failed to spawn thread when switching to work-stealing mode")]
54    SpawnThread(#[from] std::io::Error),
55    #[error(transparent)]
56    Delta(#[from] crate::data::delta::apply::Error),
57}
58
59impl From<TryReserveError> for Error {
60    #[cold]
61    fn from(_: TryReserveError) -> Self {
62        Self::OutOfMemory
63    }
64}
65
66/// Additional context passed to the `inspect_object(…)` function of the [`Tree::traverse()`] method.
67pub struct Context<'a> {
68    /// The pack entry describing the object
69    pub entry: &'a crate::data::Entry,
70    /// The offset at which `entry` ends in the pack, useful to learn about the exact range of `entry` within the pack.
71    pub entry_end: u64,
72    /// The decompressed object itself, ready to be decoded.
73    pub decompressed: &'a [u8],
74    /// The depth at which this object resides in the delta-tree. It represents the number of base objects, with 0 indicating
75    /// an 'undeltified' object, and higher values indicating delta objects with the given number of bases.
76    pub level: u16,
77}
78
79/// Options for [`Tree::traverse()`].
80pub struct Options<'a, 's> {
81    /// is a progress instance to track progress for each object in the traversal.
82    pub object_progress: Box<dyn DynNestedProgress>,
83    /// is a progress instance to track the overall progress.
84    pub size_progress: &'s mut dyn Progress,
85    /// If `Some`, only use the given number of threads. Otherwise, the number of threads to use will be selected based on
86    /// the number of available logical cores.
87    pub thread_limit: Option<usize>,
88    /// Abort the operation if the value is `true`.
89    pub should_interrupt: &'a AtomicBool,
90    /// specifies what kind of hashes we expect to be stored in oid-delta entries, which is viable to decoding them
91    /// with the correct size.
92    pub object_hash: gix_hash::Kind,
93    /// If `Some`, rejects individual allocations above the given number of bytes while resolving decoded object and
94    /// delta result buffers. `Some(0)` rejects all non-empty allocations.
95    pub alloc_limit_bytes: Option<usize>,
96}
97
98/// The outcome of [`Tree::traverse()`]
99pub struct Outcome<T> {
100    /// The items that have no children in the pack, i.e. base objects.
101    pub roots: Vec<Item<T>>,
102    /// The items that children to a root object, i.e. delta objects.
103    pub children: Vec<Item<T>>,
104}
105
106impl<T> Tree<T>
107where
108    T: Send,
109{
110    /// Traverse this tree of delta objects with a function `inspect_object` to process each object at will.
111    ///
112    /// * `should_run_in_parallel() -> bool` returns true if the underlying pack is big enough to warrant parallel traversal at all.
113    /// * `resolve(EntrySlice, &mut Vec<u8>) -> Option<()>` resolves the bytes in the pack for the given `EntrySlice` and stores them in the
114    ///   output vector. It returns `Some(())` if the object existed in the pack, or `None` to indicate a resolution error, which would abort the
115    ///   operation as well.
116    /// * `pack_entries_end` marks one-past-the-last byte of the last entry in the pack, as the last entries size would otherwise
117    ///   be unknown as it's not part of the index file.
118    /// * `inspect_object(node_data: &mut T, progress: Progress, context: Context<ThreadLocal State>) -> Result<(), CustomError>` is a function
119    ///   running for each thread receiving fully decoded objects along with contextual information, which either succeeds with `Ok(())`
120    ///   or returns a `CustomError`.
121    ///   Note that `node_data` can be modified to allow storing maintaining computation results on a per-object basis. It should contain
122    ///   its own mutable per-thread data as required.
123    ///
124    /// This method returns a vector of all tree items, along with their potentially modified custom node data.
125    ///
126    /// _Note_ that this method consumed the Tree to assure safe parallel traversal with mutation support.
127    pub fn traverse<F, MBFN, E, R>(
128        mut self,
129        resolve: F,
130        resolve_data: &R,
131        pack_entries_end: u64,
132        inspect_object: MBFN,
133        Options {
134            thread_limit,
135            mut object_progress,
136            size_progress,
137            should_interrupt,
138            object_hash,
139            alloc_limit_bytes,
140        }: Options<'_, '_>,
141    ) -> Result<Outcome<T>, Error>
142    where
143        F: for<'r> Fn(EntryRange, &'r R) -> Option<&'r [u8]> + Send + Clone,
144        R: Send + Sync,
145        MBFN: FnMut(&mut T, &dyn Progress, Context<'_>) -> Result<(), E> + Send + Clone,
146        E: std::error::Error + Send + Sync + 'static,
147    {
148        self.set_pack_entries_end_and_resolve_ref_offsets(pack_entries_end)?;
149
150        let num_objects = self.num_items();
151        let object_counter = {
152            let progress = &mut object_progress;
153            progress.init(Some(num_objects), progress::count("objects"));
154            progress.counter()
155        };
156        size_progress.init(None, progress::bytes());
157        let size_counter = size_progress.counter();
158        let resolver_progress = object_progress.add_child("delta resolver".into());
159
160        let start = std::time::Instant::now();
161        let (mut root_items, mut child_items_vec, ref_delta_children) = self.take_root_child_and_refs();
162        let ref_delta_children =
163            (!ref_delta_children.is_empty()).then(|| OwnShared::new(Mutable::new(ref_delta_children)));
164        let child_items = ItemSliceSync::new(&mut child_items_vec);
165        // SAFETY: Both item slices come from the same Tree, whose child-index uniqueness invariant still holds.
166        #[expect(unsafe_code)]
167        unsafe {
168            resolve::all(
169                &mut root_items,
170                &child_items,
171                thread_limit,
172                num_objects,
173                object_counter,
174                size_counter,
175                &resolver_progress,
176                resolve,
177                resolve_data,
178                inspect_object,
179                ref_delta_children.clone(),
180                object_hash,
181                alloc_limit_bytes,
182                should_interrupt,
183            )?;
184        }
185
186        if let Some(ref_delta_children) = ref_delta_children {
187            if let Some((base_id, _children)) = threading::lock(&ref_delta_children).first_key_value() {
188                return Err(Error::UnresolvedRefDelta { base_id: *base_id });
189            }
190        }
191
192        object_progress.show_throughput(start);
193        size_progress.show_throughput(start);
194
195        Ok(Outcome {
196            roots: root_items,
197            children: child_items_vec,
198        })
199    }
200}
gix_pack/cache/delta/traverse/mod.rs

gix_pack/cache/delta/traverse/
mod.rs
