git_zero_core/pack/
materialize.rs

1//! Complete, caller-owned pack materialization with constant-stack indexing.
2use super::{DeltaLimits, Entry, EntryKind, Reader, apply_delta};
3use crate::{
4    Error, Object, ObjectId, ObjectKind, Result,
5    object::Tree,
6    zlib::{InflateLimits, WINDOW_SIZE},
7};
8
9/// Storage for one imported object. Initialize with Default; only materialize
10/// populates entries. The C representation lets adapters allocate this storage
11/// without introducing an allocator into the core.
12#[repr(C)]
13#[derive(Clone, Copy, Debug, Default)]
14pub struct MaterializedEntry {
15    id: [u8; 20],
16    kind: u32,
17    pack_offset: u64,
18    offset: usize,
19    length: usize,
20    depth: u32,
21}
22
23impl MaterializedEntry {
24    pub fn id(&self) -> ObjectId {
25        ObjectId::Sha1(self.id)
26    }
27    pub fn kind(&self) -> Result<ObjectKind> {
28        match self.kind {
29            1 => Ok(ObjectKind::Commit),
30            2 => Ok(ObjectKind::Tree),
31            3 => Ok(ObjectKind::Blob),
32            4 => Ok(ObjectKind::Tag),
33            _ => Err(Error::InvalidObject),
34        }
35    }
36    pub fn offset(&self) -> usize {
37        self.offset
38    }
39    pub fn length(&self) -> usize {
40        self.length
41    }
42    pub fn delta_depth(&self) -> u32 {
43        self.depth
44    }
45    pub fn pack_offset(&self) -> u64 {
46        self.pack_offset
47    }
48}
49
50#[derive(Clone, Copy, Debug)]
51pub struct MaterializeLimits {
52    pub inflate: InflateLimits,
53    pub delta: DeltaLimits,
54    pub max_passes: u32,
55    /// Counts every inflated entry on each pass, even already-resolved entries.
56    pub max_decoded_bytes_per_pass: u64,
57    /// Maximum index slots inspected for delta bases across all passes.
58    pub max_base_probes: u64,
59    /// Encoded tree bytes read, including alias rescans, across the whole import.
60    pub max_tree_validation_bytes: u64,
61}
62
63/// An immutable, ID-sorted index and materialized bodies. The input pack and
64/// decoding scratch are not retained. This validates objects and tree structure,
65/// not graph closure, refs or commit/tag header semantics.
66pub struct MaterializedPack<'a> {
67    index: &'a [MaterializedEntry],
68    arena: &'a [u8],
69}
70
71impl<'a> MaterializedPack<'a> {
72    pub fn entries(&self) -> &'a [MaterializedEntry] {
73        self.index
74    }
75    pub fn bytes_used(&self) -> usize {
76        self.arena.len()
77    }
78    pub fn object(&self, position: usize) -> Option<Object<'a>> {
79        let entry = self.index.get(position)?;
80        Some(Object {
81            kind: entry.kind().ok()?,
82            data: self
83                .arena
84                .get(entry.offset..entry.offset.checked_add(entry.length)?)?,
85        })
86    }
87    pub fn find(&self, id: ObjectId) -> Option<Object<'a>> {
88        let entry = find_materialized(self.index, id)?;
89        Some(Object {
90            kind: entry.kind().ok()?,
91            data: self
92                .arena
93                .get(entry.offset..entry.offset.checked_add(entry.length)?)?,
94        })
95    }
96}
97
98/// Find metadata in the sorted index produced by materialize. Adapters retaining
99/// the raw index must keep it immutable. Default/unpopulated entries are omitted.
100pub fn find_materialized(index: &[MaterializedEntry], id: ObjectId) -> Option<&MaterializedEntry> {
101    let ObjectId::Sha1(id) = id else {
102        return None;
103    };
104    let position = index.binary_search_by_key(&id, |entry| entry.id).ok()?;
105    let entry = &index[position];
106    (entry.kind != 0).then_some(entry)
107}
108
109/// Import a checksummed, non-thin SHA-1 pack into caller-owned index/body storage.
110/// Index needs object_count slots; excess slots remain untouched. Each pass
111/// resets the reader and can resolve backward OFS or forward REF deltas against
112/// earlier materialized objects. Depth, instruction, inflation, pass and work
113/// limits are explicit; missing/external bases fail rather than doing I/O.
114///
115/// The ID index uses iterative heap sort, with constant stack space. Resolution
116/// charges every metadata probe and tree-validation read against explicit work
117/// budgets, and may reinflate entries across passes. Discard partial storage on
118/// error; a retry reinitializes the index. No allocation, recursion or platform
119/// I/O is used.
120///
121/// ```
122/// # #[cfg(feature = "write")]
123/// # fn example() -> git_zero_core::Result<()> {
124/// use git_zero_core::{Snapshot, ObjectKind, object::Commit, io::SliceWriter, pack,
125///     zlib::{InflateLimits, WINDOW_SIZE}};
126/// let mut tree = [0; 256];
127/// let mut commit = [0; 512];
128/// let source = Snapshot::new(&[], &mut tree, &mut commit)?;
129/// let mut wire = [0; 2048];
130/// let mut output = SliceWriter::new(&mut wire);
131/// pack::write(&source, &mut output)?;
132/// let mut index = [pack::MaterializedEntry::default(); 2];
133/// let mut arena = [0; 1024];
134/// let mut scratch = [0; 512];
135/// let mut window = [0; WINDOW_SIZE];
136/// let limits = pack::MaterializeLimits {
137///     inflate: InflateLimits { max_output: 512, max_ratio: 1024, ratio_slack: 64 },
138///     delta: pack::DeltaLimits { max_output: 512, max_instructions: 512, max_depth: 64 },
139///     max_passes: 65,
140///     max_decoded_bytes_per_pass: 1024,
141///     max_base_probes: 4096,
142///     max_tree_validation_bytes: 4096,
143/// };
144/// let objects = pack::materialize(output.as_bytes(), &mut index, &mut arena,
145///     &mut scratch, &mut window, limits)?;
146/// let head = objects.entries().iter().find(|entry| entry.kind() == Ok(ObjectKind::Commit)).unwrap();
147/// let commit = Commit::parse(objects.find(head.id()).unwrap().data)?;
148/// assert_eq!(objects.find(commit.tree()).unwrap().kind, ObjectKind::Tree);
149/// # Ok(()) }
150/// # #[cfg(feature = "write")]
151/// # example().unwrap();
152/// ```
153pub fn materialize<'a>(
154    pack: &[u8],
155    index: &'a mut [MaterializedEntry],
156    arena: &'a mut [u8],
157    scratch: &mut [u8],
158    window: &mut [u8; WINDOW_SIZE],
159    limits: MaterializeLimits,
160) -> Result<MaterializedPack<'a>> {
161    let count = Reader::new(pack)?.object_count() as usize;
162    let index = index.get_mut(..count).ok_or(Error::BufferTooSmall)?;
163    index.fill(MaterializedEntry::default());
164    if count == 0 {
165        return Ok(MaterializedPack {
166            index,
167            arena: &arena[..0],
168        });
169    }
170    let mut used = 0;
171    let mut remaining = count;
172    let mut base_probes = limits.max_base_probes;
173    let mut tree_bytes = limits.max_tree_validation_bytes;
174    for _ in 0..limits.max_passes {
175        let mut reader = Reader::new(pack)?;
176        let mut progress = false;
177        let mut decoded_bytes = 0_u64;
178        for i in 0..count {
179            decoded_bytes =
180                decoded_bytes.saturating_add(reader.next_entry_size()?.ok_or(Error::CorruptPack)?);
181            if decoded_bytes > limits.max_decoded_bytes_per_pass {
182                return Err(Error::LimitExceeded);
183            }
184            let entry = reader
185                .read_entry(scratch, window, limits.inflate)?
186                .ok_or(Error::CorruptPack)?;
187            if index[i].kind != 0 {
188                continue;
189            }
190            let base = if remaining == count {
191                None
192            } else {
193                find_base(entry.kind(), index, &mut base_probes)?
194            };
195            if !matches!(entry.kind(), EntryKind::Object(_)) && base.is_none() {
196                continue;
197            }
198            let (previous, output) = arena.split_at_mut(used);
199            let (object, depth) = materialize_entry(&entry, base, previous, output, limits.delta)?;
200            if object.kind == ObjectKind::Tree {
201                Tree::parse_with_budget(object.data, &mut tree_bytes)?;
202            }
203            let ObjectId::Sha1(id) = object.id() else {
204                return Err(Error::Unsupported);
205            };
206            index[i] = MaterializedEntry {
207                id,
208                kind: object.kind as u32,
209                pack_offset: entry.offset(),
210                offset: used,
211                length: object.data.len(),
212                depth,
213            };
214            used += object.data.len();
215            remaining -= 1;
216            progress = true;
217        }
218        reader.finish()?;
219        if remaining == 0 {
220            sort_index(index);
221            return Ok(MaterializedPack {
222                index,
223                arena: &arena[..used],
224            });
225        }
226        if !progress {
227            return Err(Error::CorruptPack);
228        }
229    }
230    Err(Error::LimitExceeded)
231}
232
233// Charge every inspected slot, including unresolved entries, before matching.
234fn find_base(
235    kind: EntryKind,
236    index: &[MaterializedEntry],
237    probes: &mut u64,
238) -> Result<Option<MaterializedEntry>> {
239    if matches!(kind, EntryKind::Object(_)) {
240        return Ok(None);
241    }
242    for candidate in index {
243        *probes = probes.checked_sub(1).ok_or(Error::LimitExceeded)?;
244        let matches = match kind {
245            EntryKind::OffsetDelta { base_offset } => candidate.pack_offset == base_offset,
246            EntryKind::ReferenceDelta { base_id } => candidate.id.as_slice() == base_id.as_bytes(),
247            EntryKind::Object(_) => false,
248        };
249        if candidate.kind != 0 && matches {
250            return Ok(Some(*candidate));
251        }
252    }
253    Ok(None)
254}
255
256// Prior bodies and the destination are disjoint regions of the caller's arena.
257fn materialize_entry<'out>(
258    entry: &Entry<'_>,
259    base: Option<MaterializedEntry>,
260    previous: &[u8],
261    output: &'out mut [u8],
262    limits: DeltaLimits,
263) -> Result<(Object<'out>, u32)> {
264    if let Some(base) = base {
265        if base.depth >= limits.max_depth {
266            return Err(Error::LimitExceeded);
267        }
268        let end = base
269            .offset
270            .checked_add(base.length)
271            .ok_or(Error::CorruptPack)?;
272        let body = previous.get(base.offset..end).ok_or(Error::CorruptPack)?;
273        let object = apply_delta(
274            Object {
275                kind: base.kind()?,
276                data: body,
277            },
278            entry.data(),
279            output,
280            limits,
281        )?;
282        Ok((object, base.depth + 1))
283    } else {
284        let EntryKind::Object(kind) = entry.kind() else {
285            return Err(Error::CorruptPack);
286        };
287        let output = output
288            .get_mut(..entry.data().len())
289            .ok_or(Error::BufferTooSmall)?;
290        output.copy_from_slice(entry.data());
291        Ok((Object { kind, data: output }, 0))
292    }
293}
294
295fn sort_index(index: &mut [MaterializedEntry]) {
296    fn sift(index: &mut [MaterializedEntry], mut root: usize, length: usize) {
297        loop {
298            let left = root * 2 + 1;
299            if left >= length {
300                return;
301            }
302            let larger = if left + 1 < length && index[left].id < index[left + 1].id {
303                left + 1
304            } else {
305                left
306            };
307            if index[root].id >= index[larger].id {
308                return;
309            }
310            index.swap(root, larger);
311            root = larger;
312        }
313    }
314    for root in (0..index.len() / 2).rev() {
315        sift(index, root, index.len());
316    }
317    for end in (1..index.len()).rev() {
318        index.swap(0, end);
319        sift(index, 0, end);
320    }
321}
git_zero_core/pack/materialize.rs

git_zero_core/pack/
materialize.rs
