grit_lib/pack_bitmap/
index.rs

1//! Parsed pack or MIDX reachability bitmap index.
2
3use std::collections::HashMap;
4use std::path::{Path, PathBuf};
5use std::sync::{Arc, Mutex};
6
7use crate::diagnostics::Warning;
8use crate::ewah_bitmap::{Bitmap, EwahView};
9use crate::midx::resolve_midx_bitmap_layer;
10use crate::objects::{ObjectId, ObjectKind};
11use crate::pack::PackIndex;
12use crate::pack_map::PackData;
13use crate::pack_rev::hashfile_checksum_valid;
14use crate::repo::Repository;
15
16use super::error::BitmapError;
17use super::order::BitmapOrder;
18use crate::pack::read_pack_index_cached;
19
20const BITMAP_MAGIC: &[u8; 4] = b"BITM";
21const BITMAP_VERSION: u16 = 1;
22const BITMAP_OPT_FULL_DAG: u16 = 0x1;
23const BITMAP_OPT_HASH_CACHE: u16 = 0x4;
24const BITMAP_OPT_LOOKUP_TABLE: u16 = 0x10;
25const BITMAP_OPT_PSEUDO_MERGES: u16 = 0x20;
26const LOOKUP_TRIPLET_WIDTH: usize = 16;
27const MAX_XOR_OFFSET: usize = 160;
28const XOR_ROW_NONE: u32 = 0xffff_ffff;
29
30/// Decoded reachability set for one commit (bits index pack/MIDX object positions).
31#[derive(Debug, Clone)]
32pub struct CommitReachabilityBitmap {
33    bits: Arc<Bitmap>,
34}
35
36impl CommitReachabilityBitmap {
37    /// Whether `position` is reachable from the indexed commit.
38    #[must_use]
39    pub fn contains(&self, position: u32) -> bool {
40        self.bits.get(position as usize)
41    }
42
43    /// Union this reachability set into `dest`.
44    pub(crate) fn or_into(&self, dest: &mut Bitmap) {
45        dest.or_assign(&self.bits);
46    }
47
48    /// Iterate set bit positions in ascending order.
49    pub fn positions(&self) -> impl Iterator<Item = u32> + '_ {
50        self.bits
51            .set_bits()
52            .map(|p| u32::try_from(p).unwrap_or(u32::MAX))
53    }
54}
55
56/// Borrowed type filter bitmap (commits, trees, blobs, or tags).
57#[derive(Debug, Clone, Copy)]
58pub struct TypeBitmap<'a> {
59    view: EwahView<'a>,
60}
61
62impl TypeBitmap<'_> {
63    /// Test whether `position` is marked in this type index.
64    ///
65    /// # Errors
66    ///
67    /// Returns [`BitmapError::InvalidEwah`] when the embedded EWAH cannot be read.
68    pub fn contains(&self, position: u32) -> Result<bool, BitmapError> {
69        let mut scratch = Bitmap::new();
70        self.view
71            .expand_into(&mut scratch)
72            .map_err(|_| BitmapError::InvalidEwah)?;
73        Ok(scratch.get(position as usize))
74    }
75
76    /// Decompress this type index into `dest`.
77    ///
78    /// # Errors
79    ///
80    /// Returns [`BitmapError::InvalidEwah`] when the embedded EWAH cannot be read.
81    pub(crate) fn expand_into_bitmap(&self, dest: &mut Bitmap) -> Result<(), BitmapError> {
82        self.view
83            .expand_into(dest)
84            .map_err(|_| BitmapError::InvalidEwah)
85    }
86}
87
88/// Memory-mapped pack or MIDX reachability bitmap (Git `BITM` v1).
89pub struct BitmapIndex {
90    map: Arc<PackData>,
91    entry_count: u32,
92    has_lookup_table: bool,
93    order: BitmapOrder,
94    type_commits_off: usize,
95    type_trees_off: usize,
96    type_blobs_off: usize,
97    type_tags_off: usize,
98    name_hashes: Option<(usize, usize)>,
99    lookup_table: Option<(usize, usize)>,
100    eager_entries: Option<Vec<EagerEntry>>,
101    decode_cache: Mutex<HashMap<ObjectId, Arc<Bitmap>>>,
102}
103
104#[derive(Debug, Clone)]
105struct EagerEntry {
106    oid: ObjectId,
107    ewah_offset: usize,
108    xor_prev_index: Option<usize>,
109}
110
111#[derive(Debug, Clone, Copy)]
112struct LookupTriplet {
113    commit_pos: u32,
114    offset: u64,
115    xor_row: u32,
116}
117
118impl BitmapIndex {
119    /// Open the active reachability bitmap for `repo`, preferring MIDX over pack bitmaps.
120    ///
121    /// Returns `Ok(None)` when no usable bitmap exists, the primary store is not
122    /// files-backed, or the on-disk file failed validation (a warning is emitted).
123    ///
124    /// # Errors
125    ///
126    /// Propagates unexpected I/O failures while discovering bitmap paths.
127    pub fn open(repo: &Repository) -> Result<Option<Arc<Self>>, BitmapError> {
128        if !repo.odb().uses_files_primary() {
129            return Ok(None);
130        }
131        if let Some(cached) = repo.caches().bitmap_index().get() {
132            return Ok(Some(cached));
133        }
134        let objects_dir = repo.odb().files_objects_dir().ok_or(BitmapError::Corrupt)?;
135        let loaded = try_open_bitmap(objects_dir, repo)?;
136        repo.caches().bitmap_index().set(loaded.clone());
137        Ok(loaded)
138    }
139
140    /// Pack index backing this bitmap when opened from a pack sidecar (not MIDX).
141    pub(crate) fn backing_pack_index(&self) -> Option<Arc<PackIndex>> {
142        match &self.order {
143            super::order::BitmapOrder::Pack { index, .. } => Some(Arc::clone(index)),
144            super::order::BitmapOrder::Midx { .. } => None,
145        }
146    }
147
148    /// Reachability bitmap for `commit`, when that commit is indexed.
149    #[must_use]
150    pub fn commit_bitmap(&self, commit: &ObjectId) -> Option<CommitReachabilityBitmap> {
151        let bits = self.decode_commit_bitmap(commit).ok()??;
152        Some(CommitReachabilityBitmap { bits })
153    }
154
155    /// Type filter bitmap for `kind` (commits, trees, blobs, or tags).
156    #[must_use]
157    pub fn type_bitmap(&self, kind: ObjectKind) -> TypeBitmap<'_> {
158        let off = match kind {
159            ObjectKind::Commit => self.type_commits_off,
160            ObjectKind::Tree => self.type_trees_off,
161            ObjectKind::Blob => self.type_blobs_off,
162            ObjectKind::Tag => self.type_tags_off,
163        };
164        TypeBitmap {
165            view: self.type_ewah_view(off),
166        }
167    }
168
169    /// Name-hash cache entry for bitmap position `position`, when present.
170    #[must_use]
171    pub fn name_hash(&self, position: u32) -> Option<u32> {
172        let (start, end) = self.name_hashes?;
173        let row = self.order.storage_row_for_bitmap_rank(position)?;
174        let base = start + usize::try_from(row).ok()?.checked_mul(4)?;
175        if base + 4 > end {
176            return None;
177        }
178        let slice = self.map.get(base..base + 4)?;
179        Some(u32::from_be_bytes(slice.try_into().ok()?))
180    }
181
182    /// Number of objects in the pack/MIDX namespace (length of type bitmaps).
183    #[must_use]
184    pub fn object_count(&self) -> u32 {
185        self.order.object_count()
186    }
187
188    /// Whether the on-disk index included a commit lookup table extension.
189    #[must_use]
190    pub fn has_lookup_table(&self) -> bool {
191        self.has_lookup_table
192    }
193
194    /// Number of reachability bitmap entries (selected commits) in this file.
195    #[must_use]
196    pub fn selected_commit_count(&self) -> u32 {
197        self.entry_count
198    }
199
200    /// Pack-index or MIDX storage row for bitmap bit `position`.
201    #[must_use]
202    pub(crate) fn pack_index_row_for_bitmap_position(&self, position: u32) -> Option<u32> {
203        self.order.storage_row_for_bitmap_rank(position)
204    }
205
206    /// Object id at bitmap bit `position`.
207    ///
208    /// # Errors
209    ///
210    /// Returns [`BitmapError::Corrupt`] when `position` is out of range.
211    pub fn oid_at(&self, position: u32) -> Result<ObjectId, BitmapError> {
212        self.order
213            .oid_at(position)
214            .map_err(|_| BitmapError::Corrupt)
215    }
216
217    /// Bitmap bit position for `oid`, when the object is in this index.
218    #[must_use]
219    pub fn position_of(&self, oid: &ObjectId) -> Option<u32> {
220        self.order.position_of(oid)
221    }
222
223    fn ewah_at(&self, offset: usize) -> Result<EwahView<'_>, BitmapError> {
224        let (view, _) = EwahView::parse(self.map.get(offset..).ok_or(BitmapError::Corrupt)?)
225            .map_err(|_| BitmapError::InvalidEwah)?;
226        Ok(view)
227    }
228
229    /// Type EWAH slices are validated when the index is opened.
230    #[allow(clippy::expect_used)]
231    fn type_ewah_view(&self, offset: usize) -> EwahView<'_> {
232        self.ewah_at(offset)
233            .expect("type bitmap EWAH validated at open")
234    }
235
236    fn decode_commit_bitmap(&self, commit: &ObjectId) -> Result<Option<Arc<Bitmap>>, BitmapError> {
237        if let Ok(guard) = self.decode_cache.lock() {
238            if let Some(bits) = guard.get(commit) {
239                return Ok(Some(Arc::clone(bits)));
240            }
241        }
242        let Some(bits) = self.decode_commit_bitmap_uncached(commit)? else {
243            return Ok(None);
244        };
245        let arc = Arc::new(bits);
246        if let Ok(mut guard) = self.decode_cache.lock() {
247            guard.insert(*commit, Arc::clone(&arc));
248        }
249        Ok(Some(arc))
250    }
251
252    fn decode_commit_bitmap_uncached(
253        &self,
254        commit: &ObjectId,
255    ) -> Result<Option<Bitmap>, BitmapError> {
256        if self.has_lookup_table {
257            return self.decode_via_lookup_table(commit);
258        }
259        let Some(entries) = self.eager_entries.as_ref() else {
260            return Ok(None);
261        };
262        if let Some(idx) = entries.iter().position(|e| e.oid == *commit) {
263            return self.decode_eager_index(idx);
264        }
265        Ok(None)
266    }
267
268    fn decode_eager_index(&self, idx: usize) -> Result<Option<Bitmap>, BitmapError> {
269        let entries = self.eager_entries.as_ref().ok_or(BitmapError::Corrupt)?;
270        let entry = entries.get(idx).ok_or(BitmapError::Corrupt)?;
271        let xor = if let Some(prev) = entry.xor_prev_index {
272            Some(self.decode_eager_index(prev)?.ok_or(BitmapError::Corrupt)?)
273        } else {
274            None
275        };
276        self.decode_ewah_payload_at(entry.ewah_offset, xor)
277            .map(Some)
278    }
279
280    fn decode_via_lookup_table(&self, commit: &ObjectId) -> Result<Option<Bitmap>, BitmapError> {
281        let commit_pos = match self.order.storage_row_for_oid(commit) {
282            Some(p) => p,
283            None => return Ok(None),
284        };
285        let (start, end) = self.lookup_table.ok_or(BitmapError::Corrupt)?;
286        let table = self.map.get(start..end).ok_or(BitmapError::Corrupt)?;
287        let Some(triplet) = lookup_triplet_by_commit_pos(table, self.entry_count, commit_pos)
288        else {
289            return Ok(None);
290        };
291        let mut xor_base: Option<Bitmap> = None;
292        if triplet.xor_row != XOR_ROW_NONE {
293            xor_base = Some(self.decode_xor_chain(triplet.xor_row)?);
294        }
295        self.decode_entry_at(triplet.offset as usize, xor_base)
296            .map(Some)
297    }
298
299    fn decode_xor_chain(&self, mut xor_row: u32) -> Result<Bitmap, BitmapError> {
300        let (start, end) = self.lookup_table.ok_or(BitmapError::Corrupt)?;
301        let table = self.map.get(start..end).ok_or(BitmapError::Corrupt)?;
302        let mut stack: Vec<LookupTriplet> = Vec::new();
303        let mut steps = 0u32;
304        while xor_row != XOR_ROW_NONE {
305            steps += 1;
306            if steps > self.entry_count {
307                return Err(BitmapError::Corrupt);
308            }
309            let triplet = lookup_triplet_by_row(table, xor_row).ok_or(BitmapError::Corrupt)?;
310            if let Ok(oid) = self.order.oid_at_storage_row(triplet.commit_pos) {
311                if let Ok(guard) = self.decode_cache.lock() {
312                    if let Some(existing) = guard.get(&oid) {
313                        return Ok((**existing).clone());
314                    }
315                }
316            }
317            stack.push(triplet);
318            xor_row = triplet.xor_row;
319        }
320        let mut acc: Option<Bitmap> = None;
321        while let Some(t) = stack.pop() {
322            acc = Some(self.decode_entry_at(t.offset as usize, acc)?);
323            if let Ok(oid) = self.order.oid_at_storage_row(t.commit_pos) {
324                if let Some(ref composed) = acc {
325                    if let Ok(mut guard) = self.decode_cache.lock() {
326                        guard.insert(oid, Arc::new(composed.clone()));
327                    }
328                }
329            }
330        }
331        acc.ok_or(BitmapError::Corrupt)
332    }
333
334    /// Decode from the start of a commit entry (lookup-table offsets).
335    fn decode_entry_at(
336        &self,
337        entry_start: usize,
338        xor_with: Option<Bitmap>,
339    ) -> Result<Bitmap, BitmapError> {
340        let data = self.map.as_ref();
341        if entry_start + 6 > data.len() {
342            return Err(BitmapError::Corrupt);
343        }
344        let ewah_start = entry_start + 6;
345        self.decode_ewah_payload_at(ewah_start, xor_with)
346    }
347
348    /// Decode an EWAH payload at `ewah_start` (after the 6-byte entry header).
349    fn decode_ewah_payload_at(
350        &self,
351        ewah_start: usize,
352        xor_with: Option<Bitmap>,
353    ) -> Result<Bitmap, BitmapError> {
354        let (view, _) = EwahView::parse(self.map.get(ewah_start..).ok_or(BitmapError::Corrupt)?)
355            .map_err(|_| BitmapError::InvalidEwah)?;
356        let mut out = xor_with.unwrap_or_default();
357        let mut xor_layer = Bitmap::new();
358        view.expand_into(&mut xor_layer)
359            .map_err(|_| BitmapError::InvalidEwah)?;
360        out.xor_assign(&xor_layer);
361        Ok(out)
362    }
363}
364
365fn try_open_bitmap(
366    objects_dir: &Path,
367    repo: &Repository,
368) -> Result<Option<Arc<BitmapIndex>>, BitmapError> {
369    let pack_dir = objects_dir.join("pack");
370    if let Some((bitmap_path, midx_path)) = resolve_midx_bitmap_layer(&pack_dir) {
371        match open_bitmap_file(
372            &bitmap_path,
373            objects_dir,
374            BitmapSource::Midx { midx_path },
375            repo,
376        ) {
377            Ok(idx) => return Ok(Some(Arc::new(idx))),
378            Err(err) => warn_bitmap(repo, &bitmap_path, &err),
379        }
380    }
381    let mut bitmapped = bitmapped_pack_indexes(&pack_dir)?;
382    bitmapped.sort_by_key(|(idx, _)| std::cmp::Reverse(idx.len()));
383    for (idx, bitmap_path) in bitmapped {
384        match open_bitmap_file(
385            &bitmap_path,
386            objects_dir,
387            BitmapSource::Pack { index: idx },
388            repo,
389        ) {
390            Ok(index) => return Ok(Some(Arc::new(index))),
391            Err(err) => warn_bitmap(repo, &bitmap_path, &err),
392        }
393    }
394    Ok(None)
395}
396
397/// Indexes of the packs in `pack_dir` that carry a `.bitmap` sidecar, with that path.
398///
399/// Packs without a bitmap are never opened, so a repository without bitmaps pays for
400/// one directory listing instead of reading every `.idx`. The indexes come from the
401/// shared pack-index cache, so the object store and the bitmap read one copy, and like
402/// Git's they are not re-hashed on open. Unreadable indexes and indexes whose `.pack`
403/// is missing are skipped.
404fn bitmapped_pack_indexes(pack_dir: &Path) -> Result<Vec<(Arc<PackIndex>, PathBuf)>, BitmapError> {
405    let entries = match std::fs::read_dir(pack_dir) {
406        Ok(entries) => entries,
407        Err(err) if err.kind() == std::io::ErrorKind::NotFound => return Ok(Vec::new()),
408        Err(err) => return Err(BitmapError::Io(err.to_string())),
409    };
410    let mut out = Vec::new();
411    for entry in entries {
412        let bitmap_path = entry.map_err(|e| BitmapError::Io(e.to_string()))?.path();
413        if bitmap_path.extension().and_then(|e| e.to_str()) != Some("bitmap") {
414            continue;
415        }
416        let Ok(idx) = read_pack_index_cached(&bitmap_path.with_extension("idx")) else {
417            continue;
418        };
419        if idx.pack_path.is_file() && bitmap_path.is_file() {
420            out.push((idx, bitmap_path));
421        }
422    }
423    Ok(out)
424}
425
426enum BitmapSource {
427    Pack { index: Arc<PackIndex> },
428    Midx { midx_path: PathBuf },
429}
430
431fn warn_bitmap(repo: &Repository, path: &Path, err: &BitmapError) {
432    repo.caches()
433        .diagnostics_handle()
434        .warn(Warning::PackBitmapIgnored {
435            path: path.to_path_buf(),
436            reason: err.to_string(),
437        });
438}
439
440fn open_bitmap_file(
441    path: &Path,
442    objects_dir: &Path,
443    source: BitmapSource,
444    repo: &Repository,
445) -> Result<BitmapIndex, BitmapError> {
446    let map = PackData::open(path).map_err(|e| BitmapError::Io(e.to_string()))?;
447    let data = map.as_ref();
448    if data.is_empty() {
449        return Err(BitmapError::TooSmall);
450    }
451    let hash_len = repo.odb().hash_algo().len();
452    if !hashfile_checksum_valid(data, hash_len) {
453        return Err(BitmapError::FileChecksumMismatch);
454    }
455    let header_size = 12 + hash_len;
456    if data.len() < header_size + hash_len {
457        return Err(BitmapError::TooSmall);
458    }
459    if &data[0..4] != BITMAP_MAGIC {
460        return Err(BitmapError::InvalidHeader);
461    }
462    let version = u16::from_be_bytes([data[4], data[5]]);
463    if version != BITMAP_VERSION {
464        return Err(BitmapError::InvalidHeader);
465    }
466    let flags = u16::from_be_bytes([data[6], data[7]]);
467    if flags & BITMAP_OPT_FULL_DAG == 0 {
468        return Err(BitmapError::MissingFullDag);
469    }
470    let entry_count = u32::from_be_bytes(data[8..12].try_into().map_err(|_| BitmapError::Corrupt)?);
471    let header_checksum = &data[12..12 + hash_len];
472    verify_source_checksum(&source, objects_dir, header_checksum, hash_len)?;
473
474    let mut pos = header_size;
475    let type_commits_off = pos;
476    pos += ewah_consumed(data, pos)?;
477    let type_trees_off = pos;
478    pos += ewah_consumed(data, pos)?;
479    let type_blobs_off = pos;
480    pos += ewah_consumed(data, pos)?;
481    let type_tags_off = pos;
482    pos += ewah_consumed(data, pos)?;
483
484    let order = match &source {
485        BitmapSource::Pack { index } => BitmapOrder::load_pack(objects_dir, Arc::clone(index))
486            .map_err(|_| BitmapError::Corrupt)?,
487        BitmapSource::Midx { midx_path } => BitmapOrder::load_midx_file(midx_path)
488            .map_err(|_| BitmapError::Corrupt)?
489            .ok_or(BitmapError::Corrupt)?,
490    };
491
492    let num_objects = order.object_count() as usize;
493    let hash_cache_len = num_objects.checked_mul(4).unwrap_or(0);
494    let mut tail_end = data.len() - hash_len;
495    let mut name_hashes = None;
496    let mut lookup_table = None;
497
498    if flags & BITMAP_OPT_HASH_CACHE != 0 {
499        if hash_cache_len > tail_end.saturating_sub(header_size) {
500            return Err(BitmapError::Corrupt);
501        }
502        tail_end -= hash_cache_len;
503        name_hashes = Some((tail_end, tail_end + hash_cache_len));
504    }
505    if flags & BITMAP_OPT_LOOKUP_TABLE != 0 {
506        let table_len = entry_count as usize * LOOKUP_TRIPLET_WIDTH;
507        if table_len > tail_end.saturating_sub(header_size) {
508            return Err(BitmapError::Corrupt);
509        }
510        tail_end -= table_len;
511        lookup_table = Some((tail_end, tail_end + table_len));
512    }
513    if flags & BITMAP_OPT_PSEUDO_MERGES != 0 {
514        tail_end = skip_pseudo_merge_extension(data, header_size, tail_end)?;
515    }
516
517    let entries_start = pos;
518    let eager_entries = if lookup_table.is_some() {
519        None
520    } else {
521        Some(load_eager_entries(
522            data,
523            entries_start,
524            entry_count,
525            &order,
526            tail_end,
527        )?)
528    };
529
530    Ok(BitmapIndex {
531        map,
532        entry_count,
533        has_lookup_table: lookup_table.is_some(),
534        order,
535        type_commits_off,
536        type_trees_off,
537        type_blobs_off,
538        type_tags_off,
539        name_hashes,
540        lookup_table,
541        eager_entries,
542        decode_cache: Mutex::new(HashMap::new()),
543    })
544}
545
546fn verify_source_checksum(
547    source: &BitmapSource,
548    _objects_dir: &Path,
549    header_checksum: &[u8],
550    hash_len: usize,
551) -> Result<(), BitmapError> {
552    let path = match source {
553        BitmapSource::Pack { index } => &index.pack_path,
554        BitmapSource::Midx { midx_path } => midx_path,
555    };
556    match read_file_trailer(path, hash_len).map_err(BitmapError::io)? {
557        Some(trailer) if trailer == header_checksum => Ok(()),
558        _ => Err(BitmapError::PackChecksumMismatch),
559    }
560}
561
562/// Read the last `len` bytes of `path` without loading the rest of the file.
563///
564/// Returns `None` when the file is shorter than `len`.
565fn read_file_trailer(path: &Path, len: usize) -> std::io::Result<Option<Vec<u8>>> {
566    use std::io::{Read, Seek, SeekFrom};
567
568    let mut file = std::fs::File::open(path)?;
569    let file_len = file.metadata()?.len();
570    let Ok(len_u64) = u64::try_from(len) else {
571        return Ok(None);
572    };
573    if file_len < len_u64 {
574        return Ok(None);
575    }
576    file.seek(SeekFrom::Start(file_len - len_u64))?;
577    let mut trailer = vec![0u8; len];
578    file.read_exact(&mut trailer)?;
579    Ok(Some(trailer))
580}
581
582fn skip_pseudo_merge_extension(
583    data: &[u8],
584    header_size: usize,
585    mut tail_end: usize,
586) -> Result<usize, BitmapError> {
587    if tail_end < header_size + 8 {
588        return Err(BitmapError::Corrupt);
589    }
590    let ext_size = u64::from_be_bytes(
591        data[tail_end - 8..tail_end]
592            .try_into()
593            .map_err(|_| BitmapError::Corrupt)?,
594    );
595    let ext_size = usize::try_from(ext_size).map_err(|_| BitmapError::Corrupt)?;
596    if ext_size > tail_end.saturating_sub(header_size) {
597        return Err(BitmapError::Corrupt);
598    }
599    tail_end -= ext_size;
600    Ok(tail_end)
601}
602
603fn ewah_consumed(data: &[u8], pos: usize) -> Result<usize, BitmapError> {
604    let (_, consumed) = EwahView::parse(data.get(pos..).ok_or(BitmapError::Corrupt)?)
605        .map_err(|_| BitmapError::InvalidEwah)?;
606    Ok(consumed)
607}
608
609fn load_eager_entries(
610    data: &[u8],
611    mut pos: usize,
612    entry_count: u32,
613    order: &BitmapOrder,
614    body_end: usize,
615) -> Result<Vec<EagerEntry>, BitmapError> {
616    let mut entries = Vec::with_capacity(entry_count as usize);
617    for i in 0..entry_count {
618        if pos + 6 > body_end {
619            return Err(BitmapError::Corrupt);
620        }
621        let commit_pos = u32::from_be_bytes(
622            data[pos..pos + 4]
623                .try_into()
624                .map_err(|_| BitmapError::Corrupt)?,
625        );
626        pos += 4;
627        let xor_offset = data[pos];
628        pos += 1;
629        let _flags = data[pos];
630        pos += 1;
631        let ewah_offset = pos;
632        pos += ewah_consumed(data, pos)?;
633        let oid = order
634            .oid_at_storage_row(commit_pos)
635            .map_err(|_| BitmapError::Corrupt)?;
636        let xor_prev_index = if xor_offset == 0 {
637            None
638        } else {
639            let x = xor_offset as usize;
640            if x > i as usize || x > MAX_XOR_OFFSET {
641                return Err(BitmapError::Corrupt);
642            }
643            Some(i as usize - x)
644        };
645        entries.push(EagerEntry {
646            oid,
647            ewah_offset,
648            xor_prev_index,
649        });
650    }
651    Ok(entries)
652}
653
654fn lookup_triplet_by_commit_pos(
655    table: &[u8],
656    entry_count: u32,
657    commit_pos: u32,
658) -> Option<LookupTriplet> {
659    let mut lo = 0usize;
660    let mut hi = entry_count as usize;
661    while lo < hi {
662        let mid = lo + (hi - lo) / 2;
663        let triplet = lookup_triplet_by_row(table, mid as u32)?;
664        match triplet.commit_pos.cmp(&commit_pos) {
665            std::cmp::Ordering::Less => lo = mid + 1,
666            std::cmp::Ordering::Greater => hi = mid,
667            std::cmp::Ordering::Equal => return Some(triplet),
668        }
669    }
670    None
671}
672
673fn lookup_triplet_by_row(table: &[u8], row: u32) -> Option<LookupTriplet> {
674    let base = row as usize * LOOKUP_TRIPLET_WIDTH;
675    let slice = table.get(base..base + LOOKUP_TRIPLET_WIDTH)?;
676    Some(LookupTriplet {
677        commit_pos: u32::from_be_bytes(slice[0..4].try_into().ok()?),
678        offset: u64::from_be_bytes(slice[4..12].try_into().ok()?),
679        xor_row: u32::from_be_bytes(slice[12..16].try_into().ok()?),
680    })
681}
682
683/// Repository-scoped cache slot for [`BitmapIndex::open`].
684#[derive(Default)]
685pub struct BitmapIndexCache {
686    inner: std::sync::OnceLock<Option<Arc<BitmapIndex>>>,
687}
688
689impl BitmapIndexCache {
690    pub(crate) fn get(&self) -> Option<Arc<BitmapIndex>> {
691        self.inner.get().and_then(|opt| opt.clone())
692    }
693
694    pub(crate) fn set(&self, value: Option<Arc<BitmapIndex>>) {
695        let _ = self.inner.set(value);
696    }
697}
698
699#[cfg(test)]
700mod tests {
701    use super::{bitmapped_pack_indexes, read_file_trailer, BitmapIndex};
702    use crate::environment::RepositoryOptions;
703    use crate::repo::Repository;
704    use grit_test_support::git;
705
706    #[test]
707    fn only_packs_with_a_bitmap_are_opened() {
708        let dir = tempfile::tempdir().unwrap();
709        let work = dir.path();
710        git(work, &["init", "-q", "-b", "main", "."]);
711        git(work, &["commit", "-q", "--allow-empty", "-m", "one"]);
712        let pack_dir = work.join(".git/objects/pack");
713        git(work, &["repack", "-q", "-ad"]);
714        assert!(bitmapped_pack_indexes(&pack_dir).unwrap().is_empty());
715        assert!(bitmapped_pack_indexes(&work.join("absent"))
716            .unwrap()
717            .is_empty());
718        let repo = Repository::open(&work.join(".git"), &RepositoryOptions::empty()).unwrap();
719        assert!(BitmapIndex::open(&repo).unwrap().is_none());
720
721        git(work, &["repack", "-q", "-adb"]);
722        git(work, &["commit", "-q", "--allow-empty", "-m", "two"]);
723        git(work, &["repack", "-q", "-d"]);
724        let packs = std::fs::read_dir(&pack_dir)
725            .unwrap()
726            .filter(|e| {
727                e.as_ref()
728                    .is_ok_and(|e| e.path().extension().is_some_and(|x| x == "pack"))
729            })
730            .count();
731        assert_eq!(packs, 2);
732        let bitmapped = bitmapped_pack_indexes(&pack_dir).unwrap();
733        assert_eq!(bitmapped.len(), 1);
734        let (idx, bitmap_path) = &bitmapped[0];
735        assert!(bitmap_path.is_file());
736        assert_eq!(idx.idx_path, bitmap_path.with_extension("idx"));
737        let repo = Repository::open(&work.join(".git"), &RepositoryOptions::empty()).unwrap();
738        assert!(BitmapIndex::open(&repo).unwrap().is_some());
739    }
740
741    #[test]
742    fn read_file_trailer_returns_last_bytes_only() -> std::io::Result<()> {
743        let dir = tempfile::tempdir()?;
744        let path = dir.path().join("data");
745        let mut body = vec![0u8; 64 * 1024];
746        body.extend_from_slice(b"0123456789abcdefghij");
747        std::fs::write(&path, &body)?;
748        assert_eq!(
749            read_file_trailer(&path, 20)?.as_deref(),
750            Some(&b"0123456789abcdefghij"[..])
751        );
752        assert_eq!(read_file_trailer(&path, 0)?.as_deref(), Some(&b""[..]));
753
754        let short = dir.path().join("short");
755        std::fs::write(&short, b"abc")?;
756        assert_eq!(read_file_trailer(&short, 20)?, None);
757        assert_eq!(read_file_trailer(&short, 3)?.as_deref(), Some(&b"abc"[..]));
758        Ok(())
759    }
760}
grit_lib/pack_bitmap/index.rs

grit_lib/pack_bitmap/
index.rs
