grit_lib/bench_fixture/
synth.rs

1//! Deterministic synthetic repository generator (grit-lib backed).
2
3use std::fs;
4use std::path::{Path, PathBuf};
5use std::time::Instant;
6
7use crate::error::{Error, Result};
8use crate::index::{Index, IndexEntry, MODE_REGULAR};
9use crate::objects::ObjectId;
10use crate::objects::{serialize_commit, serialize_tag, CommitData, ObjectKind, TagData};
11use crate::odb::Odb;
12use crate::pack_write::{install_pack_stream, whole_pack_uncompressed_size, InstallPackOptions};
13use crate::porcelain::checkout::checkout_between_trees;
14use crate::prune_packed::{prune_packed_objects, PrunePackedOptions};
15use crate::refs::{write_packed_refs_file, PackedRefRecord};
16use crate::repo::{InitOptions, Repository};
17use crate::transfer::{build_pack, PackBuildOptions};
18use crate::write_tree::{write_tree_from_index, write_tree_update_index, WriteTreeFlags};
19
20/// Benchmark fixture size tier.
21#[derive(Debug, Clone, Copy, PartialEq, Eq)]
22pub enum SynthTier {
23    /// CI-sized repo (~2k files, ~500 commits, ~1k refs).
24    S,
25    /// Medium repo (~20k files, ~5k commits, ~10k refs).
26    M,
27    /// Large repo (≥100k files, ≥50k commits, ≥100k refs, ≥1 GiB pack uncompressed).
28    L,
29}
30
31/// How tracked file paths are laid out in the worktree.
32#[derive(Debug, Clone, Copy, PartialEq, Eq)]
33pub enum PathLayout {
34    /// Layout derived from [`SynthTier`] (`S`/`M` grid or `L` wide+deep mix).
35    TierDefault,
36    /// Shallow `wide/w*/f*.txt` grid with a fixed number of files per leaf directory.
37    WideGrid {
38        /// Files in each `wide/w*` directory (directory count is `file_count / files_per_dir`).
39        files_per_dir: usize,
40    },
41}
42
43/// Core daily-benchmark repository shapes (deterministic via [`Self::spec`]).
44#[derive(Debug, Clone, Copy, PartialEq, Eq)]
45pub enum RepoShape {
46    /// ~100 tracked files and ~50 commits.
47    Small,
48    /// 10k files in ~100 directories and ~1000 commits (hot-path 10k layout).
49    Synth10k,
50    /// 100k files in a wide layout with ~1000 directories and ~1000 commits.
51    Synth100k,
52}
53
54impl RepoShape {
55    /// Full-size parameters for this shape.
56    #[must_use]
57    pub fn spec(self, smoke: bool) -> TierSpec {
58        let base = self.base_spec();
59        if smoke {
60            scale_tier_spec(base, 20)
61        } else {
62            base
63        }
64    }
65
66    fn base_spec(self) -> TierSpec {
67        match self {
68            Self::Small => TierSpec {
69                tier: SynthTier::S,
70                layout: PathLayout::TierDefault,
71                file_count: 100,
72                commit_count: 50,
73                ref_count: 60,
74                edits_per_commit: 4,
75                blob_body_bytes: 48,
76                loose_after_pack: 8,
77                seed: 0x3122_3501,
78            },
79            Self::Synth10k => TierSpec {
80                tier: SynthTier::M,
81                layout: PathLayout::TierDefault,
82                file_count: 10_000,
83                commit_count: 1_000,
84                ref_count: 800,
85                edits_per_commit: 8,
86                blob_body_bytes: 64,
87                loose_after_pack: 16,
88                seed: 0x3122_3502,
89            },
90            Self::Synth100k => TierSpec {
91                tier: SynthTier::L,
92                layout: PathLayout::WideGrid { files_per_dir: 100 },
93                file_count: 100_000,
94                commit_count: 1_000,
95                ref_count: 1_200,
96                edits_per_commit: 4,
97                blob_body_bytes: 12_000,
98                loose_after_pack: 32,
99                seed: 0x3122_3503,
100            },
101        }
102    }
103}
104
105fn scale_tier_spec(spec: TierSpec, divisor: usize) -> TierSpec {
106    let scale = |n: usize| (n / divisor).max(1);
107    TierSpec {
108        tier: spec.tier,
109        layout: spec.layout,
110        file_count: scale(spec.file_count),
111        commit_count: scale(spec.commit_count),
112        ref_count: scale(spec.ref_count).max(3),
113        edits_per_commit: scale(spec.edits_per_commit),
114        blob_body_bytes: spec.blob_body_bytes,
115        loose_after_pack: scale(spec.loose_after_pack),
116        seed: spec.seed,
117    }
118}
119
120/// Resolved numeric targets for a tier.
121#[derive(Debug, Clone, Copy)]
122pub struct TierSpec {
123    /// Tier label these numbers came from.
124    pub tier: SynthTier,
125    /// Path layout (independent of blob sizing in [`Self::tier`]).
126    pub layout: PathLayout,
127    /// Number of tracked file paths in the initial index.
128    pub file_count: usize,
129    /// Linear commit count on `refs/heads/main`.
130    pub commit_count: usize,
131    /// Total refs (branches, tags, plus `main`).
132    pub ref_count: usize,
133    /// Blob rewrites per commit after the root commit.
134    pub edits_per_commit: usize,
135    /// Target size for generated blob bodies (bytes).
136    pub blob_body_bytes: usize,
137    /// Loose blobs materialized at the tip after pack install.
138    pub loose_after_pack: usize,
139    /// Deterministic RNG seed for ref and edit selection.
140    pub seed: u64,
141}
142
143impl SynthTier {
144    /// Fixed tier parameters used by tests and the CLI.
145    #[must_use]
146    pub fn spec(self) -> TierSpec {
147        match self {
148            SynthTier::S => TierSpec {
149                tier: self,
150                layout: PathLayout::TierDefault,
151                file_count: 2_000,
152                commit_count: 500,
153                ref_count: 1_000,
154                edits_per_commit: 4,
155                blob_body_bytes: 48,
156                loose_after_pack: 8,
157                seed: 0x312_0001,
158            },
159            SynthTier::M => TierSpec {
160                tier: self,
161                layout: PathLayout::TierDefault,
162                file_count: 20_000,
163                commit_count: 5_000,
164                ref_count: 10_000,
165                edits_per_commit: 8,
166                blob_body_bytes: 64,
167                loose_after_pack: 16,
168                seed: 0x312_0002,
169            },
170            SynthTier::L => TierSpec {
171                tier: self,
172                layout: PathLayout::TierDefault,
173                file_count: 100_000,
174                commit_count: 50_000,
175                ref_count: 100_000,
176                edits_per_commit: 4,
177                blob_body_bytes: 12_000,
178                loose_after_pack: 32,
179                seed: 0x312_0003,
180            },
181        }
182    }
183}
184
185/// Summary returned after generation completes.
186#[derive(Debug, Clone)]
187pub struct SynthReport {
188    /// Tier that was generated.
189    pub tier: SynthTier,
190    /// Hex object id of `HEAD`.
191    pub head: String,
192    /// Commits on `main` (matches [`TierSpec::commit_count`]).
193    pub commit_count: usize,
194    /// Ref count (matches [`TierSpec::ref_count`]).
195    pub ref_count: usize,
196    /// Tracked paths (matches [`TierSpec::file_count`]).
197    pub file_count: usize,
198    /// Sum of inflated object sizes in the installed pack.
199    pub pack_uncompressed_bytes: u64,
200    /// Wall time spent generating the repository (milliseconds).
201    pub generation_ms: u64,
202    /// Output directory passed to [`generate_synth_repo`].
203    pub repo_path: PathBuf,
204}
205
206struct DetRng {
207    state: u64,
208}
209
210impl DetRng {
211    fn new(seed: u64) -> Self {
212        Self { state: seed }
213    }
214
215    fn next_u64(&mut self) -> u64 {
216        self.state = self.state.wrapping_mul(6364136223846793005).wrapping_add(1);
217        self.state
218    }
219
220    fn next_usize(&mut self, upper: usize) -> usize {
221        if upper == 0 {
222            return 0;
223        }
224        (self.next_u64() as usize) % upper
225    }
226}
227
228/// Fixed parameters for history-rewrite grit-bench scenarios (~10k files, 5k commits, 50 branches).
229#[must_use]
230pub fn history_rewrite_bench_spec() -> TierSpec {
231    TierSpec {
232        tier: SynthTier::M,
233        layout: PathLayout::TierDefault,
234        file_count: 10_000,
235        commit_count: 5_000,
236        ref_count: 51,
237        edits_per_commit: 1,
238        blob_body_bytes: 64,
239        loose_after_pack: 16,
240        seed: 0x319_3100,
241    }
242}
243
244/// Generate a deterministic synthetic repository at `out`.
245pub fn generate_synth_repo(out: &Path, tier: SynthTier) -> Result<SynthReport> {
246    generate_synth_repo_with_spec(out, tier.spec())
247}
248
249/// Generate a repository using explicit [`TierSpec`] numbers (for custom bench fixtures).
250pub fn generate_synth_repo_with_spec(out: &Path, spec: TierSpec) -> Result<SynthReport> {
251    let started = Instant::now();
252    if out.exists() {
253        fs::remove_dir_all(out).map_err(Error::Io)?;
254    }
255    fs::create_dir_all(out).map_err(Error::Io)?;
256    let repo = Repository::init(out, &InitOptions::default())?;
257    let head = generate_into_repo(&repo, spec)?;
258    let pack_bytes = build_pack(
259        repo.odb(),
260        &[head],
261        &[],
262        &PackBuildOptions {
263            delta: false,
264            ..PackBuildOptions::default()
265        },
266    )?;
267    let pack_uncompressed = whole_pack_uncompressed_size(&pack_bytes, repo.odb().hash_algo())?;
268    install_pack_stream(
269        repo.odb().objects_dir(),
270        &pack_bytes,
271        InstallPackOptions {
272            hash_algo: repo.odb().hash_algo(),
273            ..InstallPackOptions::default()
274        },
275    )?;
276    let _ = prune_packed_objects(
277        repo.odb().objects_dir(),
278        PrunePackedOptions {
279            quiet: true,
280            ..PrunePackedOptions::default()
281        },
282    )?;
283    materialize_loose_tip_objects(&repo, head, spec.loose_after_pack)?;
284    let head_tree = repo.odb().commit_tree(&head)?;
285    checkout_between_trees(&repo, None, &head_tree)?;
286    let elapsed = started.elapsed();
287    Ok(SynthReport {
288        tier: spec.tier,
289        head: head.to_string(),
290        commit_count: spec.commit_count,
291        ref_count: spec.ref_count,
292        file_count: spec.file_count,
293        pack_uncompressed_bytes: pack_uncompressed,
294        generation_ms: elapsed.as_millis() as u64,
295        repo_path: out.to_path_buf(),
296    })
297}
298
299fn generate_into_repo(repo: &Repository, spec: TierSpec) -> Result<ObjectId> {
300    let mut rng = DetRng::new(spec.seed);
301    let paths = file_paths_for_spec(spec);
302    let mut file_oids: Vec<ObjectId> = Vec::with_capacity(paths.len());
303    let mut index = Index::new();
304    index.hash_algo = repo.odb().hash_algo();
305
306    for (i, path) in paths.iter().enumerate() {
307        let body = blob_body(spec.tier, i as u32, 0, spec.blob_body_bytes);
308        let oid = repo.odb().write(ObjectKind::Blob, &body)?;
309        file_oids.push(oid);
310        index.add_or_replace(synth_index_entry(path, oid, body.len()));
311    }
312
313    let mut parent: Option<ObjectId> = None;
314    let mut commits: Vec<ObjectId> = Vec::with_capacity(spec.commit_count);
315    for commit_idx in 0..spec.commit_count {
316        if commit_idx > 0 {
317            for _ in 0..spec.edits_per_commit {
318                let fi = rng.next_usize(paths.len());
319                let body = blob_body(
320                    spec.tier,
321                    fi as u32,
322                    commit_idx as u32,
323                    spec.blob_body_bytes,
324                );
325                let oid = repo.odb().write(ObjectKind::Blob, &body)?;
326                file_oids[fi] = oid;
327                index.add_or_replace(synth_index_entry(&paths[fi], oid, body.len()));
328            }
329        }
330        let tree = if commit_idx == 0 {
331            write_tree_from_index(repo.odb(), &index, "")?
332        } else {
333            write_tree_update_index(repo.odb(), &mut index, "", WriteTreeFlags::default())?
334        };
335        let ts = 1_700_000_000i64 + commit_idx as i64;
336        let ident = format!("Synth Generator <synth@grit-scm.com> {ts} +0000");
337        let commit = CommitData {
338            tree,
339            parents: parent.into_iter().collect(),
340            author: ident.clone(),
341            committer: ident,
342            author_raw: Vec::new(),
343            committer_raw: Vec::new(),
344            encoding: None,
345            message: format!("synthetic commit {commit_idx}\n"),
346            raw_message: None,
347            extra_headers: Vec::new(),
348        };
349        let raw = serialize_commit(&commit);
350        let commit_oid = repo.odb().write(ObjectKind::Commit, &raw)?;
351        commits.push(commit_oid);
352        parent = Some(commit_oid);
353    }
354    let head = *commits
355        .last()
356        .ok_or_else(|| Error::CorruptObject("no commits generated".into()))?;
357    write_refs(repo, &commits, spec, &mut rng)?;
358    crate::refs::update_direct_ref_on_store(repo.refs(), repo.git_dir(), "refs/heads/main", &head)?;
359    Ok(head)
360}
361
362fn write_refs(
363    repo: &Repository,
364    commits: &[ObjectId],
365    spec: TierSpec,
366    rng: &mut DetRng,
367) -> Result<()> {
368    let branch_refs = spec.ref_count * 2 / 3;
369    let tag_refs = spec.ref_count - branch_refs - 1; // minus main written loose
370    let mut records = Vec::with_capacity(spec.ref_count);
371    for i in 0..branch_refs {
372        let name = format!("refs/heads/synth/b{i:06}");
373        let oid = commits[i % commits.len()];
374        records.push(PackedRefRecord {
375            refname: name,
376            oid,
377            peeled: None,
378        });
379    }
380    for i in 0..tag_refs {
381        let commit = commits[(i * 17 + rng.next_usize(commits.len())) % commits.len()];
382        if i % 2 == 0 {
383            let tag_name = format!("v{i:06}");
384            let ts = 1_700_100_000i64 + i as i64;
385            let tagger = format!("Synth Generator <synth@grit-scm.com> {ts} +0000");
386            let tag = TagData {
387                object: commit,
388                object_type: "commit".to_owned(),
389                tag: tag_name.clone(),
390                tagger: Some(tagger),
391                extra_headers: Vec::new(),
392                message: format!("annotated {tag_name}\n"),
393            };
394            let raw = serialize_tag(&tag);
395            let tag_oid = repo.odb().write(ObjectKind::Tag, &raw)?;
396            records.push(PackedRefRecord {
397                refname: format!("refs/tags/{tag_name}"),
398                oid: tag_oid,
399                peeled: Some(commit),
400            });
401        } else {
402            records.push(PackedRefRecord {
403                refname: format!("refs/tags/light-{i:06}"),
404                oid: commit,
405                peeled: None,
406            });
407        }
408    }
409    write_packed_refs_file(repo.git_dir(), &records)?;
410    Ok(())
411}
412
413fn materialize_loose_tip_objects(repo: &Repository, head: ObjectId, count: usize) -> Result<()> {
414    let head_tree = repo.odb().commit_tree(&head)?;
415    let mut blobs = Vec::new();
416    collect_blob_oids(repo.odb(), &head_tree, &mut blobs)?;
417    for oid in blobs.into_iter().take(count) {
418        let obj = repo.odb().read(&oid)?;
419        repo.odb().write_loose_materialize(obj.kind, &obj.data)?;
420    }
421    Ok(())
422}
423
424fn collect_blob_oids(odb: &Odb, tree_oid: &ObjectId, out: &mut Vec<ObjectId>) -> Result<()> {
425    use crate::index::MODE_TREE;
426    let tree_obj = odb.read(tree_oid)?;
427    for entry in crate::objects::parse_tree(&tree_obj.data)? {
428        if entry.mode == MODE_TREE {
429            collect_blob_oids(odb, &entry.oid, out)?;
430        } else {
431            out.push(entry.oid);
432        }
433    }
434    Ok(())
435}
436
437fn synth_index_entry(path: &[u8], oid: ObjectId, size: usize) -> IndexEntry {
438    IndexEntry {
439        ctime_sec: 1_700_000_000,
440        ctime_nsec: 0,
441        mtime_sec: 1_700_000_000,
442        mtime_nsec: 0,
443        dev: 0,
444        ino: 0,
445        mode: MODE_REGULAR,
446        uid: 0,
447        gid: 0,
448        size: size as u32,
449        oid,
450        flags: (path.len().min(0xfff)) as u16,
451        flags_extended: None,
452        path: path.to_vec(),
453        base_index_pos: 0,
454    }
455}
456
457fn file_paths_for_spec(spec: TierSpec) -> Vec<Vec<u8>> {
458    match spec.layout {
459        PathLayout::WideGrid { files_per_dir } => wide_grid_paths(spec.file_count, files_per_dir),
460        PathLayout::TierDefault => file_paths_tier_default(spec.tier, spec.file_count),
461    }
462}
463
464fn wide_grid_paths(count: usize, files_per_dir: usize) -> Vec<Vec<u8>> {
465    let files_per_dir = files_per_dir.max(1);
466    let mut out = Vec::with_capacity(count);
467    for i in 0..count {
468        let dir = i / files_per_dir;
469        let file = i % files_per_dir;
470        out.push(format!("wide/w{dir:05}/f{file:04}.txt").into_bytes());
471    }
472    out
473}
474
475fn file_paths_tier_default(tier: SynthTier, count: usize) -> Vec<Vec<u8>> {
476    match tier {
477        SynthTier::S | SynthTier::M => {
478            let mut out = Vec::with_capacity(count);
479            for i in 0..count {
480                let dir = i / 100;
481                let file = i % 100;
482                out.push(format!("data/d{dir:04}/f{file:04}.txt").into_bytes());
483            }
484            out
485        }
486        SynthTier::L => {
487            let wide_count = count * 2 / 3;
488            let mut out = Vec::with_capacity(count);
489            for i in 0..wide_count {
490                let dir = i / 1000;
491                let file = i % 1000;
492                out.push(format!("wide/w{dir:05}/f{file:04}.txt").into_bytes());
493            }
494            for j in 0..(count - wide_count) {
495                let i = wide_count + j;
496                let seg = |k: usize| format!("{:02x}", (i.wrapping_mul(0x9e37) >> (k * 4)) & 0xff);
497                out.push(
498                    format!(
499                        "deep/{}/{}/{}/{}/{}/{}/{}/{}/leaf_{j:05}.txt",
500                        seg(0),
501                        seg(1),
502                        seg(2),
503                        seg(3),
504                        seg(4),
505                        seg(5),
506                        seg(6),
507                        seg(7),
508                    )
509                    .into_bytes(),
510                );
511            }
512            out
513        }
514    }
515}
516
517fn blob_body(tier: SynthTier, file_id: u32, version: u32, body_bytes: usize) -> Vec<u8> {
518    let mut s = match tier {
519        SynthTier::L => {
520            let line_count = 32usize;
521            let mut lines: Vec<String> = (0..line_count)
522                .map(|ln| format!("file={file_id} line={ln} seed=0"))
523                .collect();
524            for churn in 0..3usize {
525                let ln = ((file_id as usize + version as usize + churn) % (line_count - 2)) + 1;
526                lines[ln] = format!("file={file_id} line={ln} ver={version} churn={churn}");
527            }
528            let mut joined = lines.join("\n");
529            joined.push('\n');
530            joined
531        }
532        SynthTier::S | SynthTier::M => format!("synth file={file_id} ver={version}\n"),
533    };
534    if s.len() < body_bytes {
535        s.push_str(&"x".repeat(body_bytes - s.len()));
536    }
537    s.into_bytes()
538}
539
540#[cfg(test)]
541mod layout_tests {
542    use super::*;
543    use std::collections::HashSet;
544
545    fn path_component_depth(path: &[u8]) -> usize {
546        path.iter().filter(|&&b| b == b'/').count() + 1
547    }
548
549    fn distinct_parent_directories(paths: &[Vec<u8>]) -> usize {
550        paths
551            .iter()
552            .filter_map(|p| {
553                let s = std::str::from_utf8(p).ok()?;
554                s.rfind('/').map(|idx| &s[..idx])
555            })
556            .collect::<HashSet<_>>()
557            .len()
558    }
559
560    fn assert_wide_grid_topology(spec: TierSpec) {
561        let paths = file_paths_for_spec(spec);
562        assert_eq!(paths.len(), spec.file_count);
563        let files_per_dir = match spec.layout {
564            PathLayout::WideGrid { files_per_dir } => files_per_dir,
565            PathLayout::TierDefault => panic!("expected wide grid layout"),
566        };
567        let expected_dirs = spec.file_count.div_ceil(files_per_dir);
568        assert_eq!(distinct_parent_directories(&paths), expected_dirs);
569        assert!(
570            paths
571                .iter()
572                .all(|p| path_component_depth(p) == 3 && p.starts_with(b"wide/w")),
573            "expected shallow wide/w*/f* paths only"
574        );
575    }
576
577    #[test]
578    fn repo_shape_synth100k_uses_wide_grid_directories() {
579        assert_wide_grid_topology(RepoShape::Synth100k.spec(false));
580        assert_eq!(
581            distinct_parent_directories(&file_paths_for_spec(RepoShape::Synth100k.spec(false))),
582            1_000
583        );
584    }
585
586    #[test]
587    fn repo_shape_synth100k_smoke_scales_directories() {
588        let smoke = RepoShape::Synth100k.spec(true);
589        assert_eq!(smoke.file_count, 5_000);
590        assert_eq!(smoke.commit_count, 50);
591        assert_wide_grid_topology(smoke);
592        assert_eq!(distinct_parent_directories(&file_paths_for_spec(smoke)), 50);
593    }
594
595    #[test]
596    fn repo_shape_daily_counts() {
597        let small = RepoShape::Small.spec(false);
598        assert_eq!(small.file_count, 100);
599        assert_eq!(small.commit_count, 50);
600
601        let ten_k = RepoShape::Synth10k.spec(false);
602        assert_eq!(ten_k.file_count, 10_000);
603        assert_eq!(ten_k.commit_count, 1_000);
604        assert_eq!(
605            distinct_parent_directories(&file_paths_for_spec(ten_k)),
606            100
607        );
608
609        let hundred_k = RepoShape::Synth100k.spec(false);
610        assert_eq!(hundred_k.file_count, 100_000);
611        assert_eq!(hundred_k.commit_count, 1_000);
612    }
613
614    #[test]
615    fn l_tier_paths_are_deep_and_wide() {
616        let paths = file_paths_tier_default(SynthTier::L, 10_000);
617        let max_depth = paths
618            .iter()
619            .map(|p| path_component_depth(p))
620            .max()
621            .unwrap_or(0);
622        assert!(
623            max_depth >= 10,
624            "expected deep hierarchy, max depth was {max_depth}"
625        );
626        let wide_shallow = paths
627            .iter()
628            .filter(|p| path_component_depth(p) <= 3)
629            .count();
630        assert!(
631            wide_shallow > 5_000,
632            "expected wide shallow files, got {wide_shallow}"
633        );
634    }
635
636    #[test]
637    fn l_tier_blobs_have_multiline_churn() {
638        let body = blob_body(SynthTier::L, 7, 42, 800);
639        let text = String::from_utf8(body).expect("utf-8");
640        assert!(text.lines().count() >= 20, "expected many lines for blame");
641        assert!(text.contains("ver=42"));
642        assert!(text.contains("churn=0"));
643    }
644
645    #[test]
646    fn s_tier_keeps_shallow_layout() {
647        let paths = file_paths_tier_default(SynthTier::S, 100);
648        assert!(paths.iter().all(|p| path_component_depth(p) == 3));
649    }
650
651    #[test]
652    fn repo_shape_smoke_scales_down() {
653        let full = RepoShape::Synth10k.spec(false);
654        let smoke = RepoShape::Synth10k.spec(true);
655        assert_eq!(smoke.file_count, full.file_count / 20);
656        assert_eq!(smoke.commit_count, full.commit_count / 20);
657    }
658}
grit_lib/bench_fixture/synth.rs

grit_lib/bench_fixture/
synth.rs
