alice.pds.demo.boltless.dev
This repository has no description
25 kB
795 lines
did:plc:3fwecdnvtcscjnrx2p4n7a…
1use std::collections::{HashMap, HashSet};
2
3use gix::ObjectId;
4use gix::objs::tree::EntryKind as TreeEntryKind;
5use gix::objs::{CommitRef, Kind, TagRefIter, TreeRef};
6use gix::prelude::FindExt;
7use knot_git::Repo;
8use knot_types::UnixSeconds;
9
10use crate::MaintError;
11use crate::fsio;
12
13const GRAPH_PARENT_NONE: u32 = 0x7000_0000;
14const GRAPH_EXTRA_EDGES_NEEDED: u32 = 0x8000_0000;
15const GRAPH_LAST_EDGE: u32 = 0x8000_0000;
16const GRAPH_GENERATION_MAX: u32 = 0x3FFF_FFFF;
17const MAX_PEEL_DEPTH: usize = 32;
18
19const CORRECTED_OFFSET_OVERFLOW: u32 = 0x8000_0000;
20const CORRECTED_OFFSET_MAX: u64 = (1 << 31) - 1;
21
22const BLOOM_HASH_VERSION: u32 = 2;
23const BLOOM_NUM_HASHES: u32 = 7;
24const BLOOM_BITS_PER_ENTRY: u32 = 10;
25const BLOOM_MAX_CHANGED_PATHS: usize = 512;
26const BLOOM_SEED0: u32 = 0x293a_e76f;
27const BLOOM_SEED1: u32 = 0x7e64_6e2c;
28const MURMUR_C1: u32 = 0xcc9e_2d51;
29const MURMUR_C2: u32 = 0x1b87_3593;
30const MURMUR_N: u32 = 0xe654_6b64;
31
32#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
33struct Generation(u32);
34
35impl Generation {
36 const fn new(value: u32) -> Self {
37 Self(value)
38 }
39
40 const fn get(self) -> u32 {
41 self.0
42 }
43
44 const fn succ(self) -> Self {
45 Self(self.0.saturating_add(1))
46 }
47}
48
49knot_types::scalar_newtype! {
50 struct GraphPosition(u32);
51}
52
53#[derive(Debug, Clone, Copy)]
54struct ParentField(u32);
55
56impl ParentField {
57 const NONE: Self = Self(GRAPH_PARENT_NONE);
58
59 fn from_position(position: Option<GraphPosition>) -> Self {
60 position.map_or(Self::NONE, |position| Self(position.get()))
61 }
62
63 fn extra_edges(index: usize) -> Self {
64 Self(GRAPH_EXTRA_EDGES_NEEDED | index as u32)
65 }
66
67 fn to_be_bytes(self) -> [u8; 4] {
68 self.0.to_be_bytes()
69 }
70}
71
72#[derive(Debug, Clone, Copy)]
73struct ParentFields {
74 first: ParentField,
75 second: ParentField,
76}
77
78#[derive(Debug, Clone, Copy)]
79struct EdgeField(u32);
80
81impl EdgeField {
82 fn new(parent: ParentField, last: bool) -> Self {
83 Self(parent.0 | if last { GRAPH_LAST_EDGE } else { 0 })
84 }
85
86 fn to_be_bytes(self) -> [u8; 4] {
87 self.0.to_be_bytes()
88 }
89}
90
91knot_types::scalar_newtype! {
92 struct CorrectedDate(u64);
93}
94
95struct ChangedPathFilter(Vec<u8>);
96
97impl ChangedPathFilter {
98 fn bytes(&self) -> &[u8] {
99 &self.0
100 }
101
102 fn len_bytes(&self) -> usize {
103 self.0.len()
104 }
105}
106
107struct CommitMeta {
108 tree: ObjectId,
109 parents: Vec<ObjectId>,
110 seconds: UnixSeconds,
111}
112
113pub fn graph_path(repo: &Repo) -> std::path::PathBuf {
114 repo.objects_dir().join("info").join("commit-graph")
115}
116
117pub fn exists(repo: &Repo) -> bool {
118 graph_path(repo).exists()
119}
120
121pub fn write(repo: &Repo) -> Result<bool, MaintError> {
122 let kind = repo.object_format().kind();
123 let Some(commits) = collect(repo, kind)? else {
124 return Ok(false);
125 };
126 if commits.is_empty() {
127 return Ok(false);
128 }
129 let blooms = changed_path_filters(repo, &commits, kind)?;
130 let bytes = serialize(&commits, &blooms, kind);
131 let path = graph_path(repo);
132 let info_dir = repo.objects_dir().join("info");
133 std::fs::create_dir_all(&info_dir).map_err(|error| fsio::io_error(&info_dir, error))?;
134 clear_chain(&info_dir)?;
135 knot_resource::atomic_write_bytes(&path, &bytes, knot_resource::FileMode::Inherited)?;
136 Ok(true)
137}
138
139pub fn remove(repo: &Repo) -> Result<(), MaintError> {
140 let path = graph_path(repo);
141 match std::fs::remove_file(&path) {
142 Ok(()) => {}
143 Err(error) if error.kind() == std::io::ErrorKind::NotFound => {}
144 Err(error) => return Err(fsio::io_error(&path, error)),
145 }
146 clear_chain(&repo.objects_dir().join("info"))
147}
148
149fn clear_chain(info_dir: &std::path::Path) -> Result<(), MaintError> {
150 let chain_dir = info_dir.join("commit-graphs");
151 match std::fs::remove_dir_all(&chain_dir) {
152 Ok(()) => Ok(()),
153 Err(error) if error.kind() == std::io::ErrorKind::NotFound => Ok(()),
154 Err(error) => Err(fsio::io_error(&chain_dir, error)),
155 }
156}
157
158fn collect(
159 repo: &Repo,
160 kind: gix::hash::Kind,
161) -> Result<Option<HashMap<ObjectId, CommitMeta>>, MaintError> {
162 let odb = &repo.git().objects;
163 let mut stack: Vec<ObjectId> = repo
164 .references()?
165 .into_iter()
166 .filter_map(|record| peel_to_commit(odb, record.target.object_id(), kind, MAX_PEEL_DEPTH))
167 .collect();
168 let mut commits: HashMap<ObjectId, CommitMeta> = HashMap::new();
169 while let Some(oid) = stack.pop() {
170 if commits.contains_key(&oid) {
171 continue;
172 }
173 let mut buf = Vec::new();
174 let data = match odb.find(&oid, &mut buf) {
175 Ok(data) => data,
176 Err(_) => return Ok(None),
177 };
178 if data.kind != Kind::Commit {
179 return Ok(None);
180 }
181 let commit = CommitRef::from_bytes(data.data, kind)
182 .map_err(|error| MaintError::CommitGraph(error.to_string()))?;
183 let tree = commit.tree();
184 let parents: Vec<ObjectId> = commit.parents().collect();
185 let seconds = UnixSeconds::new(commit.committer().map(|sig| sig.seconds()).unwrap_or(0));
186 parents.iter().for_each(|parent| stack.push(*parent));
187 commits.insert(
188 oid,
189 CommitMeta {
190 tree,
191 parents,
192 seconds,
193 },
194 );
195 }
196 Ok(Some(commits))
197}
198
199fn peel_to_commit(
200 odb: &gix::odb::Handle,
201 oid: ObjectId,
202 kind: gix::hash::Kind,
203 depth: usize,
204) -> Option<ObjectId> {
205 if depth == 0 {
206 return None;
207 }
208 let mut buf = Vec::new();
209 let data = odb.find(&oid, &mut buf).ok()?;
210 match data.kind {
211 Kind::Commit => Some(oid),
212 Kind::Tag => {
213 let target = TagRefIter::from_bytes(data.data, kind).target_id().ok()?;
214 peel_to_commit(odb, target, kind, depth - 1)
215 }
216 _ => None,
217 }
218}
219
220fn serialize(
221 commits: &HashMap<ObjectId, CommitMeta>,
222 blooms: &HashMap<ObjectId, ChangedPathFilter>,
223 kind: gix::hash::Kind,
224) -> Vec<u8> {
225 let hash_len = match kind {
226 gix::hash::Kind::Sha256 => 32,
227 _ => 20,
228 };
229 let mut oids: Vec<ObjectId> = commits.keys().copied().collect();
230 oids.sort();
231 let position: HashMap<ObjectId, GraphPosition> = oids
232 .iter()
233 .enumerate()
234 .map(|(index, oid)| (*oid, GraphPosition::new(index as u32)))
235 .collect();
236 let generations = generations(commits, &oids);
237 let corrected = corrected_dates(commits, &oids);
238
239 let mut edges: Vec<EdgeField> = Vec::new();
240 let mut cdat: Vec<u8> = Vec::with_capacity(oids.len() * (hash_len + 16));
241 oids.iter().for_each(|oid| {
242 let meta = &commits[oid];
243 cdat.extend_from_slice(meta.tree.as_slice());
244 let parents = parent_fields(&meta.parents, &position, &mut edges);
245 cdat.extend_from_slice(&parents.first.to_be_bytes());
246 cdat.extend_from_slice(&parents.second.to_be_bytes());
247 let generation = generations
248 .get(oid)
249 .copied()
250 .unwrap_or(Generation::new(0))
251 .get() as u64;
252 let date = (meta.seconds.get().max(0) as u64) & 0x3_FFFF_FFFF;
253 let packed = (generation << 34) | date;
254 cdat.extend_from_slice(&packed.to_be_bytes());
255 });
256
257 let (gda2, overflow) = oids.iter().fold(
258 (Vec::with_capacity(oids.len() * 4), Vec::<u64>::new()),
259 |(mut bytes, mut ovf), oid| {
260 let date = commits[oid].seconds.get().max(0) as u64;
261 let offset = corrected
262 .get(oid)
263 .copied()
264 .unwrap_or(CorrectedDate::new(date))
265 .get()
266 .saturating_sub(date);
267 let packed = if offset > CORRECTED_OFFSET_MAX {
268 let index = ovf.len() as u32;
269 ovf.push(offset);
270 CORRECTED_OFFSET_OVERFLOW | index
271 } else {
272 offset as u32
273 };
274 bytes.extend_from_slice(&packed.to_be_bytes());
275 (bytes, ovf)
276 },
277 );
278 let gdo2: Vec<u8> = overflow
279 .iter()
280 .flat_map(|value| value.to_be_bytes())
281 .collect();
282
283 let bidx: Vec<u8> = oids
284 .iter()
285 .scan(0u32, |acc, oid| {
286 *acc = acc.saturating_add(filter_for(blooms, oid).len_bytes() as u32);
287 Some(acc.to_be_bytes())
288 })
289 .flatten()
290 .collect();
291 let bdat: Vec<u8> = [BLOOM_HASH_VERSION, BLOOM_NUM_HASHES, BLOOM_BITS_PER_ENTRY]
292 .iter()
293 .flat_map(|value| value.to_be_bytes())
294 .chain(
295 oids.iter()
296 .flat_map(|oid| filter_for(blooms, oid).bytes().iter().copied()),
297 )
298 .collect();
299
300 let oidf = fanout(&oids);
301 let mut oidl: Vec<u8> = Vec::with_capacity(oids.len() * hash_len);
302 oids.iter()
303 .for_each(|oid| oidl.extend_from_slice(oid.as_slice()));
304 let mut edge_bytes: Vec<u8> = Vec::with_capacity(edges.len() * 4);
305 edges
306 .iter()
307 .for_each(|edge| edge_bytes.extend_from_slice(&edge.to_be_bytes()));
308
309 let mut chunks: Vec<(&[u8; 4], Vec<u8>)> = vec![
310 (b"OIDF", oidf),
311 (b"OIDL", oidl),
312 (b"CDAT", cdat),
313 (b"GDA2", gda2),
314 ];
315 if !gdo2.is_empty() {
316 chunks.push((b"GDO2", gdo2));
317 }
318 if !edge_bytes.is_empty() {
319 chunks.push((b"EDGE", edge_bytes));
320 }
321 chunks.push((b"BIDX", bidx));
322 chunks.push((b"BDAT", bdat));
323
324 assemble(chunks, kind)
325}
326
327fn filter_for<'a>(
328 blooms: &'a HashMap<ObjectId, ChangedPathFilter>,
329 oid: &ObjectId,
330) -> &'a ChangedPathFilter {
331 static EMPTY: ChangedPathFilter = ChangedPathFilter(Vec::new());
332 blooms.get(oid).unwrap_or(&EMPTY)
333}
334
335fn parent_fields(
336 parents: &[ObjectId],
337 position: &HashMap<ObjectId, GraphPosition>,
338 edges: &mut Vec<EdgeField>,
339) -> ParentFields {
340 let pos = |oid: &ObjectId| ParentField::from_position(position.get(oid).copied());
341 match parents {
342 [] => ParentFields {
343 first: ParentField::NONE,
344 second: ParentField::NONE,
345 },
346 [first] => ParentFields {
347 first: pos(first),
348 second: ParentField::NONE,
349 },
350 [first, second] => ParentFields {
351 first: pos(first),
352 second: pos(second),
353 },
354 [first, rest @ ..] => {
355 let edge_index = edges.len();
356 let last = rest.len() - 1;
357 rest.iter().enumerate().for_each(|(index, parent)| {
358 edges.push(EdgeField::new(pos(parent), index == last));
359 });
360 ParentFields {
361 first: pos(first),
362 second: ParentField::extra_edges(edge_index),
363 }
364 }
365 }
366}
367
368fn fanout(oids: &[ObjectId]) -> Vec<u8> {
369 let mut buckets = [0u32; 256];
370 oids.iter()
371 .for_each(|oid| buckets[oid.as_slice()[0] as usize] += 1);
372 (1..256).for_each(|index| buckets[index] += buckets[index - 1]);
373 buckets
374 .iter()
375 .flat_map(|count| count.to_be_bytes())
376 .collect()
377}
378
379fn resolve_topo<V: Copy>(
380 commits: &HashMap<ObjectId, CommitMeta>,
381 oids: &[ObjectId],
382 transform: impl Fn(&[V], &CommitMeta) -> V,
383) -> HashMap<ObjectId, V> {
384 let mut value: HashMap<ObjectId, V> = HashMap::new();
385 oids.iter().for_each(|root| {
386 if value.contains_key(root) {
387 return;
388 }
389 let mut stack = vec![*root];
390 while let Some(top) = stack.last().copied() {
391 if value.contains_key(&top) {
392 stack.pop();
393 continue;
394 }
395 let parents = &commits[&top].parents;
396 let unresolved: Vec<ObjectId> = parents
397 .iter()
398 .filter(|parent| commits.contains_key(*parent) && !value.contains_key(*parent))
399 .copied()
400 .collect();
401 if unresolved.is_empty() {
402 let resolved: Vec<V> = parents
403 .iter()
404 .filter_map(|parent| value.get(parent))
405 .copied()
406 .collect();
407 let computed = transform(&resolved, &commits[&top]);
408 value.insert(top, computed);
409 stack.pop();
410 } else {
411 unresolved.into_iter().for_each(|parent| stack.push(parent));
412 }
413 }
414 });
415 value
416}
417
418fn generations(
419 commits: &HashMap<ObjectId, CommitMeta>,
420 oids: &[ObjectId],
421) -> HashMap<ObjectId, Generation> {
422 resolve_topo(commits, oids, |parents: &[Generation], _meta| {
423 parents
424 .iter()
425 .copied()
426 .max()
427 .unwrap_or(Generation::new(0))
428 .succ()
429 .min(Generation::new(GRAPH_GENERATION_MAX))
430 })
431}
432
433fn corrected_dates(
434 commits: &HashMap<ObjectId, CommitMeta>,
435 oids: &[ObjectId],
436) -> HashMap<ObjectId, CorrectedDate> {
437 resolve_topo(commits, oids, |parents: &[CorrectedDate], meta| {
438 let max_parent = parents.iter().map(|date| date.get()).max().unwrap_or(0);
439 let date = meta.seconds.get().max(0) as u64;
440 let base = if date > max_parent {
441 date - 1
442 } else {
443 max_parent
444 };
445 CorrectedDate::new(base + 1)
446 })
447}
448
449fn tuned(handle: &gix::odb::Handle) -> gix::odb::Handle {
450 let mut odb = handle.clone();
451 odb.refresh_never();
452 odb.prevent_pack_unload();
453 odb
454}
455
456fn one_filter(
457 odb: &gix::odb::Handle,
458 commits: &HashMap<ObjectId, CommitMeta>,
459 meta: &CommitMeta,
460 kind: gix::hash::Kind,
461) -> Result<ChangedPathFilter, MaintError> {
462 let parent_tree = meta
463 .parents
464 .first()
465 .and_then(|parent| commits.get(parent))
466 .map(|found| found.tree);
467 let changed = diff_trees(odb, parent_tree, Some(meta.tree), kind)?;
468 Ok(build_filter(&changed))
469}
470
471fn changed_path_filters(
472 repo: &Repo,
473 commits: &HashMap<ObjectId, CommitMeta>,
474 kind: gix::hash::Kind,
475) -> Result<HashMap<ObjectId, ChangedPathFilter>, MaintError> {
476 let entries: Vec<(&ObjectId, &CommitMeta)> = commits.iter().collect();
477 let path = repo.path().to_owned();
478 let produced = knot_resource::map_chunks(&entries, |batch| {
479 let local = Repo::open(&path)?;
480 let odb = tuned(&local.git().objects);
481 batch
482 .iter()
483 .map(|(oid, meta)| Ok((**oid, one_filter(&odb, commits, meta, kind)?)))
484 .collect::<Result<Vec<_>, MaintError>>()
485 })?;
486 Ok(produced.into_iter().collect())
487}
488
489fn tree_entries(
490 odb: &gix::odb::Handle,
491 oid: Option<ObjectId>,
492 kind: gix::hash::Kind,
493) -> Result<HashMap<Vec<u8>, (TreeEntryKind, ObjectId)>, MaintError> {
494 let Some(oid) = oid else {
495 return Ok(HashMap::new());
496 };
497 if oid == ObjectId::empty_tree(kind) {
498 return Ok(HashMap::new());
499 }
500 let mut buf = Vec::new();
501 let data = odb
502 .find(&oid, &mut buf)
503 .map_err(|error| MaintError::CommitGraph(error.to_string()))?;
504 if data.kind != Kind::Tree {
505 return Ok(HashMap::new());
506 }
507 let tree = TreeRef::from_bytes(data.data, kind)
508 .map_err(|error| MaintError::CommitGraph(error.to_string()))?;
509 Ok(tree
510 .entries
511 .into_iter()
512 .map(|entry| {
513 (
514 entry.filename.to_vec(),
515 (entry.mode.kind(), entry.oid.to_owned()),
516 )
517 })
518 .collect())
519}
520
521fn diff_trees(
522 odb: &gix::odb::Handle,
523 parent: Option<ObjectId>,
524 commit: Option<ObjectId>,
525 kind: gix::hash::Kind,
526) -> Result<Vec<Vec<u8>>, MaintError> {
527 let is_tree = |kind: &TreeEntryKind| matches!(kind, TreeEntryKind::Tree);
528 let mut out: Vec<Vec<u8>> = Vec::new();
529 let mut stack: Vec<(Option<ObjectId>, Option<ObjectId>, Vec<u8>)> =
530 vec![(parent, commit, Vec::new())];
531 while let Some((parent, commit, prefix)) = stack.pop() {
532 let parent_entries = tree_entries(odb, parent, kind)?;
533 let commit_entries = tree_entries(odb, commit, kind)?;
534 let names: HashSet<&Vec<u8>> = parent_entries.keys().chain(commit_entries.keys()).collect();
535 names.into_iter().for_each(|name| {
536 let full: Vec<u8> = prefix.iter().copied().chain(name.iter().copied()).collect();
537 let subprefix =
538 || -> Vec<u8> { full.iter().copied().chain(std::iter::once(b'/')).collect() };
539 match (parent_entries.get(name), commit_entries.get(name)) {
540 (None, Some((ck, co))) => {
541 if is_tree(ck) {
542 stack.push((None, Some(*co), subprefix()));
543 } else {
544 out.push(full);
545 }
546 }
547 (Some((pk, po)), None) => {
548 if is_tree(pk) {
549 stack.push((Some(*po), None, subprefix()));
550 } else {
551 out.push(full);
552 }
553 }
554 (Some((pk, po)), Some((ck, co))) => match (is_tree(pk), is_tree(ck)) {
555 (true, true) => {
556 if po != co {
557 stack.push((Some(*po), Some(*co), subprefix()));
558 }
559 }
560 (false, false) => {
561 if po != co || pk != ck {
562 out.push(full);
563 }
564 }
565 (true, false) => {
566 stack.push((Some(*po), None, subprefix()));
567 out.push(full);
568 }
569 (false, true) => {
570 stack.push((None, Some(*co), subprefix()));
571 out.push(full);
572 }
573 },
574 (None, None) => {}
575 }
576 });
577 }
578 Ok(out)
579}
580
581fn build_filter(changed: &[Vec<u8>]) -> ChangedPathFilter {
582 if changed.len() > BLOOM_MAX_CHANGED_PATHS {
583 // `0xFF` = git's "too many changed paths" marker.
584 return ChangedPathFilter(vec![0xFF]);
585 }
586 let paths: HashSet<Vec<u8>> = changed.iter().flat_map(|path| prefixes(path)).collect();
587 if paths.len() > BLOOM_MAX_CHANGED_PATHS {
588 return ChangedPathFilter(vec![0xFF]);
589 }
590 let bits = paths.len() * BLOOM_BITS_PER_ENTRY as usize;
591 let len_bytes = bits.div_ceil(8).max(1);
592 let modulus = (len_bytes * 8) as u64;
593 let data = paths.iter().fold(vec![0u8; len_bytes], |mut data, path| {
594 let hash0 = murmur3(BLOOM_SEED0, path);
595 let hash1 = murmur3(BLOOM_SEED1, path);
596 (0..BLOOM_NUM_HASHES).for_each(|index| {
597 let combined = hash0.wrapping_add(index.wrapping_mul(hash1));
598 let position = (combined as u64) % modulus;
599 data[(position / 8) as usize] |= 1 << (position % 8);
600 });
601 data
602 });
603 ChangedPathFilter(data)
604}
605
606fn prefixes(path: &[u8]) -> Vec<Vec<u8>> {
607 std::iter::once(path.to_vec())
608 .chain(
609 path.iter()
610 .enumerate()
611 .filter(|(_, byte)| **byte == b'/')
612 .map(|(index, _)| path[..index].to_vec()),
613 )
614 .collect()
615}
616
617fn murmur3(seed: u32, data: &[u8]) -> u32 {
618 let body = data.len() / 4;
619 let mixed = (0..body).fold(seed, |seed, index| {
620 let base = index * 4;
621 let block =
622 u32::from_le_bytes([data[base], data[base + 1], data[base + 2], data[base + 3]]);
623 let block = block
624 .wrapping_mul(MURMUR_C1)
625 .rotate_left(15)
626 .wrapping_mul(MURMUR_C2);
627 (seed ^ block)
628 .rotate_left(13)
629 .wrapping_mul(5)
630 .wrapping_add(MURMUR_N)
631 });
632 let tail = &data[body * 4..];
633 let tail_key = tail.iter().enumerate().fold(0u32, |key, (index, byte)| {
634 key | ((*byte as u32) << (8 * index))
635 });
636 let mixed = if tail.is_empty() {
637 mixed
638 } else {
639 mixed
640 ^ tail_key
641 .wrapping_mul(MURMUR_C1)
642 .rotate_left(15)
643 .wrapping_mul(MURMUR_C2)
644 };
645 let mixed = mixed ^ (data.len() as u32);
646 let mixed = (mixed ^ (mixed >> 16)).wrapping_mul(0x85eb_ca6b);
647 let mixed = (mixed ^ (mixed >> 13)).wrapping_mul(0xc2b2_ae35);
648 mixed ^ (mixed >> 16)
649}
650
651fn assemble(chunks: Vec<(&[u8; 4], Vec<u8>)>, kind: gix::hash::Kind) -> Vec<u8> {
652 let num_chunks = chunks.len() as u8;
653 let table_len = (chunks.len() + 1) * 12;
654 let data_start = 8 + table_len;
655 let hash_version = match kind {
656 gix::hash::Kind::Sha256 => 2u8,
657 _ => 1u8,
658 };
659
660 let mut out: Vec<u8> = Vec::new();
661 out.extend_from_slice(b"CGPH");
662 out.push(1);
663 out.push(hash_version);
664 out.push(num_chunks);
665 out.push(0);
666
667 let mut offset = data_start as u64;
668 chunks.iter().for_each(|(id, body)| {
669 out.extend_from_slice(*id);
670 out.extend_from_slice(&offset.to_be_bytes());
671 offset += body.len() as u64;
672 });
673 out.extend_from_slice(&[0, 0, 0, 0]);
674 out.extend_from_slice(&offset.to_be_bytes());
675
676 chunks
677 .iter()
678 .for_each(|(_, body)| out.extend_from_slice(body));
679
680 let mut hasher = gix_hash::hasher(kind);
681 hasher.update(&out);
682 let checksum = hasher
683 .try_finalize()
684 .expect("commit-graph checksum finalizes");
685 out.extend_from_slice(checksum.as_slice());
686 out
687}
688
689#[cfg(test)]
690mod tests {
691 use super::{GRAPH_GENERATION_MAX, Generation, build_filter, murmur3};
692
693 #[test]
694 fn succ_advances_by_one_and_orders_above_its_source() {
695 let base = Generation::new(7);
696 assert_eq!(base.succ(), Generation::new(8));
697 assert!(base.succ() > base);
698 }
699
700 #[test]
701 fn succ_saturates_at_the_numeric_ceiling() {
702 assert_eq!(Generation::new(u32::MAX).succ(), Generation::new(u32::MAX));
703 }
704
705 #[test]
706 fn a_child_sits_one_above_its_highest_parent() {
707 let parents = [Generation::new(2), Generation::new(5), Generation::new(3)];
708 let child = parents.into_iter().max().unwrap().succ();
709 assert_eq!(child, Generation::new(6));
710 }
711
712 #[test]
713 fn clamping_holds_the_value_at_the_format_maximum() {
714 let value = Generation::new(GRAPH_GENERATION_MAX)
715 .succ()
716 .min(Generation::new(GRAPH_GENERATION_MAX));
717 assert_eq!(value, Generation::new(GRAPH_GENERATION_MAX));
718 }
719
720 #[test]
721 fn empty_change_set_is_a_single_zero_word() {
722 let filter = build_filter(&[]);
723 assert_eq!(filter.bytes(), &[0u8]);
724 }
725
726 #[test]
727 fn overlarge_change_set_is_a_single_saturated_word() {
728 let many: Vec<Vec<u8>> = (0..600).map(|n| format!("p{n}").into_bytes()).collect();
729 let filter = build_filter(&many);
730 assert_eq!(filter.bytes(), &[0xFFu8]);
731 }
732
733 #[test]
734 fn murmur3_matches_known_vectors() {
735 assert_eq!(murmur3(0, b""), 0);
736 assert_eq!(murmur3(0, b"hello"), 0x248bfa47);
737 }
738
739 #[test]
740 fn diff_trees_walks_a_deeply_nested_tree_without_overflowing_the_stack() {
741 use knot_git::{EntryKind, Repo, StagedAction, StagedChange};
742 use knot_types::Oid;
743
744 let depth = 4000usize;
745 let dir = tempfile::tempdir().unwrap();
746 let git_dir = dir.path().join("deep.git");
747
748 let build_dir = git_dir.clone();
749 let tree = std::thread::Builder::new()
750 .stack_size(64 * 1024 * 1024)
751 .spawn(move || {
752 let repo = Repo::create(&build_dir).unwrap();
753 let kind = repo.object_format().kind();
754 let base = Oid::from(gix::ObjectId::empty_tree(kind));
755 let path = (0..depth)
756 .map(|_| "d")
757 .chain(std::iter::once("leaf.txt"))
758 .collect::<Vec<_>>()
759 .join("/");
760 repo.write_staged_tree(
761 base,
762 &[StagedChange {
763 path: knot_types::RepoPath::new(path).unwrap(),
764 action: StagedAction::Put {
765 content: b"leaf\n".to_vec(),
766 kind: EntryKind::Blob,
767 },
768 }],
769 )
770 .unwrap()
771 .object_id()
772 })
773 .unwrap()
774 .join()
775 .unwrap();
776
777 let changed = std::thread::Builder::new()
778 .stack_size(256 * 1024)
779 .spawn(move || {
780 let repo = Repo::open(&git_dir).unwrap();
781 let kind = repo.object_format().kind();
782 super::diff_trees(&repo.git().objects, None, Some(tree), kind).unwrap()
783 })
784 .unwrap()
785 .join()
786 .expect("diff_trees on a 256 KiB stack mustn't overflow on a 4000-deep tree");
787
788 assert_eq!(changed.len(), 1, "the single leaf is the only changed path");
789 assert_eq!(
790 changed[0].iter().filter(|byte| **byte == b'/').count(),
791 depth,
792 "the changed path retains every nesting level"
793 );
794 }
795}