agentis-ctx 0.3.5

//! Deterministic synthetic-repo generator.
//!
//! Produces seeded, byte-reproducible Rust codebases with cross-file call
//! graphs and synthesized git history, used by the performance harness in
//! `perf/` and reusable by the external ctx-bench suite.
//!
//! # Determinism contract
//!
//! The same [`FixtureSpec`] always produces a byte-identical tree at every
//! commit, and — because commits use a fixed identity, fixed dates, and fixed
//! messages — identical commit SHAs. Generation never depends on wall-clock
//! time, environment, platform, or hash-map iteration order; randomness comes
//! from an inline SplitMix64 PRNG and the only floating-point operations are
//! IEEE 754 basic ops (`+`, `*`, `/`, `sqrt`), which are exactly specified.
//! Any change that alters the generated bytes MUST bump
//! [`FIXTURE_FORMAT_VERSION`].
//!
//! # Shape of the output
//!
//! Files live at `src/m{module:02}/f{file:04}.rs` and parse individually as
//! Rust, but the tree is deliberately not a compilable cargo project — the
//! ctx indexer only needs parseable `.rs` files. Function names are globally
//! unique (`f_{file:04}_{k}`), so the bare-identifier calls the generator
//! emits resolve to unique symbols during edge resolution and materialize as
//! cross-file call edges in the index. Callee files are chosen with a
//! zipf-skewed popularity distribution ([`FixtureSpec::fan_in_skew`]), giving
//! a few very-high-fan-in files and a long tail.

use std::path::{Path, PathBuf};
use std::process::Command;

use crate::error::{CtxError, Result};
use crate::testutil::GitRepo;

/// Version of the generated byte format. Bump on ANY change to the bytes
/// produced by [`generate`] or [`apply_change_set`] for a given spec.
pub const FIXTURE_FORMAT_VERSION: u32 = 1;

/// 2024-01-01T00:00:00Z; the initial commit date. Commit `i` (0 = initial)
/// is dated `BASE_UNIX_TIME + i` days.
const BASE_UNIX_TIME: i64 = 1_704_067_200;

// Independent PRNG stream tags, so draws for one purpose never perturb
// another (e.g. rewriting a body must not change call targets).
const STREAM_POPULARITY: u64 = 0x504f_5055_4c41_5249;
const STREAM_STRUCTURE: u64 = 0x5354_5255_4354_5552;
const STREAM_BODY: u64 = 0x424f_4459_424f_4459;
const STREAM_FN_COUNT: u64 = 0x464e_434f_554e_5400;
const STREAM_HISTORY: u64 = 0x4849_5354_4f52_5900;
const STREAM_CHANGESET: u64 = 0x4348_414e_4745_5345;

// Content-salt namespaces: initial tree, history commit `c`, changeset
// round `r`. They must never collide so every rewrite changes bytes.
const SALT_INITIAL: u64 = 0;
const SALT_HISTORY_BASE: u64 = 1;
const SALT_CHANGESET_BASE: u64 = 1 << 32;

/// Approximate lines a file spends outside function bodies (header, consts,
/// struct + impl). Used to derive the per-file function count from `avg_loc`.
const FILE_OVERHEAD_LOC: usize = 16;
/// Approximate lines per generated function (signature to closing brace).
const FN_BODY_LOC: usize = 12;

/// Parameters for a synthetic repository.
#[derive(Debug, Clone)]
pub struct FixtureSpec {
    /// Master seed; every derived PRNG stream mixes this in.
    pub seed: u64,
    /// Total number of generated `.rs` files.
    pub files: usize,
    /// Approximate lines per file (drives the per-file function count).
    pub avg_loc: usize,
    /// Number of top-level directories `src/m00..m{modules-1}`.
    pub modules: usize,
    /// Zipf-ish exponent for callee-file popularity (e.g. `1.1`). Higher
    /// values concentrate fan-in on fewer files.
    pub fan_in_skew: f64,
    /// Synthesized mutation commits after the initial one.
    pub history_commits: usize,
}

impl FixtureSpec {
    /// 2,000 files, ~50 lines each, 20 modules, 3 history commits.
    pub fn repo_2k() -> Self {
        FixtureSpec {
            seed: 0xC7C5_2000,
            files: 2000,
            avg_loc: 50,
            modules: 20,
            fan_in_skew: 1.1,
            history_commits: 3,
        }
    }

    /// ~1,500 files x ~100 LOC, roughly 150k lines total.
    pub fn repo_150k_loc() -> Self {
        FixtureSpec {
            seed: 0xC7C5_150C,
            files: 1500,
            avg_loc: 100,
            modules: 15,
            fan_in_skew: 1.1,
            history_commits: 3,
        }
    }

    /// ~20 files; small enough for smoke tests that index the result.
    pub fn tiny() -> Self {
        FixtureSpec {
            seed: 0xC7C5_0011,
            files: 20,
            avg_loc: 40,
            modules: 3,
            fan_in_skew: 1.1,
            history_commits: 2,
        }
    }
}

/// Generate the repository (git init + initial commit + history commits) at
/// `root`, which must be empty or nonexistent.
///
/// Deterministic: the same spec produces a byte-identical tree at every
/// commit and identical commit SHAs (fixed identity and dates).
pub fn generate(spec: &FixtureSpec, root: &Path) -> Result<()> {
    validate(spec)?;
    if root.exists() && std::fs::read_dir(root)?.next().is_some() {
        return Err(CtxError::Other(format!(
            "fixture root '{}' is not empty",
            root.display()
        )));
    }

    let repo = GitRepo::init(root);
    // Line endings must reach the object store verbatim, or blob (and thus
    // commit) hashes would vary with the host's autocrlf configuration.
    run_git(root, &["config", "core.autocrlf", "false"])?;

    std::fs::write(root.join("README.md"), readme(spec))?;
    let pop = Popularity::new(spec);
    for file_idx in 0..spec.files {
        write_source_file(spec, &pop, root, file_idx, SALT_INITIAL)?;
    }
    repo.commit_all_with_date("fixture: initial tree", &commit_date(0));

    let churn = (spec.files / 64).max(1);
    for c in 0..spec.history_commits {
        let selected = select_files(spec, STREAM_HISTORY, c as u64, churn);
        for &file_idx in &selected {
            write_source_file(spec, &pop, root, file_idx, SALT_HISTORY_BASE + c as u64)?;
        }
        repo.commit_all_with_date(
            &format!("fixture: churn commit {}", c + 1),
            &commit_date(c as i64 + 1),
        );
    }
    Ok(())
}

/// Deterministically rewrite `n_files` existing files, leaving the working
/// tree dirty (no commit, no staging). Selection and content depend on
/// `(spec.seed, round)`, so each perf round performs identical fresh work.
///
/// Returns the rewritten paths (rooted at `root`), sorted by file index.
pub fn apply_change_set(
    spec: &FixtureSpec,
    root: &Path,
    n_files: usize,
    round: u32,
) -> Result<Vec<PathBuf>> {
    validate(spec)?;
    if n_files > spec.files {
        return Err(CtxError::Other(format!(
            "cannot rewrite {} files: spec has only {}",
            n_files, spec.files
        )));
    }

    let pop = Popularity::new(spec);
    let selected = select_files(spec, STREAM_CHANGESET, round as u64, n_files);
    let mut paths = Vec::with_capacity(selected.len());
    for &file_idx in &selected {
        write_source_file(
            spec,
            &pop,
            root,
            file_idx,
            SALT_CHANGESET_BASE + round as u64,
        )?;
        paths.push(root.join(rel_path(spec, file_idx)));
    }
    Ok(paths)
}

// ============================================================================
// PRNG (SplitMix64) and deterministic math
// ============================================================================

/// Inline SplitMix64. Small, seedable, and identical on every platform.
struct Rng(u64);

impl Rng {
    fn new(seed: u64) -> Rng {
        Rng(seed)
    }

    fn next_u64(&mut self) -> u64 {
        self.0 = self.0.wrapping_add(0x9E37_79B9_7F4A_7C15);
        let mut z = self.0;
        z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
        z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
        z ^ (z >> 31)
    }

    /// Uniform in `0..n` (`n > 0`). Modulo bias is irrelevant here.
    fn next_range(&mut self, n: u64) -> u64 {
        self.next_u64() % n
    }

    /// Uniform in `[0, 1)` with 53 bits of precision.
    fn next_f64(&mut self) -> f64 {
        (self.next_u64() >> 11) as f64 * (1.0 / (1u64 << 53) as f64)
    }
}

/// Combine two seed values into an independent stream seed.
fn mix(a: u64, b: u64) -> u64 {
    Rng::new(a ^ b.rotate_left(32)).next_u64()
}

fn mix3(a: u64, b: u64, c: u64) -> u64 {
    mix(mix(a, b), c)
}

/// `x^p` for `x > 0`, `p >= 0`, bit-identical on every platform: built only
/// from IEEE 754 multiplication and `sqrt`, both correctly rounded by spec
/// (`f64::powf` is libm-dependent and must not be used on generation paths).
/// The fractional exponent uses 24 binary digits, far more precision than a
/// popularity weight needs.
fn det_pow(x: f64, p: f64) -> f64 {
    let int_part = p as u64;
    let mut result = 1.0;
    let mut base = x;
    let mut n = int_part;
    while n > 0 {
        if n & 1 == 1 {
            result *= base;
        }
        base *= base;
        n >>= 1;
    }
    let mut frac = p - int_part as f64;
    let mut root = x;
    for _ in 0..24 {
        root = root.sqrt();
        frac *= 2.0;
        if frac >= 1.0 {
            result *= root;
            frac -= 1.0;
        }
    }
    result
}

// ============================================================================
// Popularity (zipf-skewed callee-file selection)
// ============================================================================

/// Precomputed zipf-ish popularity over file indices: rank `r` has weight
/// `(r + 1)^-fan_in_skew`, and ranks are mapped to file indices through a
/// seeded permutation so hot files are scattered across modules.
struct Popularity {
    rank_to_file: Vec<usize>,
    cdf: Vec<f64>,
}

impl Popularity {
    fn new(spec: &FixtureSpec) -> Popularity {
        let mut rng = Rng::new(mix(spec.seed, STREAM_POPULARITY));
        let rank_to_file = permutation(spec.files, &mut rng);
        let mut cdf = Vec::with_capacity(spec.files);
        let mut total = 0.0;
        for rank in 0..spec.files {
            total += 1.0 / det_pow((rank + 1) as f64, spec.fan_in_skew);
            cdf.push(total);
        }
        Popularity { rank_to_file, cdf }
    }

    /// Draw a file index with zipf-skewed probability.
    fn sample(&self, rng: &mut Rng) -> usize {
        let total = *self.cdf.last().expect("cdf is non-empty");
        let u = rng.next_f64() * total;
        let rank = self
            .cdf
            .partition_point(|&c| c <= u)
            .min(self.cdf.len() - 1);
        self.rank_to_file[rank]
    }
}

/// Fisher-Yates permutation of `0..n` driven by `rng`.
fn permutation(n: usize, rng: &mut Rng) -> Vec<usize> {
    let mut v: Vec<usize> = (0..n).collect();
    for i in (1..n).rev() {
        let j = rng.next_range(i as u64 + 1) as usize;
        v.swap(i, j);
    }
    v
}

/// The first `n` entries of a `(seed, stream, round)`-seeded permutation of
/// all file indices, sorted ascending for deterministic write order.
fn select_files(spec: &FixtureSpec, stream: u64, round: u64, n: usize) -> Vec<usize> {
    let mut rng = Rng::new(mix3(spec.seed, stream, round));
    let mut selected = permutation(spec.files, &mut rng);
    selected.truncate(n);
    selected.sort_unstable();
    selected
}

// ============================================================================
// Source generation
// ============================================================================

/// Module index for a file: contiguous blocks of files per module.
fn module_of(spec: &FixtureSpec, file_idx: usize) -> usize {
    file_idx * spec.modules / spec.files
}

/// Repo-relative path of a generated file.
fn rel_path(spec: &FixtureSpec, file_idx: usize) -> String {
    format!("src/m{:02}/f{:04}.rs", module_of(spec, file_idx), file_idx)
}

/// Number of functions in a file: a pure function of `(seed, file_idx)` so
/// callers can size call targets without generating the callee, and so
/// rewrites (salts) never change the symbol set or call graph.
fn fn_count(spec: &FixtureSpec, file_idx: usize) -> usize {
    let mut rng = Rng::new(mix3(spec.seed, STREAM_FN_COUNT, file_idx as u64));
    let base = (spec.avg_loc.saturating_sub(FILE_OVERHEAD_LOC) / FN_BODY_LOC).max(2);
    base + rng.next_range(2) as usize
}

/// A small positive literal for generated arithmetic.
fn lit(rng: &mut Rng) -> i64 {
    (rng.next_u64() & 0xFFFF) as i64 + 1
}

/// Render one file. The structural stream (function count, branch shapes,
/// call targets) depends only on `(seed, file_idx)`; the body stream mixes in
/// `salt`, so rewrites change literals but never the call graph. The header
/// embeds `salt` so every rewrite is guaranteed to change bytes.
fn file_source(spec: &FixtureSpec, pop: &Popularity, file_idx: usize, salt: u64) -> String {
    let module = module_of(spec, file_idx);
    let n_fns = fn_count(spec, file_idx);
    let mut structure = Rng::new(mix3(spec.seed, STREAM_STRUCTURE, file_idx as u64));
    let mut body = Rng::new(mix3(spec.seed, mix(STREAM_BODY, salt), file_idx as u64));

    let mut out = String::with_capacity(spec.avg_loc * 48 + 256);
    out.push_str(&format!(
        "//! Fixture file {file_idx:04} in module m{module:02} \
         (format v{FIXTURE_FORMAT_VERSION}, salt {salt}).\n"
    ));
    out.push_str("//! Machine-generated by ctx::fixture; do not edit.\n\n");

    let n_consts = 2 + structure.next_range(2) as usize;
    for j in 0..n_consts {
        out.push_str(&format!(
            "pub const C_{file_idx:04}_{j}: i64 = {};\n",
            lit(&mut body)
        ));
    }
    out.push('\n');

    out.push_str(&format!(
        "pub struct S{file_idx:04} {{\n    pub a: i64,\n    pub b: i64,\n}}\n\n"
    ));
    out.push_str(&format!("impl S{file_idx:04} {{\n"));
    out.push_str(&format!(
        "    pub fn m_{file_idx:04}_0(&self, x: i64) -> i64 {{\n"
    ));
    out.push_str(&format!(
        "        let t = self.a.wrapping_mul(x).wrapping_add({});\n",
        lit(&mut body)
    ));
    out.push_str("        if t % 2 == 0 { t } else { t.wrapping_neg() }\n");
    out.push_str("    }\n}\n");

    for k in 0..n_fns {
        out.push('\n');
        push_function(spec, pop, &mut out, file_idx, k, &mut structure, &mut body);
    }
    out
}

/// Render one `fn f_{file:04}_{k}` with varied branching and 1-4 cross-file
/// calls by bare identifier.
fn push_function(
    spec: &FixtureSpec,
    pop: &Popularity,
    out: &mut String,
    file_idx: usize,
    k: usize,
    structure: &mut Rng,
    body: &mut Rng,
) {
    out.push_str(&format!("pub fn f_{file_idx:04}_{k}(a: i64) -> i64 {{\n"));
    out.push_str(&format!("    let mut acc = a ^ {};\n", lit(body)));
    out.push_str(&format!("    let step = {};\n", lit(body)));

    // 0..=3 control-flow blocks so cyclomatic complexity varies per function.
    let n_branches = structure.next_range(4);
    for _ in 0..n_branches {
        match structure.next_range(3) {
            0 => {
                let d = 2 + structure.next_range(5);
                out.push_str(&format!("    if acc % {d} == 0 {{\n"));
                out.push_str(&format!("        acc = acc.wrapping_mul({});\n", lit(body)));
                out.push_str("    } else {\n");
                out.push_str(&format!("        acc = acc.wrapping_sub({});\n", lit(body)));
                out.push_str("    }\n");
            }
            1 => {
                let n = 1 + structure.next_range(6);
                out.push_str(&format!("    for i in 0..{n}i64 {{\n"));
                out.push_str(&format!(
                    "        acc = acc.wrapping_add(i * {});\n",
                    lit(body)
                ));
                out.push_str("    }\n");
            }
            _ => {
                out.push_str("    match acc % 4 {\n");
                out.push_str(&format!(
                    "        0 => acc = acc.wrapping_add({}),\n",
                    lit(body)
                ));
                out.push_str(&format!(
                    "        1 => acc = acc.wrapping_sub({}),\n",
                    lit(body)
                ));
                out.push_str(&format!("        2 => acc ^= {},\n", lit(body)));
                out.push_str("        _ => acc = acc.wrapping_mul(3),\n");
                out.push_str("    }\n");
            }
        }
    }

    // 1..=4 cross-file calls; callee files follow the zipf popularity.
    let n_calls = 1 + structure.next_range(4);
    for _ in 0..n_calls {
        let mut callee = pop.sample(structure);
        if callee == file_idx {
            callee = (callee + 1) % spec.files;
        }
        let j = structure.next_range(fn_count(spec, callee) as u64);
        out.push_str(&format!(
            "    acc = acc.wrapping_add(f_{callee:04}_{j}(acc));\n"
        ));
    }
    out.push_str("    acc.wrapping_add(step)\n}\n");
}

/// Write one generated file (creating parent directories).
fn write_source_file(
    spec: &FixtureSpec,
    pop: &Popularity,
    root: &Path,
    file_idx: usize,
    salt: u64,
) -> Result<()> {
    let path = root.join(rel_path(spec, file_idx));
    if let Some(parent) = path.parent() {
        std::fs::create_dir_all(parent)?;
    }
    std::fs::write(&path, file_source(spec, pop, file_idx, salt))?;
    Ok(())
}

fn readme(spec: &FixtureSpec) -> String {
    format!(
        "# ctx synthetic fixture\n\n\
         Machine-generated Rust tree for ctx benchmarks \
         (format v{FIXTURE_FORMAT_VERSION}). Files parse individually but the \
         tree is not a compilable cargo project.\n\n\
         - seed: {}\n\
         - files: {}\n\
         - avg_loc: {}\n\
         - modules: {}\n\
         - fan_in_skew: {}\n\
         - history_commits: {}\n",
        spec.seed, spec.files, spec.avg_loc, spec.modules, spec.fan_in_skew, spec.history_commits,
    )
}

// ============================================================================
// Git plumbing
// ============================================================================

/// Commit date for commit `i` (0 = initial), in git's internal
/// `<unix-timestamp> <tz>` format.
fn commit_date(i: i64) -> String {
    format!("{} +0000", BASE_UNIX_TIME + i * 86_400)
}

/// Run a git command in `root`, mapping failure to [`CtxError::Git`].
fn run_git(root: &Path, args: &[&str]) -> Result<()> {
    let output = Command::new("git").args(args).current_dir(root).output()?;
    if !output.status.success() {
        return Err(CtxError::git(format!(
            "git {:?} failed: {}",
            args,
            String::from_utf8_lossy(&output.stderr)
        )));
    }
    Ok(())
}

fn validate(spec: &FixtureSpec) -> Result<()> {
    if spec.files < 2 {
        return Err(CtxError::Other(
            "fixture spec needs at least 2 files for cross-file calls".to_string(),
        ));
    }
    if spec.modules == 0 || spec.modules > spec.files {
        return Err(CtxError::Other(format!(
            "fixture spec needs 1..=files modules, got {}",
            spec.modules
        )));
    }
    if !spec.fan_in_skew.is_finite() || spec.fan_in_skew < 0.0 {
        return Err(CtxError::Other(format!(
            "fan_in_skew must be finite and non-negative, got {}",
            spec.fan_in_skew
        )));
    }
    Ok(())
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn splitmix_stream_is_stable() {
        // Pin the PRNG output so an accidental algorithm change is caught
        // even before the (slower) tree-level determinism tests run.
        let mut rng = Rng::new(42);
        assert_eq!(rng.next_u64(), 13679457532755275413);
        assert_eq!(rng.next_u64(), 2949826092126892291);
    }

    #[test]
    fn det_pow_matches_expected_values() {
        assert_eq!(det_pow(2.0, 2.0), 4.0);
        assert_eq!(det_pow(4.0, 0.5), 2.0);
        // ~3^1.1 within the 24-bit fractional-exponent precision.
        assert!((det_pow(3.0, 1.1) - 3.348_369_522_101_714).abs() < 1e-6);
    }

    #[test]
    fn file_source_is_salt_sensitive_but_graph_stable() {
        let spec = FixtureSpec::tiny();
        let pop = Popularity::new(&spec);
        let a = file_source(&spec, &pop, 3, 0);
        let b = file_source(&spec, &pop, 3, 7);
        assert_ne!(a, b, "different salt must change bytes");

        // Same function set and same call targets regardless of salt.
        let calls = |s: &str| -> Vec<String> {
            s.lines()
                .filter(|l| l.contains("(acc));"))
                .map(|l| l.trim().to_string())
                .collect()
        };
        assert_eq!(calls(&a), calls(&b));
    }

    #[test]
    fn selection_is_deterministic_per_round() {
        let spec = FixtureSpec::tiny();
        assert_eq!(
            select_files(&spec, STREAM_CHANGESET, 0, 5),
            select_files(&spec, STREAM_CHANGESET, 0, 5)
        );
        assert_ne!(
            select_files(&spec, STREAM_CHANGESET, 0, 5),
            select_files(&spec, STREAM_CHANGESET, 1, 5)
        );
    }
}