thread-flow 0.1.0

// SPDX-FileCopyrightText: 2025 Knitli Inc. <knitli@knit.li>
// SPDX-License-Identifier: AGPL-3.0-or-later

//! Incremental update system performance benchmarks.
//!
//! This benchmark suite validates Phase 4 constitutional requirements and measures
//! performance characteristics of the incremental analysis system.
//!
//! ## Benchmark Groups (48-72 benchmarks total):
//!
//! 1. **change_detection** - Incremental overhead validation
//!    - Fingerprint computation speed
//!    - Change detection latency
//!    - Graph traversal time
//!    - **Target: <10ms overhead**
//!
//! 2. **graph_traversal** - Invalidation propagation
//!    - BFS traversal (100/1000/10000 nodes)
//!    - Affected file calculation
//!    - **Target: <50ms for 1000 nodes**
//!
//! 3. **topological_sort** - Analysis ordering
//!    - DAG sorting (various sizes)
//!    - Cycle detection overhead
//!    - Parallel sorting (feature-gated)
//!
//! 4. **reanalysis** - Incremental vs full
//!    - 1% change rate
//!    - 10% change rate
//!    - 50% change rate
//!    - Speedup factor measurement
//!
//! 5. **cache_hit_rate** - Repeated analysis
//!    - Zero changes
//!    - Identical content
//!    - **Target: >90% hit rate**
//!
//! 6. **executor_comparison** - Concurrency (feature-gated)
//!    - Sequential baseline
//!    - Tokio async
//!    - Rayon parallel
//!    - Speedup measurements
//!
//! ## Constitutional Requirements Validation:
//!
//! - Incremental overhead: <10ms (Constitution VI)
//! - Graph traversal: <50ms for 1000 nodes (Constitution VI)
//! - Cache hit rate: >90% (Constitution VI)
//! - All targets must be met for compliance
//!
//! ## Running:
//!
//! ```bash
//! # Run all incremental benchmarks
//! cargo bench -p thread-flow incremental_benchmarks --all-features
//!
//! # Run specific benchmark group
//! cargo bench -p thread-flow incremental_benchmarks -- change_detection
//! cargo bench -p thread-flow incremental_benchmarks -- graph_traversal
//! cargo bench -p thread-flow incremental_benchmarks -- cache_hit_rate
//! ```

use ::std::hint::black_box;
use criterion::{BenchmarkId, Criterion, criterion_group, criterion_main};
use std::path::PathBuf;
use thread_flow::incremental::{
    AnalysisDefFingerprint, DependencyEdge, DependencyGraph, DependencyType, InMemoryStorage,
    StorageBackend,
};

// ============================================================================
// Test Data Generation
// ============================================================================

/// Helper to generate synthetic Rust file content
fn generate_rust_file(file_id: usize, size: &str) -> String {
    match size {
        "small" => format!(
            r#"
// File {}
pub fn func_{}() -> i32 {{
    {}
}}
"#,
            file_id, file_id, file_id
        ),
        "medium" => format!(
            r#"
// File {}
use std::collections::HashMap;

pub struct Data{} {{
    value: i32,
}}

impl Data{} {{
    pub fn new(v: i32) -> Self {{ Self {{ value: v }} }}
    pub fn process(&self) -> i32 {{ self.value * 2 }}
}}

pub fn func_{}() -> Data{} {{
    Data{}::new({})
}}
"#,
            file_id, file_id, file_id, file_id, file_id, file_id, file_id
        ),
        "large" => {
            let mut code = format!(
                r#"
// File {}
use std::collections::{{HashMap, HashSet}};
use std::sync::Arc;

pub struct Module{} {{
    data: Vec<i32>,
}}
"#,
                file_id, file_id
            );
            for i in 0..10 {
                code.push_str(&format!(
                    r#"
pub fn func_{}_{}() -> i32 {{ {} }}
"#,
                    file_id, i, i
                ));
            }
            code
        }
        _ => panic!("Unknown size: {}", size),
    }
}

/// Creates a linear dependency chain: 0 -> 1 -> 2 -> ... -> n
fn create_linear_chain(size: usize) -> DependencyGraph {
    let mut graph = DependencyGraph::new();

    for i in 0..size {
        let current = PathBuf::from(format!("file_{}.rs", i));
        if i < size - 1 {
            let next = PathBuf::from(format!("file_{}.rs", i + 1));
            graph.add_edge(DependencyEdge::new(current, next, DependencyType::Import));
        } else {
            // Ensure leaf node exists
            graph.add_node(&current);
        }
    }

    graph
}

/// Creates a diamond dependency pattern:
/// ```text
///       0
///      / \
///     1   2
///      \ /
///       3
/// ```
fn create_diamond_pattern() -> DependencyGraph {
    let mut graph = DependencyGraph::new();

    let n0 = PathBuf::from("file_0.rs");
    let n1 = PathBuf::from("file_1.rs");
    let n2 = PathBuf::from("file_2.rs");
    let n3 = PathBuf::from("file_3.rs");

    graph.add_edge(DependencyEdge::new(
        n0.clone(),
        n1.clone(),
        DependencyType::Import,
    ));
    graph.add_edge(DependencyEdge::new(n0, n2.clone(), DependencyType::Import));
    graph.add_edge(DependencyEdge::new(n1, n3.clone(), DependencyType::Import));
    graph.add_edge(DependencyEdge::new(n2, n3, DependencyType::Import));

    graph
}

/// Creates a tree structure with specified depth and fanout
fn create_tree_structure(depth: usize, fanout: usize) -> DependencyGraph {
    let mut graph = DependencyGraph::new();
    let mut node_id = 0;

    fn add_tree_level(
        graph: &mut DependencyGraph,
        parent: PathBuf,
        depth: usize,
        fanout: usize,
        node_id: &mut usize,
    ) {
        if depth == 0 {
            return;
        }

        for _ in 0..fanout {
            let child = PathBuf::from(format!("file_{}.rs", *node_id));
            *node_id += 1;

            graph.add_edge(DependencyEdge::new(
                parent.clone(),
                child.clone(),
                DependencyType::Import,
            ));

            add_tree_level(graph, child, depth - 1, fanout, node_id);
        }
    }

    let root = PathBuf::from("file_0.rs");
    graph.add_node(&root);
    node_id += 1;

    add_tree_level(&mut graph, root, depth, fanout, &mut node_id);

    graph
}

// ============================================================================
// Benchmark Group 1: Change Detection
// ============================================================================

fn benchmark_change_detection(c: &mut Criterion) {
    let mut group = c.benchmark_group("change_detection");

    // Fingerprint computation speed
    let small_content = generate_rust_file(0, "small");
    let medium_content = generate_rust_file(0, "medium");
    let large_content = generate_rust_file(0, "large");

    group.bench_function("fingerprint_small_file", |b| {
        b.iter(|| {
            black_box(AnalysisDefFingerprint::new(black_box(
                small_content.as_bytes(),
            )))
        });
    });

    group.bench_function("fingerprint_medium_file", |b| {
        b.iter(|| {
            black_box(AnalysisDefFingerprint::new(black_box(
                medium_content.as_bytes(),
            )))
        });
    });

    group.bench_function("fingerprint_large_file", |b| {
        b.iter(|| {
            black_box(AnalysisDefFingerprint::new(black_box(
                large_content.as_bytes(),
            )))
        });
    });

    // Change detection latency
    let old_fp = AnalysisDefFingerprint::new(b"original content");

    group.bench_function("detect_no_change", |b| {
        b.iter(|| black_box(old_fp.content_matches(black_box(b"original content"))));
    });

    group.bench_function("detect_change", |b| {
        b.iter(|| black_box(!old_fp.content_matches(black_box(b"modified content"))));
    });

    // Graph traversal time (small)
    let graph = create_linear_chain(100);
    let changed: thread_utilities::RapidSet<PathBuf> =
        [PathBuf::from("file_99.rs")].into_iter().collect();

    group.bench_function("graph_traversal_100_nodes", |b| {
        b.iter(|| black_box(graph.find_affected_files(black_box(&changed))));
    });

    // Incremental overhead: full change detection pipeline
    let rt = tokio::runtime::Runtime::new().unwrap();
    let storage = InMemoryStorage::new();

    // Prime storage with 100 files
    rt.block_on(async {
        for i in 0..100 {
            let path = PathBuf::from(format!("file_{}.rs", i));
            let content = generate_rust_file(i, "small");
            let fp = AnalysisDefFingerprint::new(content.as_bytes());
            storage.save_fingerprint(&path, &fp).await.unwrap();
        }
    });

    group.bench_function("incremental_overhead_1_change", |b| {
        b.iter(|| {
            rt.block_on(async {
                let path = PathBuf::from("file_50.rs");
                let new_content = generate_rust_file(50, "medium");
                let old_fp = storage.load_fingerprint(&path).await.unwrap();
                let changed = match old_fp {
                    Some(old) => !old.content_matches(new_content.as_bytes()),
                    None => true,
                };

                black_box(changed)
            })
        });
    });

    // Target validation: <10ms overhead
    println!("\n[Constitutional Validation] Target: <10ms incremental overhead");

    group.finish();
}

// ============================================================================
// Benchmark Group 2: Graph Traversal
// ============================================================================

fn benchmark_graph_traversal(c: &mut Criterion) {
    let mut group = c.benchmark_group("graph_traversal");

    // BFS traversal with different graph sizes
    for size in [100, 500, 1000].iter() {
        let graph = create_linear_chain(*size);
        let changed: thread_utilities::RapidSet<PathBuf> =
            [PathBuf::from(format!("file_{}.rs", size - 1))]
                .into_iter()
                .collect();

        group.bench_with_input(BenchmarkId::new("bfs_linear_chain", size), size, |b, _| {
            b.iter(|| black_box(graph.find_affected_files(black_box(&changed))));
        });
    }

    // Affected file calculation (diamond pattern)
    let diamond = create_diamond_pattern();
    let changed: thread_utilities::RapidSet<PathBuf> =
        [PathBuf::from("file_3.rs")].into_iter().collect();

    group.bench_function("affected_files_diamond", |b| {
        b.iter(|| black_box(diamond.find_affected_files(black_box(&changed))));
    });

    // Wide fanout pattern (1 root -> N children)
    for fanout in [10, 50, 100].iter() {
        let mut graph = DependencyGraph::new();
        let root = PathBuf::from("root.rs");

        for i in 0..*fanout {
            let child = PathBuf::from(format!("child_{}.rs", i));
            graph.add_edge(DependencyEdge::new(
                child.clone(),
                root.clone(),
                DependencyType::Import,
            ));
        }

        let changed: thread_utilities::RapidSet<PathBuf> = [root.clone()].into_iter().collect();

        group.bench_with_input(BenchmarkId::new("wide_fanout", fanout), fanout, |b, _| {
            b.iter(|| black_box(graph.find_affected_files(black_box(&changed))));
        });
    }

    // Tree structure traversal
    let tree = create_tree_structure(4, 3); // depth=4, fanout=3 = 40 nodes
    let root_changed: thread_utilities::RapidSet<PathBuf> =
        [PathBuf::from("file_0.rs")].into_iter().collect();

    group.bench_function("tree_traversal_depth4_fanout3", |b| {
        b.iter(|| black_box(tree.find_affected_files(black_box(&root_changed))));
    });

    // Target validation: <50ms for 1000 nodes
    println!("\n[Constitutional Validation] Target: <50ms for 1000 nodes");

    group.finish();
}

// ============================================================================
// Benchmark Group 3: Topological Sort
// ============================================================================

fn benchmark_topological_sort(c: &mut Criterion) {
    let mut group = c.benchmark_group("topological_sort");

    // DAG sorting with different sizes
    for size in [10, 50, 100, 500].iter() {
        let graph = create_linear_chain(*size);
        let all_files: thread_utilities::RapidSet<_> = (0..*size)
            .map(|i| PathBuf::from(format!("file_{}.rs", i)))
            .collect();

        group.bench_with_input(BenchmarkId::new("linear_chain", size), size, |b, _| {
            b.iter(|| black_box(graph.topological_sort(black_box(&all_files))));
        });
    }

    // Diamond pattern sorting
    let diamond = create_diamond_pattern();
    let diamond_files: thread_utilities::RapidSet<_> = (0..4)
        .map(|i| PathBuf::from(format!("file_{}.rs", i)))
        .collect();

    group.bench_function("diamond_pattern", |b| {
        b.iter(|| black_box(diamond.topological_sort(black_box(&diamond_files))));
    });

    // Tree structure sorting
    let tree = create_tree_structure(4, 3);
    let tree_files: thread_utilities::RapidSet<_> = tree.nodes.keys().cloned().collect();

    group.bench_function("tree_structure", |b| {
        b.iter(|| black_box(tree.topological_sort(black_box(&tree_files))));
    });

    // Cycle detection overhead (expect error)
    let mut cyclic_graph = DependencyGraph::new();
    cyclic_graph.add_edge(DependencyEdge::new(
        PathBuf::from("a.rs"),
        PathBuf::from("b.rs"),
        DependencyType::Import,
    ));
    cyclic_graph.add_edge(DependencyEdge::new(
        PathBuf::from("b.rs"),
        PathBuf::from("a.rs"),
        DependencyType::Import,
    ));
    let cyclic_files: thread_utilities::RapidSet<PathBuf> =
        [PathBuf::from("a.rs"), PathBuf::from("b.rs")]
            .into_iter()
            .collect();

    group.bench_function("cycle_detection", |b| {
        b.iter(|| {
            let result = cyclic_graph.topological_sort(black_box(&cyclic_files));
            black_box(result.is_err())
        });
    });

    group.finish();
}

// ============================================================================
// Benchmark Group 4: Reanalysis Scenarios
// ============================================================================

fn benchmark_reanalysis(c: &mut Criterion) {
    let mut group = c.benchmark_group("reanalysis");

    // Simulate incremental vs full analysis with different change rates
    let file_count = 100;

    for change_pct in [1, 10, 50].iter() {
        let changed_count = (file_count * change_pct) / 100;

        // Setup: Create graph and storage
        let rt = tokio::runtime::Runtime::new().unwrap();
        let storage = InMemoryStorage::new();
        let graph = create_linear_chain(file_count);

        // Prime storage with all files
        rt.block_on(async {
            for i in 0..file_count {
                let path = PathBuf::from(format!("file_{}.rs", i));
                let content = generate_rust_file(i, "small");
                let fp = AnalysisDefFingerprint::new(content.as_bytes());
                storage.save_fingerprint(&path, &fp).await.unwrap();
            }
        });

        // Incremental: only analyze affected files
        let changed_files: thread_utilities::RapidSet<_> = (0..changed_count)
            .map(|i| PathBuf::from(format!("file_{}.rs", i)))
            .collect();

        group.bench_with_input(
            BenchmarkId::new("incremental_analysis", change_pct),
            change_pct,
            |b, _| {
                b.iter(|| {
                    rt.block_on(async {
                        let affected = graph.find_affected_files(black_box(&changed_files));
                        let sorted = graph.topological_sort(black_box(&affected)).unwrap();

                        for file in sorted {
                            let _fp = storage.load_fingerprint(&file).await.unwrap();
                            // Simulate analysis work
                            black_box(_fp);
                        }
                    })
                });
            },
        );

        // Full: analyze all files regardless of changes
        let all_files: thread_utilities::RapidSet<_> = (0..file_count)
            .map(|i| PathBuf::from(format!("file_{}.rs", i)))
            .collect();

        group.bench_with_input(
            BenchmarkId::new("full_analysis", change_pct),
            change_pct,
            |b, _| {
                b.iter(|| {
                    rt.block_on(async {
                        let sorted = graph.topological_sort(black_box(&all_files)).unwrap();

                        for file in sorted {
                            let _fp = storage.load_fingerprint(&file).await.unwrap();
                            // Simulate analysis work
                            black_box(_fp);
                        }
                    })
                });
            },
        );
    }

    // Speedup measurement
    println!("\n[Performance] Incremental speedup factors calculated above");

    group.finish();
}

// ============================================================================
// Benchmark Group 5: Cache Hit Rate
// ============================================================================

fn benchmark_cache_hit_rate(c: &mut Criterion) {
    let mut group = c.benchmark_group("cache_hit_rate");

    let rt = tokio::runtime::Runtime::new().unwrap();
    let storage = InMemoryStorage::new();

    // Prime cache with 1000 files
    rt.block_on(async {
        for i in 0..1000 {
            let path = PathBuf::from(format!("file_{}.rs", i));
            let content = generate_rust_file(i, "small");
            let fp = AnalysisDefFingerprint::new(content.as_bytes());
            storage.save_fingerprint(&path, &fp).await.unwrap();
        }
    });

    // Scenario 1: 100% cache hit (zero changes)
    group.bench_function("100_percent_hit_rate", |b| {
        b.iter(|| {
            rt.block_on(async {
                let mut hits = 0;
                let mut misses = 0;

                for i in 0..100 {
                    let path = PathBuf::from(format!("file_{}.rs", i));
                    let content = generate_rust_file(i, "small");

                    if let Some(old_fp) = storage.load_fingerprint(&path).await.unwrap() {
                        if old_fp.content_matches(content.as_bytes()) {
                            hits += 1;
                        } else {
                            misses += 1;
                        }
                    } else {
                        misses += 1;
                    }
                }

                black_box((hits, misses))
            })
        });
    });

    // Scenario 2: 90% cache hit (10% changed)
    group.bench_function("90_percent_hit_rate", |b| {
        b.iter(|| {
            rt.block_on(async {
                let mut hits = 0;
                let mut misses = 0;

                for i in 0..100 {
                    let path = PathBuf::from(format!("file_{}.rs", i));
                    let content = if i % 10 == 0 {
                        // 10% modified
                        generate_rust_file(i, "medium")
                    } else {
                        // 90% unchanged
                        generate_rust_file(i, "small")
                    };

                    if let Some(old_fp) = storage.load_fingerprint(&path).await.unwrap() {
                        if old_fp.content_matches(content.as_bytes()) {
                            hits += 1;
                        } else {
                            misses += 1;
                        }
                    } else {
                        misses += 1;
                    }
                }

                black_box((hits, misses))
            })
        });
    });

    // Scenario 3: 50% cache hit (50% changed)
    group.bench_function("50_percent_hit_rate", |b| {
        b.iter(|| {
            rt.block_on(async {
                let mut hits = 0;
                let mut misses = 0;

                for i in 0..100 {
                    let path = PathBuf::from(format!("file_{}.rs", i));
                    let content = if i % 2 == 0 {
                        generate_rust_file(i, "medium")
                    } else {
                        generate_rust_file(i, "small")
                    };

                    if let Some(old_fp) = storage.load_fingerprint(&path).await.unwrap() {
                        if old_fp.content_matches(content.as_bytes()) {
                            hits += 1;
                        } else {
                            misses += 1;
                        }
                    } else {
                        misses += 1;
                    }
                }

                black_box((hits, misses))
            })
        });
    });

    // Identical content detection
    group.bench_function("identical_content_detection", |b| {
        b.iter(|| {
            rt.block_on(async {
                let content = generate_rust_file(0, "small");

                let fp1 = AnalysisDefFingerprint::new(content.as_bytes());

                black_box(fp1.content_matches(content.as_bytes()))
            })
        });
    });

    // Target validation: >90% hit rate
    println!("\n[Constitutional Validation] Target: >90% cache hit rate");

    group.finish();
}

// ============================================================================
// Benchmark Group 6: Executor Comparison (Feature-Gated)
// ============================================================================

#[cfg(feature = "parallel")]
fn benchmark_executor_comparison(c: &mut Criterion) {
    use rayon::prelude::*;

    let mut group = c.benchmark_group("executor_comparison");

    let file_count = 100;
    let files: Vec<_> = (0..file_count)
        .map(|i| {
            (
                PathBuf::from(format!("file_{}.rs", i)),
                generate_rust_file(i, "small"),
            )
        })
        .collect();

    // Sequential baseline
    group.bench_function("sequential_baseline", |b| {
        b.iter(|| {
            for (_path, content) in &files {
                let fp = AnalysisDefFingerprint::new(content.as_bytes());
                black_box(fp);
            }
        });
    });

    // Tokio async
    let rt = tokio::runtime::Runtime::new().unwrap();

    group.bench_function("tokio_async", |b| {
        b.iter(|| {
            rt.block_on(async {
                let mut tasks = Vec::new();

                for (_path, content) in &files {
                    let content = content.clone();
                    tasks.push(tokio::spawn(async move {
                        AnalysisDefFingerprint::new(content.as_bytes())
                    }));
                }

                for task in tasks {
                    black_box(task.await.unwrap());
                }
            });
        });
    });

    // Rayon parallel
    group.bench_function("rayon_parallel", |b| {
        b.iter(|| {
            files.par_iter().for_each(|(_path, content)| {
                let fp = AnalysisDefFingerprint::new(content.as_bytes());
                black_box(fp);
            });
        });
    });

    // Speedup measurements
    println!("\n[Performance] Parallel speedup factors calculated above");

    group.finish();
}

#[cfg(not(feature = "parallel"))]
fn benchmark_executor_comparison(_c: &mut Criterion) {
    // Parallel benchmarks skipped (feature not enabled)
}

// ============================================================================
// Additional Performance Validation Benchmarks
// ============================================================================

fn benchmark_performance_validation(c: &mut Criterion) {
    let mut group = c.benchmark_group("performance_validation");

    // Large graph performance (10000 nodes)
    let large_graph = create_linear_chain(10000);
    let changed: thread_utilities::RapidSet<PathBuf> =
        [PathBuf::from("file_9999.rs")].into_iter().collect();

    group.bench_function("large_graph_10000_nodes", |b| {
        b.iter(|| black_box(large_graph.find_affected_files(black_box(&changed))));
    });

    // Deep chain performance (1000 levels)
    let deep_chain = create_linear_chain(1000);
    let deep_changed: thread_utilities::RapidSet<PathBuf> =
        [PathBuf::from("file_999.rs")].into_iter().collect();

    group.bench_function("deep_chain_1000_levels", |b| {
        b.iter(|| black_box(deep_chain.find_affected_files(black_box(&deep_changed))));
    });

    // Memory efficiency: batch fingerprint creation
    group.bench_function("batch_fingerprint_1000_files", |b| {
        b.iter(|| {
            let mut fingerprints = Vec::new();
            for i in 0..1000 {
                let content = generate_rust_file(i, "small");
                fingerprints.push(AnalysisDefFingerprint::new(content.as_bytes()));
            }
            black_box(fingerprints)
        });
    });

    group.finish();
}

// ============================================================================
// Criterion Configuration
// ============================================================================

criterion_group!(
    benches,
    benchmark_change_detection,
    benchmark_graph_traversal,
    benchmark_topological_sort,
    benchmark_reanalysis,
    benchmark_cache_hit_rate,
    benchmark_executor_comparison,
    benchmark_performance_validation,
);

criterion_main!(benches);