grit_lib/
bitmap_walk.rs

1//! Reachability queries using pack / MIDX commit bitmaps (Git `prepare_bitmap_walk` semantics).
2//!
3//! Computes want/have sets with optional object filters, falling back to callers when a query
4//! cannot be served from on-disk bitmaps alone.
5
6use std::collections::{HashSet, VecDeque};
7
8use crate::error::Error;
9use crate::ewah_bitmap::Bitmap;
10use crate::objects::{
11    empty_oid_set, oid_hash_set, parse_tag, ObjectId, ObjectKind, OidHashSet, TreeRefIter,
12};
13use crate::pack::read_object_info_from_packs;
14use crate::pack_bitmap::{BitmapError, BitmapIndex};
15use crate::repo::Repository;
16use crate::rev_list::{shallow_boundary_oids, FilterObjectKind, MissingAction, ObjectFilter};
17
18/// Query parameters for a bitmap reachability walk.
19#[derive(Debug, Clone, Copy)]
20pub struct ReachabilityQuery<'a> {
21    /// Tips whose reachable objects are included in the result (after subtracting [`Self::haves`]).
22    pub wants: &'a [ObjectId],
23    /// Tips whose reachable objects are excluded from the result.
24    pub haves: &'a [ObjectId],
25    /// Optional object filter (see [`ObjectFilter`]); unsupported specs yield [`BitmapWalkError::Unsupported`].
26    pub filter: Option<&'a ObjectFilter>,
27}
28
29/// Bitmap walk could not run (unsupported filter or shallow repo); use a non-bitmap walk instead.
30#[derive(Debug, Clone, Copy, PartialEq, Eq, thiserror::Error)]
31#[error("bitmap reachability walk is not supported for this repository or query")]
32pub struct BitmapWalkUnsupported;
33
34/// Errors during a bitmap reachability walk.
35#[derive(Debug, thiserror::Error)]
36pub enum BitmapWalkError {
37    /// Filter or repository shape requires a non-bitmap walk.
38    #[error(transparent)]
39    Unsupported(#[from] BitmapWalkUnsupported),
40    /// On-disk bitmap could not be read.
41    #[error(transparent)]
42    Bitmap(#[from] BitmapError),
43    /// Repository or object access failure.
44    #[error(transparent)]
45    Repository(#[from] Error),
46}
47
48/// Reachable objects from a [`ReachabilityQuery`]: in-index bits plus out-of-namespace oids.
49#[derive(Clone)]
50pub struct ReachableSet {
51    index: std::sync::Arc<BitmapIndex>,
52    bits: Bitmap,
53    extended: Vec<(ObjectId, ObjectKind)>,
54    extended_set: OidHashSet,
55}
56
57impl ReachableSet {
58    /// Total number of reachable objects (indexed and extended).
59    #[must_use]
60    pub fn count(&self) -> usize {
61        self.bits.count_ones() + self.extended.len()
62    }
63
64    /// Whether `oid` is in this set.
65    #[must_use]
66    pub fn contains(&self, oid: &ObjectId) -> bool {
67        if self.extended_set.contains(oid) {
68            return true;
69        }
70        self.index
71            .position_of(oid)
72            .is_some_and(|pos| self.bits.get(pos as usize))
73    }
74
75    /// Count reachable objects of `kind`.
76    ///
77    /// # Errors
78    ///
79    /// Propagates bitmap type-index decode failures.
80    pub fn count_by_kind(&self, kind: ObjectKind) -> std::result::Result<usize, BitmapWalkError> {
81        self.count_by_kind_popcount(kind)
82    }
83
84    /// Count reachable objects of `kind` via type-bitmap intersection popcount.
85    ///
86    /// # Errors
87    ///
88    /// Propagates bitmap type-index decode failures.
89    pub fn count_by_kind_popcount(
90        &self,
91        kind: ObjectKind,
92    ) -> std::result::Result<usize, BitmapWalkError> {
93        let mut type_bits = Bitmap::new();
94        self.index
95            .type_bitmap(kind)
96            .expand_into_bitmap(&mut type_bits)?;
97        type_bits.and_assign(&self.bits);
98        Ok(type_bits.count_ones() + self.extended.iter().filter(|(_, k)| *k == kind).count())
99    }
100
101    /// Iterate reachable oids of `kind` in ascending bitmap position order, then extended oids sorted.
102    pub fn iter_by_kind(&self, kind: ObjectKind) -> impl Iterator<Item = ObjectId> + '_ {
103        let positions = self.type_filtered_positions(kind);
104        positions
105            .into_iter()
106            .filter_map(|pos| self.index.oid_at(pos).ok())
107            .chain(
108                self.extended
109                    .iter()
110                    .filter_map(move |(oid, k)| (*k == kind).then_some(*oid)),
111            )
112    }
113
114    /// All reachable object ids (indexed namespace and extended) as a set.
115    #[must_use]
116    pub fn object_ids(&self) -> HashSet<ObjectId> {
117        let mut out = oid_hash_set();
118        for pos in self.bits.set_bits() {
119            if let Ok(oid) = self.index.oid_at(u32::try_from(pos).unwrap_or(u32::MAX)) {
120                out.insert(oid);
121            }
122        }
123        for (oid, _) in &self.extended {
124            out.insert(*oid);
125        }
126        out.into_iter().collect()
127    }
128
129    /// Bitmap positions the client still needs (indexed reachability minus haves).
130    #[must_use]
131    pub(crate) fn reuse_send_bits(&self) -> &Bitmap {
132        &self.bits
133    }
134
135    /// Bitmap index backing this set (pack or MIDX namespace).
136    #[must_use]
137    pub fn bitmap_index(&self) -> &std::sync::Arc<BitmapIndex> {
138        &self.index
139    }
140
141    /// Loose / out-of-namespace objects included in this set.
142    #[must_use]
143    pub fn extended_objects(&self) -> &[(ObjectId, ObjectKind)] {
144        &self.extended
145    }
146
147    /// All reachable oids grouped by Git's bitmap output order (commits, trees, blobs, tags).
148    pub fn iter_grouped_by_kind(&self) -> impl Iterator<Item = ObjectId> + '_ {
149        [
150            ObjectKind::Commit,
151            ObjectKind::Tree,
152            ObjectKind::Blob,
153            ObjectKind::Tag,
154        ]
155        .into_iter()
156        .flat_map(|kind| self.iter_by_kind(kind))
157    }
158
159    /// Reachable commit bitmap bit positions in ascending order (indexed namespace only).
160    pub(crate) fn reachable_commit_bitmap_positions(
161        &self,
162    ) -> std::result::Result<Vec<u32>, BitmapWalkError> {
163        let Ok(mut type_bits) = (|| {
164            let mut tb = Bitmap::new();
165            self.index
166                .type_bitmap(ObjectKind::Commit)
167                .expand_into_bitmap(&mut tb)?;
168            Ok::<_, BitmapError>(tb)
169        })() else {
170            return Ok(Vec::new());
171        };
172        type_bits.and_assign(&self.bits);
173        Ok(type_bits
174            .set_bits()
175            .map(|p| u32::try_from(p).unwrap_or(u32::MAX))
176            .collect())
177    }
178
179    fn type_filtered_positions(&self, kind: ObjectKind) -> Vec<u32> {
180        let Ok(mut type_bits) = (|| {
181            let mut tb = Bitmap::new();
182            self.index.type_bitmap(kind).expand_into_bitmap(&mut tb)?;
183            Ok::<_, BitmapError>(tb)
184        })() else {
185            return Vec::new();
186        };
187        type_bits.and_assign(&self.bits);
188        type_bits
189            .set_bits()
190            .map(|p| u32::try_from(p).unwrap_or(u32::MAX))
191            .collect()
192    }
193
194    fn subtract(&mut self, other: &Self) {
195        self.bits.and_not_assign(&other.bits);
196        self.extended.retain(|(oid, _)| !other.contains(oid));
197        self.extended_set
198            .retain(|oid| !other.extended_set.contains(oid));
199    }
200}
201
202/// Returns `true` when `filter` can be applied via type bitmaps (mirrors Git `can_filter_bitmap`).
203#[must_use]
204pub fn bitmap_filter_supported(filter: Option<&ObjectFilter>) -> bool {
205    match filter {
206        None => true,
207        Some(ObjectFilter::SparseOid(_)) => false,
208        Some(ObjectFilter::TreeDepth(depth)) if *depth > 0 => false,
209        Some(ObjectFilter::Combine(parts)) => {
210            parts.iter().all(|p| bitmap_filter_supported(Some(p)))
211        }
212        Some(ObjectFilter::BlobNone)
213        | Some(ObjectFilter::BlobLimit(_))
214        | Some(ObjectFilter::TreeDepth(0))
215        | Some(ObjectFilter::ObjectType(_)) => true,
216        Some(ObjectFilter::TreeDepth(_)) => false,
217    }
218}
219
220/// Commit, tag, and loose object tips after ref peeling (avoids re-reading objects in bitmap walks).
221pub(crate) struct PeeledTips {
222    pub commits: Vec<ObjectId>,
223    pub tags: Vec<ObjectId>,
224    pub extra_objects: Vec<ObjectId>,
225}
226
227fn peel_tips(
228    repo: &Repository,
229    tips: &[ObjectId],
230    missing: MissingAction,
231) -> std::result::Result<PeeledTips, BitmapWalkError> {
232    let mut out = PeeledTips {
233        commits: Vec::new(),
234        tags: Vec::new(),
235        extra_objects: Vec::new(),
236    };
237    for &tip in tips {
238        peel_one(repo, tip, missing, &mut out)?;
239    }
240    Ok(out)
241}
242
243fn peel_one(
244    repo: &Repository,
245    mut oid: ObjectId,
246    missing: MissingAction,
247    out: &mut PeeledTips,
248) -> std::result::Result<(), BitmapWalkError> {
249    loop {
250        let object = match repo.odb().read(&oid) {
251            Ok(obj) => obj,
252            Err(Error::ObjectNotFound(_)) if missing != MissingAction::Error => return Ok(()),
253            Err(err) => return Err(err.into()),
254        };
255        match object.kind {
256            ObjectKind::Commit => {
257                out.commits.push(oid);
258                return Ok(());
259            }
260            ObjectKind::Tag => {
261                out.tags.push(oid);
262                let tag = parse_tag(&object.data)?;
263                oid = tag.object;
264            }
265            ObjectKind::Tree | ObjectKind::Blob => {
266                out.extra_objects.push(oid);
267                return Ok(());
268            }
269        }
270    }
271}
272
273impl BitmapIndex {
274    /// Run `query` against this index and `repo`.
275    ///
276    /// # Errors
277    ///
278    /// Returns [`BitmapWalkError::Unsupported`] for shallow repositories or unsupported filters.
279    pub fn reachability(
280        self: &std::sync::Arc<Self>,
281        repo: &Repository,
282        query: ReachabilityQuery<'_>,
283        missing: MissingAction,
284    ) -> std::result::Result<ReachableSet, BitmapWalkError> {
285        if !shallow_boundary_oids(repo.git_dir()).is_empty()
286            || crate::shallow::shallow_file_path(repo.git_dir()).is_file()
287        {
288            return Err(BitmapWalkUnsupported.into());
289        }
290        if !bitmap_filter_supported(query.filter) {
291            return Err(BitmapWalkUnsupported.into());
292        }
293
294        let haves = find_objects_union(repo, self, query.haves, missing, false)?;
295        let mut wants = find_objects_union(repo, self, query.wants, missing, false)?;
296        wants.subtract(&haves);
297        apply_filter(repo, self, &mut wants, query.filter, query.wants)?;
298        Ok(wants)
299    }
300
301    /// Compare the on-disk commit bitmap for `commit` with a fresh non-bitmap walk (`rev-list --test-bitmap`).
302    ///
303    /// Returns `Ok(true)` when they match, `Ok(false)` when the commit has no stored bitmap or the
304    /// bitmap differs, and propagates read/decode errors.
305    ///
306    /// # Errors
307    ///
308    /// Propagates object read failures according to `missing`.
309    pub fn verify_commit(
310        self: &std::sync::Arc<Self>,
311        repo: &Repository,
312        commit: &ObjectId,
313        missing: MissingAction,
314    ) -> std::result::Result<bool, BitmapWalkError> {
315        let Some(stored) = self.commit_bitmap(commit) else {
316            return Ok(false);
317        };
318        let walked = find_objects_union(repo, self, &[*commit], missing, true)?;
319        let stored_set: HashSet<u32> = stored.positions().collect();
320        let walked_set: HashSet<u32> = walked
321            .bits
322            .set_bits()
323            .map(|p| u32::try_from(p).unwrap_or(u32::MAX))
324            .collect();
325        Ok(stored_set == walked_set && walked.extended.is_empty())
326    }
327
328    /// Like [`Self::reachability`], but `wants` are already split by peeled kind (no tip re-read).
329    pub(crate) fn reachability_with_peeled_wants(
330        self: &std::sync::Arc<Self>,
331        repo: &Repository,
332        wants: PeeledTips,
333        haves: &[ObjectId],
334        filter: Option<&ObjectFilter>,
335        missing: MissingAction,
336        filter_want_tips: &[ObjectId],
337    ) -> std::result::Result<ReachableSet, BitmapWalkError> {
338        if !shallow_boundary_oids(repo.git_dir()).is_empty()
339            || crate::shallow::shallow_file_path(repo.git_dir()).is_file()
340        {
341            return Err(BitmapWalkUnsupported.into());
342        }
343        if !bitmap_filter_supported(filter) {
344            return Err(BitmapWalkUnsupported.into());
345        }
346
347        let haves = find_objects_union(repo, self, haves, missing, false)?;
348        let mut want_set = find_objects_peeled(repo, self, wants, missing, false)?;
349        want_set.subtract(&haves);
350        apply_filter(repo, self, &mut want_set, filter, filter_want_tips)?;
351        Ok(want_set)
352    }
353}
354
355fn find_objects_union(
356    repo: &Repository,
357    index: &std::sync::Arc<BitmapIndex>,
358    tips: &[ObjectId],
359    missing: MissingAction,
360    ignore_stored_commit_bitmaps: bool,
361) -> std::result::Result<ReachableSet, BitmapWalkError> {
362    if tips.is_empty() {
363        return Ok(ReachableSet {
364            index: std::sync::Arc::clone(index),
365            bits: Bitmap::new(),
366            extended: Vec::new(),
367            extended_set: oid_hash_set(),
368        });
369    }
370    find_objects(repo, index, tips, missing, ignore_stored_commit_bitmaps)
371}
372
373fn find_objects(
374    repo: &Repository,
375    index: &std::sync::Arc<BitmapIndex>,
376    tips: &[ObjectId],
377    missing: MissingAction,
378    ignore_stored_commit_bitmaps: bool,
379) -> std::result::Result<ReachableSet, BitmapWalkError> {
380    let peeled = peel_tips(repo, tips, missing)?;
381    find_objects_peeled(repo, index, peeled, missing, ignore_stored_commit_bitmaps)
382}
383
384fn find_objects_peeled(
385    repo: &Repository,
386    index: &std::sync::Arc<BitmapIndex>,
387    peeled: PeeledTips,
388    missing: MissingAction,
389    ignore_stored_commit_bitmaps: bool,
390) -> std::result::Result<ReachableSet, BitmapWalkError> {
391    let mut bits = Bitmap::new();
392    let mut extended = Vec::new();
393    let mut extended_set = oid_hash_set();
394    let mut pending_commits = VecDeque::new();
395
396    for commit in peeled.commits {
397        if try_or_commit_bitmap(index, &mut bits, &commit, ignore_stored_commit_bitmaps)? {
398            continue;
399        }
400        if already_marked(index, &bits, &extended_set, &commit) {
401            continue;
402        }
403        pending_commits.push_back(commit);
404    }
405
406    for tag in peeled.tags {
407        mark_object(
408            repo,
409            index,
410            &mut bits,
411            &mut extended,
412            &mut extended_set,
413            tag,
414            ObjectKind::Tag,
415            missing,
416        )?;
417    }
418    for oid in peeled.extra_objects {
419        let kind = repo
420            .odb()
421            .read_info(&oid)
422            .map_err(BitmapWalkError::from)?
423            .kind;
424        mark_object(
425            repo,
426            index,
427            &mut bits,
428            &mut extended,
429            &mut extended_set,
430            oid,
431            kind,
432            missing,
433        )?;
434    }
435
436    let mut seen_commits = oid_hash_set();
437    while let Some(commit) = pending_commits.pop_front() {
438        if !seen_commits.insert(commit) {
439            continue;
440        }
441        if try_or_commit_bitmap(index, &mut bits, &commit, ignore_stored_commit_bitmaps)? {
442            if let Ok(parents) = repo.odb().read_commit(&commit).map(|c| c.parents) {
443                for parent in parents {
444                    seen_commits.insert(parent);
445                }
446            }
447            continue;
448        }
449        mark_index_or_extended(
450            index,
451            &mut bits,
452            &mut extended,
453            &mut extended_set,
454            commit,
455            ObjectKind::Commit,
456        );
457        let commit_data = match repo.odb().read_commit(&commit) {
458            Ok(c) => c,
459            Err(Error::ObjectNotFound(_)) => continue,
460            Err(err) => return Err(err.into()),
461        };
462        walk_tree(
463            repo,
464            index,
465            &mut bits,
466            &mut extended,
467            &mut extended_set,
468            commit_data.tree,
469            missing,
470        )?;
471        for parent in commit_data.parents {
472            if !seen_commits.contains(&parent) {
473                pending_commits.push_back(parent);
474            }
475        }
476    }
477
478    Ok(ReachableSet {
479        index: std::sync::Arc::clone(index),
480        bits,
481        extended,
482        extended_set,
483    })
484}
485
486fn try_or_commit_bitmap(
487    index: &BitmapIndex,
488    bits: &mut Bitmap,
489    commit: &ObjectId,
490    ignore_stored: bool,
491) -> std::result::Result<bool, BitmapWalkError> {
492    if ignore_stored {
493        return Ok(false);
494    }
495    let Some(bm) = index.commit_bitmap(commit) else {
496        return Ok(false);
497    };
498    bm.or_into(bits);
499    Ok(true)
500}
501
502fn already_marked(
503    index: &BitmapIndex,
504    bits: &Bitmap,
505    extended: &OidHashSet,
506    oid: &ObjectId,
507) -> bool {
508    if extended.contains(oid) {
509        return true;
510    }
511    index
512        .position_of(oid)
513        .is_some_and(|pos| bits.get(pos as usize))
514}
515
516fn mark_index_or_extended(
517    index: &BitmapIndex,
518    bits: &mut Bitmap,
519    extended: &mut Vec<(ObjectId, ObjectKind)>,
520    extended_set: &mut OidHashSet,
521    oid: ObjectId,
522    kind: ObjectKind,
523) {
524    if let Some(pos) = index.position_of(&oid) {
525        bits.set(pos as usize);
526    } else if extended_set.insert(oid) {
527        extended.push((oid, kind));
528    }
529}
530
531#[allow(clippy::too_many_arguments)]
532fn mark_object(
533    repo: &Repository,
534    index: &BitmapIndex,
535    bits: &mut Bitmap,
536    extended: &mut Vec<(ObjectId, ObjectKind)>,
537    extended_set: &mut OidHashSet,
538    oid: ObjectId,
539    kind: ObjectKind,
540    missing: MissingAction,
541) -> std::result::Result<(), BitmapWalkError> {
542    if already_marked(index, bits, extended_set, &oid) {
543        return Ok(());
544    }
545    match kind {
546        ObjectKind::Commit | ObjectKind::Tag | ObjectKind::Blob => {
547            mark_index_or_extended(index, bits, extended, extended_set, oid, kind);
548        }
549        ObjectKind::Tree => {
550            walk_tree(repo, index, bits, extended, extended_set, oid, missing)?;
551        }
552    }
553    Ok(())
554}
555
556fn walk_tree(
557    repo: &Repository,
558    index: &BitmapIndex,
559    bits: &mut Bitmap,
560    extended: &mut Vec<(ObjectId, ObjectKind)>,
561    extended_set: &mut OidHashSet,
562    tree: ObjectId,
563    missing: MissingAction,
564) -> std::result::Result<(), BitmapWalkError> {
565    if already_marked(index, bits, extended_set, &tree) {
566        return Ok(());
567    }
568    let object = match repo.odb().read(&tree) {
569        Ok(obj) => obj,
570        Err(Error::ObjectNotFound(_)) if missing != MissingAction::Error => return Ok(()),
571        Err(err) => return Err(err.into()),
572    };
573    if object.kind != ObjectKind::Tree {
574        return Ok(());
575    }
576    mark_index_or_extended(index, bits, extended, extended_set, tree, ObjectKind::Tree);
577    let oid_len = repo.odb().hash_algo().len();
578    for entry in TreeRefIter::with_oid_len(&object.data, oid_len) {
579        let entry = entry?;
580        // Submodule gitlinks name commits in another object store; do not walk them.
581        if entry.mode == 0o160000 {
582            continue;
583        }
584        if entry.mode == 0o040000 {
585            walk_tree(
586                repo,
587                index,
588                bits,
589                extended,
590                extended_set,
591                entry.oid,
592                missing,
593            )?;
594        } else {
595            mark_index_or_extended(
596                index,
597                bits,
598                extended,
599                extended_set,
600                entry.oid,
601                ObjectKind::Blob,
602            );
603        }
604    }
605    Ok(())
606}
607
608fn apply_filter(
609    repo: &Repository,
610    index: &BitmapIndex,
611    set: &mut ReachableSet,
612    filter: Option<&ObjectFilter>,
613    want_tips: &[ObjectId],
614) -> std::result::Result<(), BitmapWalkError> {
615    let Some(filter) = filter else {
616        return Ok(());
617    };
618    apply_filter_one(repo, index, set, filter, want_tips)?;
619    Ok(())
620}
621
622fn apply_filter_one(
623    repo: &Repository,
624    index: &BitmapIndex,
625    set: &mut ReachableSet,
626    filter: &ObjectFilter,
627    want_tips: &[ObjectId],
628) -> std::result::Result<(), BitmapWalkError> {
629    match filter {
630        ObjectFilter::Combine(parts) => {
631            for part in parts {
632                apply_filter_one(repo, index, set, part, want_tips)?;
633            }
634        }
635        ObjectFilter::BlobNone => {
636            let keep = explicit_filter_roots(repo, index, want_tips)?.blobs;
637            clear_type_except(index, &mut set.bits, ObjectKind::Blob, &keep);
638            set.extended
639                .retain(|(oid, kind)| *kind != ObjectKind::Blob || keep.contains(oid));
640            rebuild_extended_set(set);
641        }
642        ObjectFilter::BlobLimit(limit) => {
643            let tips = tip_blob_oids(repo, index, want_tips)?;
644            filter_blob_limit(repo, index, &mut set.bits, &tips, *limit)?;
645            set.extended.retain(|(oid, kind)| {
646                if tips.contains(oid) {
647                    return true;
648                }
649                *kind != ObjectKind::Blob || blob_under_limit(repo, oid, *limit)
650            });
651            rebuild_extended_set(set);
652        }
653        ObjectFilter::TreeDepth(0) => {
654            let roots = explicit_filter_roots(repo, index, want_tips)?;
655            clear_type_except(index, &mut set.bits, ObjectKind::Tree, &roots.trees);
656            clear_type_except(index, &mut set.bits, ObjectKind::Blob, &roots.blobs);
657            set.extended.retain(|(oid, kind)| {
658                matches!(kind, ObjectKind::Commit | ObjectKind::Tag)
659                    || roots.trees.contains(oid)
660                    || roots.blobs.contains(oid)
661            });
662            rebuild_extended_set(set);
663        }
664        ObjectFilter::ObjectType(kind) => {
665            keep_only_object_type(set, *kind);
666        }
667        ObjectFilter::SparseOid(_) | ObjectFilter::TreeDepth(_) => {
668            return Err(BitmapWalkUnsupported.into());
669        }
670    }
671    Ok(())
672}
673
674fn rebuild_extended_set(set: &mut ReachableSet) {
675    set.extended_set = set.extended.iter().map(|(oid, _)| *oid).collect();
676}
677
678fn blob_under_limit(repo: &Repository, oid: &ObjectId, limit: u64) -> bool {
679    match read_object_info_from_packs(repo.odb().objects_dir(), oid) {
680        Ok(info) => info.size < limit,
681        Err(_) => repo
682            .odb()
683            .read_info(oid)
684            .map(|info| info.size < limit)
685            .unwrap_or(false),
686    }
687}
688
689fn clear_type(index: &BitmapIndex, bits: &mut Bitmap, kind: ObjectKind) {
690    clear_type_except(index, bits, kind, empty_oid_set());
691}
692
693fn clear_type_except(index: &BitmapIndex, bits: &mut Bitmap, kind: ObjectKind, keep: &OidHashSet) {
694    if let Ok(type_bits) = expand_type(index, kind) {
695        for pos in type_bits.set_bits().collect::<Vec<_>>() {
696            let pos_u32 = u32::try_from(pos).unwrap_or(u32::MAX);
697            if let Ok(oid) = index.oid_at(pos_u32) {
698                if keep.contains(&oid) {
699                    continue;
700                }
701            }
702            bits.clear(pos);
703        }
704    }
705}
706
707struct ExplicitFilterRoots {
708    trees: OidHashSet,
709    blobs: OidHashSet,
710}
711
712fn explicit_filter_roots(
713    repo: &Repository,
714    index: &BitmapIndex,
715    tips: &[ObjectId],
716) -> std::result::Result<ExplicitFilterRoots, BitmapWalkError> {
717    let peeled = peel_tips(repo, tips, MissingAction::Error)?;
718    let mut trees = oid_hash_set();
719    let mut blobs = oid_hash_set();
720    for oid in peeled.extra_objects {
721        match repo
722            .odb()
723            .read_info(&oid)
724            .map_err(BitmapWalkError::from)?
725            .kind
726        {
727            ObjectKind::Tree => {
728                trees.insert(oid);
729            }
730            ObjectKind::Blob => {
731                blobs.insert(oid);
732            }
733            ObjectKind::Commit | ObjectKind::Tag => {}
734        }
735    }
736    for oid in tips {
737        if let Some(pos) = index.position_of(oid) {
738            if index
739                .type_bitmap(ObjectKind::Tree)
740                .contains(pos)
741                .unwrap_or(false)
742            {
743                trees.insert(*oid);
744            }
745            if index
746                .type_bitmap(ObjectKind::Blob)
747                .contains(pos)
748                .unwrap_or(false)
749            {
750                blobs.insert(*oid);
751            }
752        }
753    }
754    Ok(ExplicitFilterRoots { trees, blobs })
755}
756
757fn keep_only_object_type(set: &mut ReachableSet, kind: FilterObjectKind) {
758    let object_kind = match kind {
759        FilterObjectKind::Blob => ObjectKind::Blob,
760        FilterObjectKind::Tree => ObjectKind::Tree,
761        FilterObjectKind::Commit => ObjectKind::Commit,
762        FilterObjectKind::Tag => ObjectKind::Tag,
763    };
764    for k in [
765        ObjectKind::Commit,
766        ObjectKind::Tree,
767        ObjectKind::Blob,
768        ObjectKind::Tag,
769    ] {
770        if k != object_kind {
771            clear_type(&set.index, &mut set.bits, k);
772        }
773    }
774    set.extended.retain(|(_, k)| *k == object_kind);
775    rebuild_extended_set(set);
776}
777
778fn expand_type(
779    index: &BitmapIndex,
780    kind: ObjectKind,
781) -> std::result::Result<Bitmap, BitmapWalkError> {
782    let mut out = Bitmap::new();
783    index
784        .type_bitmap(kind)
785        .expand_into_bitmap(&mut out)
786        .map_err(BitmapWalkError::from)?;
787    Ok(out)
788}
789
790fn tip_blob_oids(
791    repo: &Repository,
792    index: &BitmapIndex,
793    tips: &[ObjectId],
794) -> std::result::Result<OidHashSet, BitmapWalkError> {
795    Ok(explicit_filter_roots(repo, index, tips)?.blobs)
796}
797
798fn filter_blob_limit(
799    repo: &Repository,
800    index: &BitmapIndex,
801    bits: &mut Bitmap,
802    tip_blobs: &OidHashSet,
803    limit: u64,
804) -> std::result::Result<(), BitmapWalkError> {
805    let mut blob_type = expand_type(index, ObjectKind::Blob)?;
806    blob_type.and_assign(bits);
807    let objects_dir = repo.odb().objects_dir();
808    for pos in blob_type.set_bits().collect::<Vec<_>>() {
809        let pos_u32 = u32::try_from(pos).unwrap_or(u32::MAX);
810        let Ok(oid) = index.oid_at(pos_u32) else {
811            continue;
812        };
813        if tip_blobs.contains(&oid) {
814            continue;
815        }
816        let size = read_object_info_from_packs(objects_dir, &oid)
817            .map_err(BitmapWalkError::from)?
818            .size;
819        if size >= limit {
820            bits.clear(pos);
821        }
822    }
823    Ok(())
824}
grit_lib/bitmap_walk.rs

grit_lib/
bitmap_walk.rs
