Skip to main content

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 crate::error::ObjectError;
7use std::collections::{BinaryHeap, HashSet, VecDeque};
8
9use crate::error::Error;
10use crate::ewah_bitmap::Bitmap;
11use crate::objects::{
12    empty_oid_set, oid_hash_set, parse_tag, CommitRef, ObjectId, ObjectKind, OidHashSet,
13    TreeRefIter,
14};
15use crate::pack::read_object_info_from_packs;
16use crate::pack_bitmap::{BitmapError, BitmapIndex};
17use crate::repo::Repository;
18use crate::rev_list::{shallow_boundary_oids, FilterObjectKind, MissingAction, ObjectFilter};
19
20/// Query parameters for a bitmap reachability walk.
21#[derive(Debug, Clone, Copy)]
22pub struct ReachabilityQuery<'a> {
23    /// Tips whose reachable objects are included in the result (after subtracting [`Self::haves`]).
24    pub wants: &'a [ObjectId],
25    /// Tips whose reachable objects are excluded from the result.
26    pub haves: &'a [ObjectId],
27    /// Optional object filter (see [`ObjectFilter`]); unsupported specs yield [`BitmapWalkError::Unsupported`].
28    pub filter: Option<&'a ObjectFilter>,
29}
30
31/// Bitmap walk could not run (unsupported filter or shallow repo); use a non-bitmap walk instead.
32#[derive(Debug, Clone, Copy, PartialEq, Eq, thiserror::Error)]
33#[error("bitmap reachability walk is not supported for this repository or query")]
34pub struct BitmapWalkUnsupported;
35
36/// Bitmap-specific failures during a reachability walk; object and ref failures are reported in
37/// their own areas.
38///
39/// Surfaced on the umbrella as [`ObjectError::BitmapWalk`](crate::error::ObjectError::BitmapWalk).
40#[derive(Debug, thiserror::Error)]
41#[non_exhaustive]
42pub enum BitmapWalkError {
43    /// Filter or repository shape requires a non-bitmap walk.
44    #[error(transparent)]
45    Unsupported(#[from] BitmapWalkUnsupported),
46    /// On-disk bitmap could not be read.
47    #[error(transparent)]
48    Bitmap(#[from] BitmapError),
49}
50
51/// Reachable objects from a [`ReachabilityQuery`]: in-index bits plus out-of-namespace oids.
52#[derive(Clone)]
53pub struct ReachableSet {
54    index: std::sync::Arc<BitmapIndex>,
55    bits: Bitmap,
56    extended: Vec<(ObjectId, ObjectKind)>,
57    extended_set: OidHashSet,
58}
59
60impl ReachableSet {
61    /// Total number of reachable objects (indexed and extended).
62    #[must_use]
63    pub fn count(&self) -> usize {
64        self.bits.count_ones() + self.extended.len()
65    }
66
67    /// Whether `oid` is in this set.
68    #[must_use]
69    pub fn contains(&self, oid: &ObjectId) -> bool {
70        if self.extended_set.contains(oid) {
71            return true;
72        }
73        self.index
74            .position_of(oid)
75            .is_some_and(|pos| self.bits.get(pos as usize))
76    }
77
78    /// Count reachable objects of `kind`.
79    ///
80    /// # Errors
81    ///
82    /// Propagates bitmap type-index decode failures.
83    pub fn count_by_kind(&self, kind: ObjectKind) -> crate::error::Result<usize> {
84        self.count_by_kind_popcount(kind)
85    }
86
87    /// Count reachable objects of `kind` via type-bitmap intersection popcount.
88    ///
89    /// # Errors
90    ///
91    /// Propagates bitmap type-index decode failures.
92    pub fn count_by_kind_popcount(&self, kind: ObjectKind) -> crate::error::Result<usize> {
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(&self) -> crate::error::Result<Vec<u32>> {
161        let Ok(mut type_bits) = (|| {
162            let mut tb = Bitmap::new();
163            self.index
164                .type_bitmap(ObjectKind::Commit)
165                .expand_into_bitmap(&mut tb)?;
166            Ok::<_, BitmapError>(tb)
167        })() else {
168            return Ok(Vec::new());
169        };
170        type_bits.and_assign(&self.bits);
171        Ok(type_bits
172            .set_bits()
173            .map(|p| u32::try_from(p).unwrap_or(u32::MAX))
174            .collect())
175    }
176
177    fn type_filtered_positions(&self, kind: ObjectKind) -> Vec<u32> {
178        let Ok(mut type_bits) = (|| {
179            let mut tb = Bitmap::new();
180            self.index.type_bitmap(kind).expand_into_bitmap(&mut tb)?;
181            Ok::<_, BitmapError>(tb)
182        })() else {
183            return Vec::new();
184        };
185        type_bits.and_assign(&self.bits);
186        type_bits
187            .set_bits()
188            .map(|p| u32::try_from(p).unwrap_or(u32::MAX))
189            .collect()
190    }
191
192    fn subtract(&mut self, other: &Self) {
193        self.bits.and_not_assign(&other.bits);
194        self.extended.retain(|(oid, _)| !other.contains(oid));
195        self.extended_set
196            .retain(|oid| !other.extended_set.contains(oid));
197    }
198}
199
200/// Returns `true` when `filter` can be applied via type bitmaps (mirrors Git `can_filter_bitmap`).
201#[must_use]
202pub fn bitmap_filter_supported(filter: Option<&ObjectFilter>) -> bool {
203    match filter {
204        None => true,
205        Some(ObjectFilter::SparseOid(_)) => false,
206        Some(ObjectFilter::TreeDepth(depth)) if *depth > 0 => false,
207        Some(ObjectFilter::Combine(parts)) => {
208            parts.iter().all(|p| bitmap_filter_supported(Some(p)))
209        }
210        Some(ObjectFilter::BlobNone)
211        | Some(ObjectFilter::BlobLimit(_))
212        | Some(ObjectFilter::TreeDepth(0))
213        | Some(ObjectFilter::ObjectType(_)) => true,
214        Some(ObjectFilter::TreeDepth(_)) => false,
215    }
216}
217
218/// Commit, tag, and loose object tips after ref peeling (avoids re-reading objects in bitmap walks).
219pub(crate) struct PeeledTips {
220    pub commits: Vec<ObjectId>,
221    pub tags: Vec<ObjectId>,
222    pub extra_objects: Vec<ObjectId>,
223}
224
225fn peel_tips(
226    repo: &Repository,
227    tips: &[ObjectId],
228    missing: MissingAction,
229) -> crate::error::Result<PeeledTips> {
230    let mut out = PeeledTips {
231        commits: Vec::new(),
232        tags: Vec::new(),
233        extra_objects: Vec::new(),
234    };
235    for &tip in tips {
236        peel_one(repo, tip, missing, &mut out)?;
237    }
238    Ok(out)
239}
240
241fn peel_one(
242    repo: &Repository,
243    mut oid: ObjectId,
244    missing: MissingAction,
245    out: &mut PeeledTips,
246) -> crate::error::Result<()> {
247    loop {
248        let object = match repo.odb().read(&oid) {
249            Ok(obj) => obj,
250            Err(Error::Object(ObjectError::NotFound { .. })) if missing != MissingAction::Error => {
251                return Ok(())
252            }
253            Err(err) => return Err(err),
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    ) -> crate::error::Result<ReachableSet> {
285        self.reachability_and_haves(repo, query, missing, missing)
286            .map(|(wants, _)| wants)
287    }
288
289    /// Like [`Self::reachability`], also returning every object reachable from the haves
290    /// (unfiltered), which the query computes anyway.
291    ///
292    /// `want_missing` applies to the wants, `have_missing` to the haves.
293    pub(crate) fn reachability_and_haves(
294        self: &std::sync::Arc<Self>,
295        repo: &Repository,
296        query: ReachabilityQuery<'_>,
297        want_missing: MissingAction,
298        have_missing: MissingAction,
299    ) -> crate::error::Result<(ReachableSet, ReachableSet)> {
300        if !shallow_boundary_oids(repo.git_dir()).is_empty()
301            || crate::shallow::shallow_file_path(repo.git_dir()).is_file()
302        {
303            return Err(BitmapWalkUnsupported.into());
304        }
305        if !bitmap_filter_supported(query.filter) {
306            return Err(BitmapWalkUnsupported.into());
307        }
308
309        let haves = find_objects_union(repo, self, query.haves, have_missing, false, None)?;
310        let mut wants =
311            find_objects_union(repo, self, query.wants, want_missing, false, Some(&haves))?;
312        wants.subtract(&haves);
313        apply_filter(repo, self, &mut wants, query.filter, query.wants)?;
314        Ok((wants, haves))
315    }
316
317    /// Compare the on-disk commit bitmap for `commit` with a fresh non-bitmap walk (`rev-list --test-bitmap`).
318    ///
319    /// Returns `Ok(true)` when they match, `Ok(false)` when the commit has no stored bitmap or the
320    /// bitmap differs, and propagates read/decode errors.
321    ///
322    /// # Errors
323    ///
324    /// Propagates object read failures according to `missing`.
325    pub fn verify_commit(
326        self: &std::sync::Arc<Self>,
327        repo: &Repository,
328        commit: &ObjectId,
329        missing: MissingAction,
330    ) -> crate::error::Result<bool> {
331        let Some(stored) = self.commit_bitmap(commit) else {
332            return Ok(false);
333        };
334        let walked = find_objects_union(repo, self, &[*commit], missing, true, None)?;
335        let stored_set: HashSet<u32> = stored.positions().collect();
336        let walked_set: HashSet<u32> = walked
337            .bits
338            .set_bits()
339            .map(|p| u32::try_from(p).unwrap_or(u32::MAX))
340            .collect();
341        Ok(stored_set == walked_set && walked.extended.is_empty())
342    }
343
344    /// Like [`Self::reachability`], but `wants` are already split by peeled kind (no tip re-read).
345    pub(crate) fn reachability_with_peeled_wants(
346        self: &std::sync::Arc<Self>,
347        repo: &Repository,
348        wants: PeeledTips,
349        haves: &[ObjectId],
350        filter: Option<&ObjectFilter>,
351        missing: MissingAction,
352        filter_want_tips: &[ObjectId],
353    ) -> crate::error::Result<ReachableSet> {
354        if !shallow_boundary_oids(repo.git_dir()).is_empty()
355            || crate::shallow::shallow_file_path(repo.git_dir()).is_file()
356        {
357            return Err(BitmapWalkUnsupported.into());
358        }
359        if !bitmap_filter_supported(filter) {
360            return Err(BitmapWalkUnsupported.into());
361        }
362
363        let haves = find_objects_union(repo, self, haves, missing, false, None)?;
364        let mut want_set = find_objects_peeled(repo, self, wants, missing, false, Some(&haves))?;
365        want_set.subtract(&haves);
366        apply_filter(repo, self, &mut want_set, filter, filter_want_tips)?;
367        Ok(want_set)
368    }
369}
370
371/// Objects reachable from `tips`.
372///
373/// With `seed`, the walk starts from the objects already in it and stops wherever it
374/// reaches one of them, so the result is everything reachable from `tips` plus `seed`;
375/// a caller subtracting `seed` afterwards does not walk what it subtracts.
376fn find_objects_union(
377    repo: &Repository,
378    index: &std::sync::Arc<BitmapIndex>,
379    tips: &[ObjectId],
380    missing: MissingAction,
381    ignore_stored_commit_bitmaps: bool,
382    seed: Option<&ReachableSet>,
383) -> crate::error::Result<ReachableSet> {
384    if tips.is_empty() {
385        return Ok(ReachableSet {
386            index: std::sync::Arc::clone(index),
387            bits: Bitmap::new(),
388            extended: Vec::new(),
389            extended_set: oid_hash_set(),
390        });
391    }
392    let peeled = peel_tips(repo, tips, missing)?;
393    find_objects_peeled(
394        repo,
395        index,
396        peeled,
397        missing,
398        ignore_stored_commit_bitmaps,
399        seed,
400    )
401}
402
403/// [`find_objects_union`] for tips already split by kind.
404fn find_objects_peeled(
405    repo: &Repository,
406    index: &std::sync::Arc<BitmapIndex>,
407    peeled: PeeledTips,
408    missing: MissingAction,
409    ignore_stored_commit_bitmaps: bool,
410    seed: Option<&ReachableSet>,
411) -> crate::error::Result<ReachableSet> {
412    let (mut bits, mut extended, mut extended_set) = match seed {
413        Some(seed) => (
414            seed.bits.clone(),
415            seed.extended.clone(),
416            seed.extended_set.clone(),
417        ),
418        None => (Bitmap::new(), Vec::new(), oid_hash_set()),
419    };
420    let mut pending_commits = VecDeque::new();
421
422    for commit in peeled.commits {
423        if try_or_commit_bitmap(index, &mut bits, &commit, ignore_stored_commit_bitmaps)? {
424            continue;
425        }
426        if already_marked(index, &bits, &extended_set, &commit) {
427            continue;
428        }
429        pending_commits.push_back(commit);
430    }
431
432    for tag in peeled.tags {
433        mark_object(
434            repo,
435            index,
436            &mut bits,
437            &mut extended,
438            &mut extended_set,
439            tag,
440            ObjectKind::Tag,
441            missing,
442        )?;
443    }
444    for oid in peeled.extra_objects {
445        let kind = repo.odb().read_info(&oid)?.kind;
446        mark_object(
447            repo,
448            index,
449            &mut bits,
450            &mut extended,
451            &mut extended_set,
452            oid,
453            kind,
454            missing,
455        )?;
456    }
457
458    // Commits without a stored bitmap are walked newest first, so the bitmaps of the
459    // recent commits that cover most of the history are OR'ed in before the walk
460    // reaches what they cover, and a commit already covered ends its line of the walk.
461    let mut seen_commits = oid_hash_set();
462    let mut queue = BinaryHeap::new();
463    for commit in pending_commits {
464        if seen_commits.insert(commit) {
465            queue_walk_commit(repo, &mut queue, commit)?;
466        }
467    }
468    while let Some(commit) = queue.pop() {
469        if already_marked(index, &bits, &extended_set, &commit.oid) {
470            continue;
471        }
472        mark_index_or_extended(
473            index,
474            &mut bits,
475            &mut extended,
476            &mut extended_set,
477            commit.oid,
478            ObjectKind::Commit,
479        );
480        walk_tree(
481            repo,
482            index,
483            &mut bits,
484            &mut extended,
485            &mut extended_set,
486            commit.tree,
487            missing,
488        )?;
489        for parent in commit.parents {
490            if !seen_commits.insert(parent)
491                || already_marked(index, &bits, &extended_set, &parent)
492                || try_or_commit_bitmap(index, &mut bits, &parent, ignore_stored_commit_bitmaps)?
493            {
494                continue;
495            }
496            queue_walk_commit(repo, &mut queue, parent)?;
497        }
498    }
499
500    Ok(ReachableSet {
501        index: std::sync::Arc::clone(index),
502        bits,
503        extended,
504        extended_set,
505    })
506}
507
508/// A commit waiting in the bitmap fallback walk, ordered newest first.
509struct WalkCommit {
510    time: i64,
511    seq: std::cmp::Reverse<u64>,
512    oid: ObjectId,
513    tree: ObjectId,
514    parents: Vec<ObjectId>,
515}
516
517impl PartialEq for WalkCommit {
518    fn eq(&self, other: &Self) -> bool {
519        (self.time, self.seq) == (other.time, other.seq)
520    }
521}
522
523impl Eq for WalkCommit {}
524
525impl PartialOrd for WalkCommit {
526    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
527        Some(self.cmp(other))
528    }
529}
530
531impl Ord for WalkCommit {
532    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
533        (self.time, self.seq).cmp(&(other.time, other.seq))
534    }
535}
536
537/// Read `oid` and queue it for the fallback walk; a missing commit is skipped.
538fn queue_walk_commit(
539    repo: &Repository,
540    queue: &mut BinaryHeap<WalkCommit>,
541    oid: ObjectId,
542) -> crate::error::Result<()> {
543    let object = match repo.odb().read(&oid) {
544        Ok(obj) => obj,
545        Err(Error::Object(ObjectError::NotFound { .. })) => return Ok(()),
546        Err(err) => return Err(err),
547    };
548    if object.kind != ObjectKind::Commit {
549        return Ok(());
550    }
551    let commit = CommitRef::parse(&object.data)?;
552    queue.push(WalkCommit {
553        time: commit.committer_unix_seconds_for_ordering(),
554        seq: std::cmp::Reverse(queue.len() as u64),
555        oid,
556        tree: commit.tree(),
557        parents: commit.parents().to_vec(),
558    });
559    Ok(())
560}
561
562fn try_or_commit_bitmap(
563    index: &BitmapIndex,
564    bits: &mut Bitmap,
565    commit: &ObjectId,
566    ignore_stored: bool,
567) -> crate::error::Result<bool> {
568    if ignore_stored {
569        return Ok(false);
570    }
571    let Some(bm) = index.commit_bitmap(commit) else {
572        return Ok(false);
573    };
574    bm.or_into(bits);
575    Ok(true)
576}
577
578fn already_marked(
579    index: &BitmapIndex,
580    bits: &Bitmap,
581    extended: &OidHashSet,
582    oid: &ObjectId,
583) -> bool {
584    if extended.contains(oid) {
585        return true;
586    }
587    index
588        .position_of(oid)
589        .is_some_and(|pos| bits.get(pos as usize))
590}
591
592fn mark_index_or_extended(
593    index: &BitmapIndex,
594    bits: &mut Bitmap,
595    extended: &mut Vec<(ObjectId, ObjectKind)>,
596    extended_set: &mut OidHashSet,
597    oid: ObjectId,
598    kind: ObjectKind,
599) {
600    if let Some(pos) = index.position_of(&oid) {
601        bits.set(pos as usize);
602    } else if extended_set.insert(oid) {
603        extended.push((oid, kind));
604    }
605}
606
607#[allow(clippy::too_many_arguments)]
608fn mark_object(
609    repo: &Repository,
610    index: &BitmapIndex,
611    bits: &mut Bitmap,
612    extended: &mut Vec<(ObjectId, ObjectKind)>,
613    extended_set: &mut OidHashSet,
614    oid: ObjectId,
615    kind: ObjectKind,
616    missing: MissingAction,
617) -> crate::error::Result<()> {
618    if already_marked(index, bits, extended_set, &oid) {
619        return Ok(());
620    }
621    match kind {
622        ObjectKind::Commit | ObjectKind::Tag | ObjectKind::Blob => {
623            mark_index_or_extended(index, bits, extended, extended_set, oid, kind);
624        }
625        ObjectKind::Tree => {
626            walk_tree(repo, index, bits, extended, extended_set, oid, missing)?;
627        }
628    }
629    Ok(())
630}
631
632fn walk_tree(
633    repo: &Repository,
634    index: &BitmapIndex,
635    bits: &mut Bitmap,
636    extended: &mut Vec<(ObjectId, ObjectKind)>,
637    extended_set: &mut OidHashSet,
638    tree: ObjectId,
639    missing: MissingAction,
640) -> crate::error::Result<()> {
641    if already_marked(index, bits, extended_set, &tree) {
642        return Ok(());
643    }
644    let object = match repo.odb().read(&tree) {
645        Ok(obj) => obj,
646        Err(Error::Object(ObjectError::NotFound { .. })) if missing != MissingAction::Error => {
647            return Ok(())
648        }
649        Err(err) => return Err(err),
650    };
651    if object.kind != ObjectKind::Tree {
652        return Ok(());
653    }
654    mark_index_or_extended(index, bits, extended, extended_set, tree, ObjectKind::Tree);
655    let oid_len = repo.odb().hash_algo().len();
656    for entry in TreeRefIter::with_oid_len(&object.data, oid_len) {
657        let entry = entry?;
658        // Submodule gitlinks name commits in another object store; do not walk them.
659        if entry.mode == 0o160000 {
660            continue;
661        }
662        if entry.mode == 0o040000 {
663            walk_tree(
664                repo,
665                index,
666                bits,
667                extended,
668                extended_set,
669                entry.oid,
670                missing,
671            )?;
672        } else {
673            mark_index_or_extended(
674                index,
675                bits,
676                extended,
677                extended_set,
678                entry.oid,
679                ObjectKind::Blob,
680            );
681        }
682    }
683    Ok(())
684}
685
686fn apply_filter(
687    repo: &Repository,
688    index: &BitmapIndex,
689    set: &mut ReachableSet,
690    filter: Option<&ObjectFilter>,
691    want_tips: &[ObjectId],
692) -> crate::error::Result<()> {
693    let Some(filter) = filter else {
694        return Ok(());
695    };
696    apply_filter_one(repo, index, set, filter, want_tips)?;
697    Ok(())
698}
699
700fn apply_filter_one(
701    repo: &Repository,
702    index: &BitmapIndex,
703    set: &mut ReachableSet,
704    filter: &ObjectFilter,
705    want_tips: &[ObjectId],
706) -> crate::error::Result<()> {
707    match filter {
708        ObjectFilter::Combine(parts) => {
709            for part in parts {
710                apply_filter_one(repo, index, set, part, want_tips)?;
711            }
712        }
713        ObjectFilter::BlobNone => {
714            let keep = explicit_filter_roots(repo, index, want_tips)?.blobs;
715            clear_type_except(index, &mut set.bits, ObjectKind::Blob, &keep);
716            set.extended
717                .retain(|(oid, kind)| *kind != ObjectKind::Blob || keep.contains(oid));
718            rebuild_extended_set(set);
719        }
720        ObjectFilter::BlobLimit(limit) => {
721            let tips = tip_blob_oids(repo, index, want_tips)?;
722            filter_blob_limit(repo, index, &mut set.bits, &tips, *limit)?;
723            set.extended.retain(|(oid, kind)| {
724                if tips.contains(oid) {
725                    return true;
726                }
727                *kind != ObjectKind::Blob || blob_under_limit(repo, oid, *limit)
728            });
729            rebuild_extended_set(set);
730        }
731        ObjectFilter::TreeDepth(0) => {
732            let roots = explicit_filter_roots(repo, index, want_tips)?;
733            clear_type_except(index, &mut set.bits, ObjectKind::Tree, &roots.trees);
734            clear_type_except(index, &mut set.bits, ObjectKind::Blob, &roots.blobs);
735            set.extended.retain(|(oid, kind)| {
736                matches!(kind, ObjectKind::Commit | ObjectKind::Tag)
737                    || roots.trees.contains(oid)
738                    || roots.blobs.contains(oid)
739            });
740            rebuild_extended_set(set);
741        }
742        ObjectFilter::ObjectType(kind) => {
743            keep_only_object_type(set, *kind);
744        }
745        ObjectFilter::SparseOid(_) | ObjectFilter::TreeDepth(_) => {
746            return Err(BitmapWalkUnsupported.into());
747        }
748    }
749    Ok(())
750}
751
752fn rebuild_extended_set(set: &mut ReachableSet) {
753    set.extended_set = set.extended.iter().map(|(oid, _)| *oid).collect();
754}
755
756fn blob_under_limit(repo: &Repository, oid: &ObjectId, limit: u64) -> bool {
757    match read_object_info_from_packs(repo.odb().objects_dir(), oid) {
758        Ok(info) => info.size < limit,
759        Err(_) => repo
760            .odb()
761            .read_info(oid)
762            .map(|info| info.size < limit)
763            .unwrap_or(false),
764    }
765}
766
767fn clear_type(index: &BitmapIndex, bits: &mut Bitmap, kind: ObjectKind) {
768    clear_type_except(index, bits, kind, empty_oid_set());
769}
770
771fn clear_type_except(index: &BitmapIndex, bits: &mut Bitmap, kind: ObjectKind, keep: &OidHashSet) {
772    if let Ok(type_bits) = expand_type(index, kind) {
773        for pos in type_bits.set_bits().collect::<Vec<_>>() {
774            let pos_u32 = u32::try_from(pos).unwrap_or(u32::MAX);
775            if let Ok(oid) = index.oid_at(pos_u32) {
776                if keep.contains(&oid) {
777                    continue;
778                }
779            }
780            bits.clear(pos);
781        }
782    }
783}
784
785struct ExplicitFilterRoots {
786    trees: OidHashSet,
787    blobs: OidHashSet,
788}
789
790fn explicit_filter_roots(
791    repo: &Repository,
792    index: &BitmapIndex,
793    tips: &[ObjectId],
794) -> crate::error::Result<ExplicitFilterRoots> {
795    let peeled = peel_tips(repo, tips, MissingAction::Error)?;
796    let mut trees = oid_hash_set();
797    let mut blobs = oid_hash_set();
798    for oid in peeled.extra_objects {
799        match repo.odb().read_info(&oid)?.kind {
800            ObjectKind::Tree => {
801                trees.insert(oid);
802            }
803            ObjectKind::Blob => {
804                blobs.insert(oid);
805            }
806            ObjectKind::Commit | ObjectKind::Tag => {}
807        }
808    }
809    for oid in tips {
810        if let Some(pos) = index.position_of(oid) {
811            if index
812                .type_bitmap(ObjectKind::Tree)
813                .contains(pos)
814                .unwrap_or(false)
815            {
816                trees.insert(*oid);
817            }
818            if index
819                .type_bitmap(ObjectKind::Blob)
820                .contains(pos)
821                .unwrap_or(false)
822            {
823                blobs.insert(*oid);
824            }
825        }
826    }
827    Ok(ExplicitFilterRoots { trees, blobs })
828}
829
830fn keep_only_object_type(set: &mut ReachableSet, kind: FilterObjectKind) {
831    let object_kind = match kind {
832        FilterObjectKind::Blob => ObjectKind::Blob,
833        FilterObjectKind::Tree => ObjectKind::Tree,
834        FilterObjectKind::Commit => ObjectKind::Commit,
835        FilterObjectKind::Tag => ObjectKind::Tag,
836    };
837    for k in [
838        ObjectKind::Commit,
839        ObjectKind::Tree,
840        ObjectKind::Blob,
841        ObjectKind::Tag,
842    ] {
843        if k != object_kind {
844            clear_type(&set.index, &mut set.bits, k);
845        }
846    }
847    set.extended.retain(|(_, k)| *k == object_kind);
848    rebuild_extended_set(set);
849}
850
851fn expand_type(index: &BitmapIndex, kind: ObjectKind) -> crate::error::Result<Bitmap> {
852    let mut out = Bitmap::new();
853    index.type_bitmap(kind).expand_into_bitmap(&mut out)?;
854    Ok(out)
855}
856
857fn tip_blob_oids(
858    repo: &Repository,
859    index: &BitmapIndex,
860    tips: &[ObjectId],
861) -> crate::error::Result<OidHashSet> {
862    Ok(explicit_filter_roots(repo, index, tips)?.blobs)
863}
864
865fn filter_blob_limit(
866    repo: &Repository,
867    index: &BitmapIndex,
868    bits: &mut Bitmap,
869    tip_blobs: &OidHashSet,
870    limit: u64,
871) -> crate::error::Result<()> {
872    let mut blob_type = expand_type(index, ObjectKind::Blob)?;
873    blob_type.and_assign(bits);
874    let objects_dir = repo.odb().objects_dir();
875    for pos in blob_type.set_bits().collect::<Vec<_>>() {
876        let pos_u32 = u32::try_from(pos).unwrap_or(u32::MAX);
877        let Ok(oid) = index.oid_at(pos_u32) else {
878            continue;
879        };
880        if tip_blobs.contains(&oid) {
881            continue;
882        }
883        let size = read_object_info_from_packs(objects_dir, &oid)?.size;
884        if size >= limit {
885            bits.clear(pos);
886        }
887    }
888    Ok(())
889}