1use 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#[derive(Debug, Clone, Copy)]
22pub struct ReachabilityQuery<'a> {
23 pub wants: &'a [ObjectId],
25 pub haves: &'a [ObjectId],
27 pub filter: Option<&'a ObjectFilter>,
29}
30
31#[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#[derive(Debug, thiserror::Error)]
41#[non_exhaustive]
42pub enum BitmapWalkError {
43 #[error(transparent)]
45 Unsupported(#[from] BitmapWalkUnsupported),
46 #[error(transparent)]
48 Bitmap(#[from] BitmapError),
49}
50
51#[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 #[must_use]
63 pub fn count(&self) -> usize {
64 self.bits.count_ones() + self.extended.len()
65 }
66
67 #[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 pub fn count_by_kind(&self, kind: ObjectKind) -> crate::error::Result<usize> {
84 self.count_by_kind_popcount(kind)
85 }
86
87 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 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 #[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 #[must_use]
131 pub(crate) fn reuse_send_bits(&self) -> &Bitmap {
132 &self.bits
133 }
134
135 #[must_use]
137 pub fn bitmap_index(&self) -> &std::sync::Arc<BitmapIndex> {
138 &self.index
139 }
140
141 #[must_use]
143 pub fn extended_objects(&self) -> &[(ObjectId, ObjectKind)] {
144 &self.extended
145 }
146
147 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 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#[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
218pub(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 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 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 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 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
371fn 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
403fn 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 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
508struct 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
537fn 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 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}