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_local_pack_indexes;
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 pack_indexes =
382        read_local_pack_indexes(objects_dir).map_err(|e| BitmapError::Io(e.to_string()))?;
383    pack_indexes.sort_by_key(|idx| std::cmp::Reverse(idx.len()));
384    for idx in pack_indexes {
385        let stem = idx
386            .idx_path
387            .file_stem()
388            .and_then(|s| s.to_str())
389            .unwrap_or("pack");
390        let bitmap_path = pack_dir.join(format!("{stem}.bitmap"));
391        if !bitmap_path.is_file() {
392            continue;
393        }
394        let index_arc = Arc::new(idx);
395        match open_bitmap_file(
396            &bitmap_path,
397            objects_dir,
398            BitmapSource::Pack {
399                index: Arc::clone(&index_arc),
400            },
401            repo,
402        ) {
403            Ok(index) => return Ok(Some(Arc::new(index))),
404            Err(err) => warn_bitmap(repo, &bitmap_path, &err),
405        }
406    }
407    Ok(None)
408}
409
410enum BitmapSource {
411    Pack { index: Arc<PackIndex> },
412    Midx { midx_path: PathBuf },
413}
414
415fn warn_bitmap(repo: &Repository, path: &Path, err: &BitmapError) {
416    repo.caches()
417        .diagnostics_handle()
418        .warn(Warning::PackBitmapIgnored {
419            path: path.to_path_buf(),
420            reason: err.to_string(),
421        });
422}
423
424fn open_bitmap_file(
425    path: &Path,
426    objects_dir: &Path,
427    source: BitmapSource,
428    repo: &Repository,
429) -> Result<BitmapIndex, BitmapError> {
430    let map = PackData::open(path).map_err(|e| BitmapError::Io(e.to_string()))?;
431    let data = map.as_ref();
432    if data.is_empty() {
433        return Err(BitmapError::TooSmall);
434    }
435    let hash_len = repo.odb().hash_algo().len();
436    if !hashfile_checksum_valid(data, hash_len) {
437        return Err(BitmapError::FileChecksumMismatch);
438    }
439    let header_size = 12 + hash_len;
440    if data.len() < header_size + hash_len {
441        return Err(BitmapError::TooSmall);
442    }
443    if &data[0..4] != BITMAP_MAGIC {
444        return Err(BitmapError::InvalidHeader);
445    }
446    let version = u16::from_be_bytes([data[4], data[5]]);
447    if version != BITMAP_VERSION {
448        return Err(BitmapError::InvalidHeader);
449    }
450    let flags = u16::from_be_bytes([data[6], data[7]]);
451    if flags & BITMAP_OPT_FULL_DAG == 0 {
452        return Err(BitmapError::MissingFullDag);
453    }
454    let entry_count = u32::from_be_bytes(data[8..12].try_into().map_err(|_| BitmapError::Corrupt)?);
455    let header_checksum = &data[12..12 + hash_len];
456    verify_source_checksum(&source, objects_dir, header_checksum, hash_len)?;
457
458    let mut pos = header_size;
459    let type_commits_off = pos;
460    pos += ewah_consumed(data, pos)?;
461    let type_trees_off = pos;
462    pos += ewah_consumed(data, pos)?;
463    let type_blobs_off = pos;
464    pos += ewah_consumed(data, pos)?;
465    let type_tags_off = pos;
466    pos += ewah_consumed(data, pos)?;
467
468    let order = match &source {
469        BitmapSource::Pack { index } => BitmapOrder::load_pack(objects_dir, Arc::clone(index))
470            .map_err(|_| BitmapError::Corrupt)?,
471        BitmapSource::Midx { midx_path } => BitmapOrder::load_midx_file(midx_path)
472            .map_err(|_| BitmapError::Corrupt)?
473            .ok_or(BitmapError::Corrupt)?,
474    };
475
476    let num_objects = order.object_count() as usize;
477    let hash_cache_len = num_objects.checked_mul(4).unwrap_or(0);
478    let mut tail_end = data.len() - hash_len;
479    let mut name_hashes = None;
480    let mut lookup_table = None;
481
482    if flags & BITMAP_OPT_HASH_CACHE != 0 {
483        if hash_cache_len > tail_end.saturating_sub(header_size) {
484            return Err(BitmapError::Corrupt);
485        }
486        tail_end -= hash_cache_len;
487        name_hashes = Some((tail_end, tail_end + hash_cache_len));
488    }
489    if flags & BITMAP_OPT_LOOKUP_TABLE != 0 {
490        let table_len = entry_count as usize * LOOKUP_TRIPLET_WIDTH;
491        if table_len > tail_end.saturating_sub(header_size) {
492            return Err(BitmapError::Corrupt);
493        }
494        tail_end -= table_len;
495        lookup_table = Some((tail_end, tail_end + table_len));
496    }
497    if flags & BITMAP_OPT_PSEUDO_MERGES != 0 {
498        tail_end = skip_pseudo_merge_extension(data, header_size, tail_end)?;
499    }
500
501    let entries_start = pos;
502    let eager_entries = if lookup_table.is_some() {
503        None
504    } else {
505        Some(load_eager_entries(
506            data,
507            entries_start,
508            entry_count,
509            &order,
510            tail_end,
511        )?)
512    };
513
514    Ok(BitmapIndex {
515        map,
516        entry_count,
517        has_lookup_table: lookup_table.is_some(),
518        order,
519        type_commits_off,
520        type_trees_off,
521        type_blobs_off,
522        type_tags_off,
523        name_hashes,
524        lookup_table,
525        eager_entries,
526        decode_cache: Mutex::new(HashMap::new()),
527    })
528}
529
530fn verify_source_checksum(
531    source: &BitmapSource,
532    _objects_dir: &Path,
533    header_checksum: &[u8],
534    hash_len: usize,
535) -> Result<(), BitmapError> {
536    let path = match source {
537        BitmapSource::Pack { index } => &index.pack_path,
538        BitmapSource::Midx { midx_path } => midx_path,
539    };
540    match read_file_trailer(path, hash_len).map_err(BitmapError::io)? {
541        Some(trailer) if trailer == header_checksum => Ok(()),
542        _ => Err(BitmapError::PackChecksumMismatch),
543    }
544}
545
546/// Read the last `len` bytes of `path` without loading the rest of the file.
547///
548/// Returns `None` when the file is shorter than `len`.
549fn read_file_trailer(path: &Path, len: usize) -> std::io::Result<Option<Vec<u8>>> {
550    use std::io::{Read, Seek, SeekFrom};
551
552    let mut file = std::fs::File::open(path)?;
553    let file_len = file.metadata()?.len();
554    let Ok(len_u64) = u64::try_from(len) else {
555        return Ok(None);
556    };
557    if file_len < len_u64 {
558        return Ok(None);
559    }
560    file.seek(SeekFrom::Start(file_len - len_u64))?;
561    let mut trailer = vec![0u8; len];
562    file.read_exact(&mut trailer)?;
563    Ok(Some(trailer))
564}
565
566fn skip_pseudo_merge_extension(
567    data: &[u8],
568    header_size: usize,
569    mut tail_end: usize,
570) -> Result<usize, BitmapError> {
571    if tail_end < header_size + 8 {
572        return Err(BitmapError::Corrupt);
573    }
574    let ext_size = u64::from_be_bytes(
575        data[tail_end - 8..tail_end]
576            .try_into()
577            .map_err(|_| BitmapError::Corrupt)?,
578    );
579    let ext_size = usize::try_from(ext_size).map_err(|_| BitmapError::Corrupt)?;
580    if ext_size > tail_end.saturating_sub(header_size) {
581        return Err(BitmapError::Corrupt);
582    }
583    tail_end -= ext_size;
584    Ok(tail_end)
585}
586
587fn ewah_consumed(data: &[u8], pos: usize) -> Result<usize, BitmapError> {
588    let (_, consumed) = EwahView::parse(data.get(pos..).ok_or(BitmapError::Corrupt)?)
589        .map_err(|_| BitmapError::InvalidEwah)?;
590    Ok(consumed)
591}
592
593fn load_eager_entries(
594    data: &[u8],
595    mut pos: usize,
596    entry_count: u32,
597    order: &BitmapOrder,
598    body_end: usize,
599) -> Result<Vec<EagerEntry>, BitmapError> {
600    let mut entries = Vec::with_capacity(entry_count as usize);
601    for i in 0..entry_count {
602        if pos + 6 > body_end {
603            return Err(BitmapError::Corrupt);
604        }
605        let commit_pos = u32::from_be_bytes(
606            data[pos..pos + 4]
607                .try_into()
608                .map_err(|_| BitmapError::Corrupt)?,
609        );
610        pos += 4;
611        let xor_offset = data[pos];
612        pos += 1;
613        let _flags = data[pos];
614        pos += 1;
615        let ewah_offset = pos;
616        pos += ewah_consumed(data, pos)?;
617        let oid = order
618            .oid_at_storage_row(commit_pos)
619            .map_err(|_| BitmapError::Corrupt)?;
620        let xor_prev_index = if xor_offset == 0 {
621            None
622        } else {
623            let x = xor_offset as usize;
624            if x > i as usize || x > MAX_XOR_OFFSET {
625                return Err(BitmapError::Corrupt);
626            }
627            Some(i as usize - x)
628        };
629        entries.push(EagerEntry {
630            oid,
631            ewah_offset,
632            xor_prev_index,
633        });
634    }
635    Ok(entries)
636}
637
638fn lookup_triplet_by_commit_pos(
639    table: &[u8],
640    entry_count: u32,
641    commit_pos: u32,
642) -> Option<LookupTriplet> {
643    let mut lo = 0usize;
644    let mut hi = entry_count as usize;
645    while lo < hi {
646        let mid = lo + (hi - lo) / 2;
647        let triplet = lookup_triplet_by_row(table, mid as u32)?;
648        match triplet.commit_pos.cmp(&commit_pos) {
649            std::cmp::Ordering::Less => lo = mid + 1,
650            std::cmp::Ordering::Greater => hi = mid,
651            std::cmp::Ordering::Equal => return Some(triplet),
652        }
653    }
654    None
655}
656
657fn lookup_triplet_by_row(table: &[u8], row: u32) -> Option<LookupTriplet> {
658    let base = row as usize * LOOKUP_TRIPLET_WIDTH;
659    let slice = table.get(base..base + LOOKUP_TRIPLET_WIDTH)?;
660    Some(LookupTriplet {
661        commit_pos: u32::from_be_bytes(slice[0..4].try_into().ok()?),
662        offset: u64::from_be_bytes(slice[4..12].try_into().ok()?),
663        xor_row: u32::from_be_bytes(slice[12..16].try_into().ok()?),
664    })
665}
666
667/// Repository-scoped cache slot for [`BitmapIndex::open`].
668#[derive(Default)]
669pub struct BitmapIndexCache {
670    inner: std::sync::OnceLock<Option<Arc<BitmapIndex>>>,
671}
672
673impl BitmapIndexCache {
674    pub(crate) fn get(&self) -> Option<Arc<BitmapIndex>> {
675        self.inner.get().and_then(|opt| opt.clone())
676    }
677
678    pub(crate) fn set(&self, value: Option<Arc<BitmapIndex>>) {
679        let _ = self.inner.set(value);
680    }
681}
682
683#[cfg(test)]
684mod tests {
685    use super::read_file_trailer;
686
687    #[test]
688    fn read_file_trailer_returns_last_bytes_only() -> std::io::Result<()> {
689        let dir = tempfile::tempdir()?;
690        let path = dir.path().join("data");
691        let mut body = vec![0u8; 64 * 1024];
692        body.extend_from_slice(b"0123456789abcdefghij");
693        std::fs::write(&path, &body)?;
694        assert_eq!(
695            read_file_trailer(&path, 20)?.as_deref(),
696            Some(&b"0123456789abcdefghij"[..])
697        );
698        assert_eq!(read_file_trailer(&path, 0)?.as_deref(), Some(&b""[..]));
699
700        let short = dir.path().join("short");
701        std::fs::write(&short, b"abc")?;
702        assert_eq!(read_file_trailer(&short, 20)?, None);
703        assert_eq!(read_file_trailer(&short, 3)?.as_deref(), Some(&b"abc"[..]));
704        Ok(())
705    }
706}
grit_lib/pack_bitmap/index.rs

grit_lib/pack_bitmap/
index.rs
