alice.pds.demo.boltless.dev
This repository has no description
did:plc:3fwecdnvtcscjnrx2p4n7a…
1use std::collections::HashSet;
2use std::path::Path;
3
4use knot_types::Oid;
5
6use super::revindex::{Order, OrderTable};
7use super::{BitPosition, BitmapEntryOffset, IndexPosition};
8use crate::error::GitError;
9use crate::objects::{Haves, Wants};
10use crate::repo::Repo;
11
12const OPT_FULL_DAG: u16 = 0x1;
13const OPT_LOOKUP_TABLE: u16 = 0x10;
14
15const CAT_COMMIT: u8 = 0;
16const CAT_TREE: u8 = 1;
17const CAT_BLOB: u8 = 2;
18const CAT_TAG: u8 = 3;
19
20pub(super) struct TypeBits {
21 commits: Vec<bool>,
22 trees: Vec<bool>,
23 blobs: Vec<bool>,
24 tags: Vec<bool>,
25}
26
27pub(super) struct Selected {
28 commit_pos: IndexPosition,
29 bits: Vec<bool>,
30}
31
32pub(crate) fn write(repo: &Repo, pack_idx: &Path) -> Result<bool, GitError> {
33 let kind = repo.object_format().kind();
34 let index = gix_pack::index::File::at(pack_idx, kind)
35 .map_err(|error| GitError::Backend(format!("open pack index: {error}")))?;
36 let rev = OrderTable::from_index(&index);
37 if rev.len() == 0 {
38 return Ok(false);
39 }
40
41 let _boost = knot_resource::saturate();
42 let types = type_index_bits(repo, &rev)?;
43 let selected = selected_entries(repo, &rev)?;
44 if selected.is_empty() {
45 return Ok(false);
46 }
47
48 let pack_path = pack_idx.with_extension("pack");
49 let checksum = gix_pack::data::File::at(&pack_path, kind)
50 .map_err(|error| GitError::Backend(format!("open pack data: {error}")))?
51 .checksum();
52
53 let bytes = assemble(kind, &checksum, &types, &selected)?;
54 install(&pack_idx.with_extension("bitmap"), &bytes)?;
55 Ok(true)
56}
57
58pub(super) fn type_index_bits<R: Order + Sync>(repo: &Repo, rev: &R) -> Result<TypeBits, GitError> {
59 let categories = categories_in_bit_order(repo, rev)?;
60 let select = |target: u8| {
61 categories
62 .iter()
63 .map(|value| *value == target)
64 .collect::<Vec<bool>>()
65 };
66 Ok(TypeBits {
67 commits: select(CAT_COMMIT),
68 trees: select(CAT_TREE),
69 blobs: select(CAT_BLOB),
70 tags: select(CAT_TAG),
71 })
72}
73
74fn categories_in_bit_order<R: Order + Sync>(repo: &Repo, rev: &R) -> Result<Vec<u8>, GitError> {
75 let path = repo.path().to_owned();
76 knot_resource::map_spans(rev.len(), |start, end| {
77 let local = Repo::open(&path)?;
78 (start..end)
79 .map(|bit| object_category(&local, rev.oid_at_bit(BitPosition(bit as u32))))
80 .collect::<Result<Vec<u8>, GitError>>()
81 })
82}
83
84fn object_category(repo: &Repo, oid: Oid) -> Result<u8, GitError> {
85 match repo.git().try_find_header(oid.object_id()) {
86 Ok(Some(header)) => Ok(match header.kind() {
87 gix::object::Kind::Commit => CAT_COMMIT,
88 gix::object::Kind::Tree => CAT_TREE,
89 gix::object::Kind::Blob => CAT_BLOB,
90 gix::object::Kind::Tag => CAT_TAG,
91 }),
92 Ok(None) => Err(GitError::ObjectNotFound(oid)),
93 Err(error) => Err(GitError::Corrupt {
94 oid,
95 message: error.to_string(),
96 }),
97 }
98}
99
100fn one_selected<R: Order>(
101 repo: &Repo,
102 rev: &R,
103 commit_pos: IndexPosition,
104 commit: Oid,
105) -> Result<Selected, GitError> {
106 let closure = repo.select_pack_objects(Wants::new(&[commit]), Haves::new(&[]))?;
107 Ok(Selected {
108 commit_pos,
109 bits: closure_bits(rev, &closure)?,
110 })
111}
112
113pub(super) fn selected_entries<R: Order + Sync>(
114 repo: &Repo,
115 rev: &R,
116) -> Result<Vec<Selected>, GitError> {
117 let mut seen: HashSet<Oid> = HashSet::new();
118 let commits: Vec<(IndexPosition, Oid)> = repo
119 .references()?
120 .into_iter()
121 .filter_map(|record| peel_to_commit(repo, record.target))
122 .filter_map(|commit| rev.index_of(commit).map(|position| (position, commit)))
123 .filter(|(_, commit)| seen.insert(*commit))
124 .collect();
125
126 let path = repo.path().to_owned();
127 let mut entries: Vec<Selected> = knot_resource::map_chunks(&commits, |batch| {
128 let local = Repo::open(&path)?;
129 batch
130 .iter()
131 .map(|(commit_pos, commit)| one_selected(&local, rev, *commit_pos, *commit))
132 .collect::<Result<Vec<_>, GitError>>()
133 })?;
134 entries.sort_by_key(|entry| entry.commit_pos);
135 Ok(entries)
136}
137
138fn peel_to_commit(repo: &Repo, oid: Oid) -> Option<Oid> {
139 let object = repo.git().find_object(oid.object_id()).ok()?;
140 match object.kind {
141 gix::object::Kind::Commit => Some(oid),
142 gix::object::Kind::Tag => {
143 let target = object.try_into_tag().ok()?.target_id().ok()?.detach();
144 peel_to_commit(repo, Oid::from(target))
145 }
146 _ => None,
147 }
148}
149
150fn closure_bits(rev: &impl Order, closure: &[Oid]) -> Result<Vec<bool>, GitError> {
151 closure
152 .iter()
153 .try_fold(vec![false; rev.len()], |mut bits, oid| {
154 let position = rev.index_of(*oid).ok_or_else(|| {
155 GitError::Backend(format!(
156 "closure object {oid} is absent from the pack bitmap"
157 ))
158 })?;
159 bits[rev.bit_at_index(position).get() as usize] = true;
160 Ok(bits)
161 })
162}
163
164pub(super) fn assemble(
165 kind: gix::hash::Kind,
166 checksum: &gix_hash::ObjectId,
167 types: &TypeBits,
168 selected: &[Selected],
169) -> Result<Vec<u8>, GitError> {
170 let flags: u16 = OPT_FULL_DAG | OPT_LOOKUP_TABLE;
171 let mut out = Vec::new();
172 out.extend_from_slice(b"BITM");
173 out.extend_from_slice(&1u16.to_be_bytes());
174 out.extend_from_slice(&flags.to_be_bytes());
175 out.extend_from_slice(&(selected.len() as u32).to_be_bytes());
176 out.extend_from_slice(checksum.as_slice());
177
178 write_ewah(&mut out, &types.commits)?;
179 write_ewah(&mut out, &types.trees)?;
180 write_ewah(&mut out, &types.blobs)?;
181 write_ewah(&mut out, &types.tags)?;
182
183 let offsets: Vec<(IndexPosition, BitmapEntryOffset)> = selected
184 .iter()
185 .map(|entry| {
186 let at = BitmapEntryOffset::new(out.len() as u64);
187 out.extend_from_slice(&entry.commit_pos.get().to_be_bytes());
188 out.push(0);
189 out.push(0);
190 write_ewah(&mut out, &entry.bits)?;
191 Ok::<_, GitError>((entry.commit_pos, at))
192 })
193 .collect::<Result<_, _>>()?;
194
195 offsets.iter().for_each(|(commit_pos, offset)| {
196 out.extend_from_slice(&commit_pos.get().to_be_bytes());
197 out.extend_from_slice(&offset.get().to_be_bytes());
198 out.extend_from_slice(&0xffff_ffffu32.to_be_bytes());
199 });
200
201 let mut hasher = gix_hash::hasher(kind);
202 hasher.update(&out);
203 let digest = hasher
204 .try_finalize()
205 .map_err(|error| GitError::Backend(format!("bitmap checksum: {error}")))?;
206 out.extend_from_slice(digest.as_slice());
207 Ok(out)
208}
209
210fn write_ewah(out: &mut Vec<u8>, bits: &[bool]) -> Result<(), GitError> {
211 let vector = gix_bitmap::ewah::Vec::from_bits(bits)
212 .ok_or_else(|| GitError::Backend("ewah bit count exceeds u32".to_string()))?;
213 vector
214 .write_to(out)
215 .map_err(|error| GitError::Backend(format!("ewah write: {error}")))
216}
217
218pub(super) fn install(path: &Path, bytes: &[u8]) -> Result<(), GitError> {
219 knot_resource::atomic_write_bytes(path, bytes, knot_resource::FileMode::Inherited).map_err(
220 |error| GitError::Maintenance(format!("write bitmap {}: {}", path.display(), error.source)),
221 )
222}
223
224#[cfg(test)]
225mod tests {
226 use super::super::{BitPosition, IndexPosition};
227 use super::*;
228
229 struct FakeOrder {
230 oids: Vec<Oid>,
231 }
232
233 impl Order for FakeOrder {
234 fn len(&self) -> usize {
235 self.oids.len()
236 }
237
238 fn index_of(&self, oid: Oid) -> Option<IndexPosition> {
239 self.oids
240 .iter()
241 .position(|candidate| *candidate == oid)
242 .map(|position| IndexPosition::new(position as u32))
243 }
244
245 fn bit_at_index(&self, position: IndexPosition) -> BitPosition {
246 BitPosition::new(position.get())
247 }
248
249 fn oid_at_bit(&self, bit: BitPosition) -> Oid {
250 self.oids[bit.get() as usize]
251 }
252 }
253
254 fn oid(byte: u8) -> Oid {
255 Oid::from_hex(&format!("{byte:02x}").repeat(20)).unwrap()
256 }
257
258 #[test]
259 fn closure_bits_sets_one_bit_per_present_object() {
260 let order = FakeOrder {
261 oids: vec![oid(1), oid(2), oid(3)],
262 };
263 let bits = closure_bits(&order, &[oid(1), oid(3)]).unwrap();
264 assert_eq!(bits, vec![true, false, true]);
265 }
266
267 #[test]
268 fn closure_bits_errors_when_an_object_is_outside_the_pack() {
269 let order = FakeOrder {
270 oids: vec![oid(1), oid(2)],
271 };
272 assert!(
273 closure_bits(&order, &[oid(1), oid(9)]).is_err(),
274 "an incomplete closure must fail the bitmap rather than write a partial one"
275 );
276 }
277}