gix_pack/index/traverse/
mod.rs

1use std::sync::atomic::AtomicBool;
2
3use gix_features::{parallel, progress::Progress};
4
5use crate::index;
6
7mod reduce;
8///
9pub mod with_index;
10///
11pub mod with_lookup;
12use reduce::Reducer;
13
14mod error;
15pub use error::Error;
16use gix_features::progress::DynNestedProgress;
17
18mod types;
19pub use types::{Algorithm, ProgressId, SafetyCheck, Statistics};
20
21/// Traversal options for [`index::File::traverse()`].
22#[derive(Debug, Clone)]
23pub struct Options<F> {
24    /// The algorithm to employ.
25    pub traversal: Algorithm,
26    /// If `Some`, only use the given number of threads. Otherwise, the number of threads to use will be selected based on
27    /// the number of available logical cores.
28    pub thread_limit: Option<usize>,
29    /// The kinds of safety checks to perform.
30    pub check: SafetyCheck,
31    /// If `Some`, rejects individual allocations above the given number of bytes while resolving decoded object and
32    /// delta result buffers during delta-tree traversal. `Some(0)` rejects all non-empty allocations.
33    pub alloc_limit_bytes: Option<usize>,
34    /// A function to create a pack cache
35    pub make_pack_lookup_cache: F,
36}
37
38impl Default for Options<fn() -> crate::cache::Never> {
39    fn default() -> Self {
40        Options {
41            check: Default::default(),
42            traversal: Default::default(),
43            thread_limit: None,
44            alloc_limit_bytes: None,
45            make_pack_lookup_cache: || crate::cache::Never,
46        }
47    }
48}
49
50/// The outcome of the [`traverse()`][index::File::traverse()] method.
51pub struct Outcome {
52    /// The checksum obtained when hashing the file, which matched the checksum contained within the file.
53    pub actual_index_checksum: gix_hash::ObjectId,
54    /// The statistics obtained during traversal.
55    pub statistics: Statistics,
56}
57
58/// Traversal of pack data files using an index file
59impl<T> index::File<T>
60where
61    T: crate::FileData + Sync,
62{
63    /// Iterate through all _decoded objects_ in the given `pack` and handle them with a `Processor`.
64    /// The return value is (pack-checksum, [`Outcome`], `progress`), thus the pack traversal will always verify
65    /// the whole packs checksum to assure it was correct. In case of bit-rod, the operation will abort early without
66    /// verifying all objects using the [interrupt mechanism][gix_features::interrupt] mechanism.
67    ///
68    /// # Algorithms
69    ///
70    /// Using the [`Options::traversal`] field one can chose between two algorithms providing different tradeoffs. Both invoke
71    /// `new_processor()` to create functions receiving decoded objects, their object kind, index entry and a progress instance to provide
72    /// progress information.
73    ///
74    /// * [`Algorithm::DeltaTreeLookup`] builds an index to avoid any unnecessary computation while resolving objects, avoiding
75    ///   the need for a cache entirely, rendering `new_cache()` unused.
76    ///   One could also call [`traverse_with_index()`][index::File::traverse_with_index()] directly.
77    /// * [`Algorithm::Lookup`] uses a cache created by `new_cache()` to avoid having to re-compute all bases of a delta-chain while
78    ///   decoding objects.
79    ///   One could also call [`traverse_with_lookup()`][index::File::traverse_with_lookup()] directly.
80    ///
81    /// Use [`thread_limit`][Options::thread_limit] to further control parallelism and [`check`][SafetyCheck] to define how much the passed
82    /// objects shall be verified beforehand.
83    pub fn traverse<C, Processor, E, F, D>(
84        &self,
85        pack: &crate::data::File<D>,
86        progress: &mut dyn DynNestedProgress,
87        should_interrupt: &AtomicBool,
88        processor: Processor,
89        Options {
90            traversal,
91            thread_limit,
92            check,
93            alloc_limit_bytes,
94            make_pack_lookup_cache,
95        }: Options<F>,
96    ) -> Result<Outcome, Error<E>>
97    where
98        C: crate::cache::DecodeEntry,
99        E: std::error::Error + Send + Sync + 'static,
100        Processor: FnMut(gix_object::Kind, &[u8], &index::Entry, &dyn Progress) -> Result<(), E> + Send + Clone,
101        F: Fn() -> C + Send + Clone,
102        D: crate::FileData + Send + Sync,
103    {
104        match traversal {
105            Algorithm::Lookup => self.traverse_with_lookup(
106                processor,
107                pack,
108                progress,
109                should_interrupt,
110                with_lookup::Options {
111                    thread_limit,
112                    check,
113                    make_pack_lookup_cache,
114                },
115            ),
116            Algorithm::DeltaTreeLookup => self.traverse_with_index(
117                pack,
118                processor,
119                progress,
120                should_interrupt,
121                with_index::Options {
122                    check,
123                    thread_limit,
124                    alloc_limit_bytes,
125                },
126            ),
127        }
128    }
129
130    fn possibly_verify<E, D>(
131        &self,
132        pack: &crate::data::File<D>,
133        check: SafetyCheck,
134        pack_progress: &mut dyn Progress,
135        index_progress: &mut dyn Progress,
136        should_interrupt: &AtomicBool,
137    ) -> Result<gix_hash::ObjectId, Error<E>>
138    where
139        E: std::error::Error + Send + Sync + 'static,
140        D: crate::FileData + Send + Sync,
141    {
142        Ok(if check.file_checksum() {
143            pack.checksum()
144                .verify(&self.pack_checksum())
145                .map_err(Error::PackMismatch)?;
146            let (pack_res, id) = parallel::join(
147                move || pack.verify_checksum(pack_progress, should_interrupt),
148                move || self.verify_checksum(index_progress, should_interrupt),
149            );
150            pack_res.map_err(Error::PackVerify)?;
151            id.map_err(Error::IndexVerify)?
152        } else {
153            self.index_checksum()
154        })
155    }
156
157    #[expect(clippy::too_many_arguments)]
158    fn decode_and_process_entry<C, E, D>(
159        &self,
160        check: SafetyCheck,
161        pack: &crate::data::File<D>,
162        cache: &mut C,
163        buf: &mut Vec<u8>,
164        inflate: &mut gix_zlib::Inflate,
165        progress: &mut dyn Progress,
166        index_entry: &index::Entry,
167        processor: &mut impl FnMut(gix_object::Kind, &[u8], &index::Entry, &dyn Progress) -> Result<(), E>,
168    ) -> Result<crate::data::decode::entry::Outcome, Error<E>>
169    where
170        C: crate::cache::DecodeEntry,
171        E: std::error::Error + Send + Sync + 'static,
172        D: crate::FileData + Send + Sync,
173    {
174        let pack_entry = pack.entry(index_entry.pack_offset)?;
175        let pack_entry_data_offset = pack_entry.data_offset;
176        let entry_stats = pack
177            .decode_entry(
178                pack_entry,
179                buf,
180                inflate,
181                &|id, _| {
182                    let index = self.lookup(id)?;
183                    pack.entry(self.pack_offset_at_index(index))
184                        .ok()
185                        .map(crate::data::decode::entry::ResolvedBase::InPack)
186                },
187                cache,
188            )
189            .map_err(|e| Error::PackDecode {
190                source: e,
191                id: index_entry.oid,
192                offset: index_entry.pack_offset,
193            })?;
194        let object_kind = entry_stats.kind;
195        let header_size = (pack_entry_data_offset - index_entry.pack_offset) as usize;
196        let entry_len = header_size + entry_stats.compressed_size;
197
198        process_entry(
199            check,
200            object_kind,
201            buf,
202            index_entry,
203            || pack.entry_crc32(index_entry.pack_offset, entry_len),
204            progress,
205            processor,
206        )?;
207        Ok(entry_stats)
208    }
209}
210
211fn process_entry<E>(
212    check: SafetyCheck,
213    object_kind: gix_object::Kind,
214    decompressed: &[u8],
215    index_entry: &index::Entry,
216    pack_entry_crc32: impl FnOnce() -> u32,
217    progress: &dyn Progress,
218    processor: &mut impl FnMut(gix_object::Kind, &[u8], &index::Entry, &dyn Progress) -> Result<(), E>,
219) -> Result<(), Error<E>>
220where
221    E: std::error::Error + Send + Sync + 'static,
222{
223    if check.object_checksum() {
224        gix_object::Data::new(decompressed, object_kind, index_entry.oid.kind())
225            .verify_checksum(&index_entry.oid)
226            .map_err(|source| Error::PackObjectVerify {
227                offset: index_entry.pack_offset,
228                source,
229            })?;
230        if let Some(desired_crc32) = index_entry.crc32 {
231            let actual_crc32 = pack_entry_crc32();
232            if actual_crc32 != desired_crc32 {
233                return Err(Error::Crc32Mismatch {
234                    actual: actual_crc32,
235                    expected: desired_crc32,
236                    offset: index_entry.pack_offset,
237                    kind: object_kind,
238                });
239            }
240        }
241    }
242    processor(object_kind, decompressed, index_entry, progress).map_err(Error::Processor)
243}
gix_pack/index/traverse/mod.rs

gix_pack/index/traverse/
mod.rs
