ryo_executor/executor/

blueprint.rs

//! ParallelBlueprint: Execution plan with dependency graph and conflict detection
//!
//! ```text
//! Vec<MutationSpec> + DependencyGraph → ParallelBlueprint
//!                                            │
//!                    ┌───────────────────────┴───────────────────────┐
//!                    ↓                                               ↓
//!          [conflicts.is_empty()]                         [conflicts detected]
//!                    ↓                                               ↓
//!           Autonomous Execution                      Escalate to High-level LLM
//! ```

use super::conflict;
use super::spec::MutationSpec;
use std::collections::{HashMap, HashSet};

/// Parallel execution blueprint
#[derive(Debug, Clone)]
pub struct ParallelBlueprint {
    /// Mutation specifications to execute
    pub mutations: Vec<MutationSpec>,

    /// Dependency graph for ordering
    pub deps: DependencyGraph,

    /// Conflicts detected at plan time
    pub conflicts: Vec<Conflict>,
}

impl ParallelBlueprint {
    /// Create a new empty blueprint
    pub fn new() -> Self {
        Self {
            mutations: vec![],
            deps: DependencyGraph::new(),
            conflicts: vec![],
        }
    }

    /// Create blueprint from mutations (auto-detects conflicts)
    pub fn from_mutations(mutations: Vec<MutationSpec>) -> Self {
        let mut builder = BlueprintBuilder::new();
        for spec in mutations {
            builder.add(spec);
        }
        builder.build()
    }

    /// Check if escalation to high-level LLM is needed
    pub fn needs_escalation(&self) -> bool {
        !self.conflicts.is_empty()
    }

    /// Get mutations ready to execute (all dependencies satisfied)
    pub fn ready_set(&self, completed: &HashSet<usize>) -> Vec<usize> {
        self.deps.ready_set(self.mutations.len(), completed)
    }

    /// Calculate parallelism factor (1.0 = sequential, N = N parallel tracks)
    pub fn parallelism(&self) -> f64 {
        if self.mutations.is_empty() {
            return 1.0;
        }

        let critical_path = self.deps.critical_path_length(self.mutations.len());
        if critical_path == 0 {
            self.mutations.len() as f64
        } else {
            self.mutations.len() as f64 / critical_path as f64
        }
    }

    /// Get topological levels for parallel execution
    pub fn topological_levels(&self) -> Vec<Vec<usize>> {
        self.deps.topological_levels(self.mutations.len())
    }
}

impl Default for ParallelBlueprint {
    fn default() -> Self {
        Self::new()
    }
}

/// Dependency graph for mutation ordering
#[derive(Debug, Clone, Default)]
pub struct DependencyGraph {
    /// Forward edges: idx → Vec<depends_on_idx>
    edges: HashMap<usize, Vec<usize>>,
}

impl DependencyGraph {
    pub fn new() -> Self {
        Self::default()
    }

    /// Add dependency: `from` depends on `to` (to must complete before from)
    pub fn add_dependency(&mut self, from: usize, to: usize) {
        self.edges.entry(from).or_default().push(to);
    }

    /// Get all dependencies for a mutation
    pub fn dependencies_of(&self, idx: usize) -> &[usize] {
        self.edges.get(&idx).map(|v| v.as_slice()).unwrap_or(&[])
    }

    /// Check if mutation is ready (all dependencies completed)
    pub fn is_ready(&self, idx: usize, completed: &HashSet<usize>) -> bool {
        self.dependencies_of(idx)
            .iter()
            .all(|dep| completed.contains(dep))
    }

    /// Get all mutations ready to execute
    pub fn ready_set(&self, total: usize, completed: &HashSet<usize>) -> Vec<usize> {
        (0..total)
            .filter(|idx| !completed.contains(idx) && self.is_ready(*idx, completed))
            .collect()
    }

    /// Check if there's an ordering between any pair of indices
    pub fn has_ordering(&self, indices: &[usize]) -> bool {
        for &a in indices {
            for &b in indices {
                if a != b && self.depends_on(a, b) {
                    return true;
                }
            }
        }
        false
    }

    /// Check if `a` depends on `b` (directly or transitively)
    pub fn depends_on(&self, a: usize, b: usize) -> bool {
        let mut visited = HashSet::new();
        self.depends_on_recursive(a, b, &mut visited)
    }

    fn depends_on_recursive(&self, a: usize, b: usize, visited: &mut HashSet<usize>) -> bool {
        if visited.contains(&a) {
            return false;
        }
        visited.insert(a);

        for &dep in self.dependencies_of(a) {
            if dep == b || self.depends_on_recursive(dep, b, visited) {
                return true;
            }
        }
        false
    }

    /// Calculate critical path length
    pub fn critical_path_length(&self, total: usize) -> usize {
        let mut memo: HashMap<usize, usize> = HashMap::new();

        fn dfs(idx: usize, graph: &DependencyGraph, memo: &mut HashMap<usize, usize>) -> usize {
            if let Some(&cached) = memo.get(&idx) {
                return cached;
            }

            let max_dep = graph
                .dependencies_of(idx)
                .iter()
                .map(|&dep| dfs(dep, graph, memo))
                .max()
                .unwrap_or(0);

            let length = max_dep + 1;
            memo.insert(idx, length);
            length
        }

        (0..total)
            .map(|idx| dfs(idx, self, &mut memo))
            .max()
            .unwrap_or(0)
    }

    /// Get topological levels (mutations in same level can run in parallel)
    pub fn topological_levels(&self, total: usize) -> Vec<Vec<usize>> {
        let mut levels: Vec<Vec<usize>> = vec![];
        let mut completed: HashSet<usize> = HashSet::new();

        while completed.len() < total {
            let ready = self.ready_set(total, &completed);
            if ready.is_empty() {
                // Cycle detected or all done
                break;
            }

            for &idx in &ready {
                completed.insert(idx);
            }
            levels.push(ready);
        }

        levels
    }
}

/// Conflict detected during blueprint planning
#[derive(Debug, Clone)]
pub struct Conflict {
    /// Type of conflict
    pub kind: ConflictKind,

    /// Indices of involved mutations
    pub involved: Vec<usize>,

    /// Human-readable question for escalation
    pub question: String,
}

/// Types of conflicts
#[derive(Debug, Clone)]
pub enum ConflictKind {
    /// Same target modified by multiple mutations
    SameTarget { target: String },

    /// Order changes semantics
    OrderDependent { reason: String },

    /// One mutation deletes what another references
    DeleteReference {
        deleted: String,
        referenced_by: String,
    },
}

/// Builder for creating ParallelBlueprint
#[derive(Debug, Default)]
pub struct BlueprintBuilder {
    specs: Vec<MutationSpec>,
    deps: DependencyGraph,
}

impl BlueprintBuilder {
    pub fn new() -> Self {
        Self::default()
    }

    /// Add a mutation spec
    pub fn add(&mut self, spec: MutationSpec) -> &mut Self {
        self.specs.push(spec);
        self
    }

    /// Add dependency between mutations
    pub fn add_dependency(&mut self, from: usize, to: usize) -> &mut Self {
        self.deps.add_dependency(from, to);
        self
    }

    /// Build the blueprint with conflict detection
    pub fn build(self) -> ParallelBlueprint {
        let conflicts = detect_conflicts(&self.specs, &self.deps);

        ParallelBlueprint {
            mutations: self.specs,
            deps: self.deps,
            conflicts,
        }
    }
}

/// Detect conflicts in mutation list using conflict::specs_conflict
fn detect_conflicts(specs: &[MutationSpec], deps: &DependencyGraph) -> Vec<Conflict> {
    let mut conflicts = vec![];

    // Use conflict::find_conflicting_pairs for pair-wise conflict detection
    let conflicting_pairs = conflict::find_conflicting_pairs(specs);

    for (i, j) in conflicting_pairs {
        // Skip if dependency ordering exists
        if deps.has_ordering(&[i, j]) {
            continue;
        }

        // Create conflict record
        conflicts.push(Conflict {
            kind: ConflictKind::SameTarget {
                target: format!("spec[{}] vs spec[{}]", i, j),
            },
            involved: vec![i, j],
            question: format!(
                "Specs {} and {} conflict without defined order. Which should be applied first?",
                i, j
            ),
        });
    }

    conflicts
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::executor::spec::{MutationTargetSymbol, Scope};
    use ryo_symbol::SymbolId;

    /// Create a dummy SymbolId for testing
    fn dummy_id(index: u32) -> SymbolId {
        SymbolId::parse(&format!("{}v1", index)).expect("valid dummy id")
    }

    #[test]
    fn test_dependency_graph_ready_set() {
        let mut deps = DependencyGraph::new();
        // 0 depends on nothing
        // 1 depends on 0
        // 2 depends on nothing
        deps.add_dependency(1, 0);

        let completed = HashSet::new();
        let ready = deps.ready_set(3, &completed);
        assert!(ready.contains(&0));
        assert!(!ready.contains(&1)); // depends on 0
        assert!(ready.contains(&2));

        let mut completed = HashSet::new();
        completed.insert(0);
        let ready = deps.ready_set(3, &completed);
        assert!(ready.contains(&1)); // now ready
        assert!(ready.contains(&2));
    }

    #[test]
    fn test_topological_levels() {
        let mut deps = DependencyGraph::new();
        // Level 0: 0, 2
        // Level 1: 1 (depends on 0)
        // Level 2: 3 (depends on 1)
        deps.add_dependency(1, 0);
        deps.add_dependency(3, 1);

        let levels = deps.topological_levels(4);
        assert_eq!(levels.len(), 3);
        assert!(levels[0].contains(&0));
        assert!(levels[0].contains(&2));
        assert!(levels[1].contains(&1));
        assert!(levels[2].contains(&3));
    }

    #[test]
    fn test_same_target_conflict_detection() {
        let specs = vec![
            MutationSpec::ChangeVisibility {
                target: MutationTargetSymbol::ById(dummy_id(1)),
                visibility: crate::executor::spec::Visibility::Pub,
            },
            MutationSpec::AddDerive {
                target: MutationTargetSymbol::ById(dummy_id(1)),
                derives: vec!["Debug".to_string()],
            },
        ];

        let blueprint = ParallelBlueprint::from_mutations(specs);
        // Both target "Config" without ordering - should conflict
        assert!(!blueprint.conflicts.is_empty());
    }

    #[test]
    fn test_rename_chain_conflict() {
        use ryo_symbol::{SymbolKind, SymbolPath, SymbolRegistry};

        // Create dummy symbol IDs for testing
        let mut registry = SymbolRegistry::new();
        let path_a = SymbolPath::parse("test_crate::A").unwrap();
        let symbol_a = registry.register(path_a, SymbolKind::Struct).unwrap();

        let specs = vec![
            MutationSpec::Rename {
                target: MutationTargetSymbol::ById(symbol_a),
                to: "B".to_string(),
                scope: Scope::Project,
            },
            MutationSpec::Rename {
                target: MutationTargetSymbol::ById(symbol_a),
                to: "C".to_string(),
                scope: Scope::Project,
            },
        ];

        let blueprint = ParallelBlueprint::from_mutations(specs);
        // Two renames on same target should conflict
        assert!(
            !blueprint.conflicts.is_empty(),
            "Expected conflict for two renames on same target"
        );
    }

    #[test]
    fn test_no_conflict_with_ordering() {
        use ryo_symbol::{SymbolKind, SymbolPath, SymbolRegistry};

        // Create dummy symbol IDs for testing
        let mut registry = SymbolRegistry::new();
        let path_a = SymbolPath::parse("test_crate::A").unwrap();
        let path_b = SymbolPath::parse("test_crate::B").unwrap();
        let symbol_a = registry.register(path_a, SymbolKind::Struct).unwrap();
        let _symbol_b = registry.register(path_b, SymbolKind::Struct).unwrap();

        let mut builder = BlueprintBuilder::new();
        builder.add(MutationSpec::Rename {
            target: MutationTargetSymbol::ById(symbol_a),
            to: "B".to_string(),
            scope: Scope::Project,
        });
        builder.add(MutationSpec::Rename {
            target: MutationTargetSymbol::ById(symbol_a),
            to: "C".to_string(),
            scope: Scope::Project,
        });
        // Explicit ordering: 1 depends on 0
        builder.add_dependency(1, 0);

        let blueprint = builder.build();
        // With ordering, no conflict
        assert!(blueprint.conflicts.is_empty());
    }

    #[test]
    fn test_delete_reference_conflict() {
        use ryo_source::ItemKind;

        let specs = vec![
            MutationSpec::RemoveItem {
                target: MutationTargetSymbol::ById(dummy_id(1)),
                item_kind: ItemKind::Struct,
            },
            MutationSpec::AddDerive {
                target: MutationTargetSymbol::ById(dummy_id(1)),
                derives: vec!["Debug".to_string()],
            },
        ];

        let blueprint = ParallelBlueprint::from_mutations(specs);
        // RemoveItem + AddDerive on same target should conflict
        assert!(
            !blueprint.conflicts.is_empty(),
            "Expected conflict: RemoveItem + AddDerive on same target"
        );
    }

    #[test]
    fn test_visibility_conflict() {
        use crate::executor::spec::Visibility;

        let specs = vec![
            MutationSpec::ChangeVisibility {
                target: MutationTargetSymbol::ById(dummy_id(1)),
                visibility: Visibility::Pub,
            },
            MutationSpec::ChangeVisibility {
                target: MutationTargetSymbol::ById(dummy_id(1)),
                visibility: Visibility::PubCrate,
            },
        ];

        let blueprint = ParallelBlueprint::from_mutations(specs);
        // Both try to change Config's visibility to different values
        assert!(!blueprint.conflicts.is_empty());
    }

    #[test]
    fn test_visibility_no_conflict_same_value() {
        use crate::executor::spec::Visibility;

        let specs = vec![
            MutationSpec::ChangeVisibility {
                target: MutationTargetSymbol::ById(dummy_id(1)),
                visibility: Visibility::Pub,
            },
            MutationSpec::ChangeVisibility {
                target: MutationTargetSymbol::ById(dummy_id(1)),
                visibility: Visibility::Pub,
            },
        ];

        let blueprint = ParallelBlueprint::from_mutations(specs);
        // Same visibility - no conflict (idempotent)
        let vis_conflicts: Vec<_> = blueprint
            .conflicts
            .iter()
            .filter(|c| {
                matches!(c.kind, ConflictKind::SameTarget { ref target } if target == "Config")
                    && c.question.contains("visibility")
            })
            .collect();
        assert!(vis_conflicts.is_empty());
    }
}