ryo-executor 0.1.0

//! Conflict Detection for MutationSpecs
//!
//! Provides simple, reliable conflict detection based on MutationTargetSymbol.
//! Used by Executor and Orchestrator for grouping mutations.
//!
//! # Design
//!
//! - **SymbolId/Path-based**: Works with MutationTargetSymbol directly
//! - **Conservative**: Unresolved targets = potential conflict (safe default)
//! - **Global**: Can be used anywhere in executor layer
//!
//! # Functions
//!
//! - `target_conflicts`: Check if two MutationTargetSymbols conflict
//! - `specs_conflict`: Check if two MutationSpecs conflict
//! - `group_by_conflicts`: Partition specs into conflict-free groups

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

/// Check if two MutationTargetSymbols potentially conflict.
///
/// # Rules
///
/// - **ById vs ById**: Compare SymbolId directly
/// - **ByPath vs ByPath**: Compare SymbolPath directly
/// - **ByKindAndName vs ByKindAndName**: Compare Kind + Name
/// - **Mixed variants**: Conservative (return true = potential conflict)
/// - **ByAffectedId**: Compare parent_id + name
///
/// # Conservative Strategy
///
/// When resolution status differs (e.g., ById vs ByPath), we conservatively
/// assume they *might* conflict until both are resolved. This prevents
/// incorrect parallel execution that could corrupt code.
///
/// # Examples
///
/// ```
/// use ryo_executor::executor::target_conflicts;
/// use ryo_executor::MutationTargetSymbol;
/// use ryo_symbol::SymbolId;
///
/// let id1 = SymbolId::parse("1v1").unwrap();
/// let id2 = SymbolId::parse("2v1").unwrap();
///
/// // Same ID = conflict
/// assert!(target_conflicts(
///     &MutationTargetSymbol::ById(id1),
///     &MutationTargetSymbol::ById(id1)
/// ));
///
/// // Different IDs = no conflict
/// assert!(!target_conflicts(
///     &MutationTargetSymbol::ById(id1),
///     &MutationTargetSymbol::ById(id2)
/// ));
/// ```
pub fn target_conflicts(a: &MutationTargetSymbol, b: &MutationTargetSymbol) -> bool {
    match (a, b) {
        // Same SymbolId = definite conflict
        (MutationTargetSymbol::ById(id_a), MutationTargetSymbol::ById(id_b)) => id_a == id_b,

        // Same SymbolPath = definite conflict
        (MutationTargetSymbol::ByPath(path_a), MutationTargetSymbol::ByPath(path_b)) => {
            path_a == path_b
        }

        // Same Kind+Name = definite conflict
        (
            MutationTargetSymbol::ByKindAndName(kind_a, name_a),
            MutationTargetSymbol::ByKindAndName(kind_b, name_b),
        ) => kind_a == kind_b && name_a == name_b,

        // Same parent + name = definite conflict
        (
            MutationTargetSymbol::ByAffectedId {
                parent_id: parent_a,
                name: name_a,
                ..
            },
            MutationTargetSymbol::ByAffectedId {
                parent_id: parent_b,
                name: name_b,
                ..
            },
        ) => parent_a == parent_b && name_a == name_b,

        // Mixed variants: Conservative approach
        // Can't determine without resolution, assume potential conflict
        _ => true,
    }
}

/// Check if two MutationSpecs conflict.
///
/// # Rules
///
/// - Compare target_symbol fields using `target_conflicts`
/// - Specs without target_symbol (project-wide) always conflict
/// - Some variants have additional conflict rules (e.g., MoveItem has source+target)
///
/// # Conservative Defaults
///
/// - Unknown/deprecated variants without target_symbol = always conflict
/// - This ensures safety over performance
///
/// # Examples
///
/// ```
/// use ryo_executor::executor::specs_conflict;
/// use ryo_executor::{MutationSpec, MutationTargetSymbol};
/// use ryo_symbol::SymbolId;
///
/// let id1 = SymbolId::parse("1v1").unwrap();
/// let id2 = SymbolId::parse("2v1").unwrap();
///
/// let spec_a = MutationSpec::AddField {
///     target: MutationTargetSymbol::ById(id1),
///     field_name: "name".into(),
///     field_type: "String".into(),
///     visibility: Default::default(),
/// };
///
/// let spec_b = MutationSpec::AddField {
///     target: MutationTargetSymbol::ById(id2),
///     field_name: "email".into(),
///     field_type: "String".into(),
///     visibility: Default::default(),
/// };
///
/// // Different targets = no conflict
/// assert!(!specs_conflict(&spec_a, &spec_b));
/// ```
pub fn specs_conflict(a: &MutationSpec, b: &MutationSpec) -> bool {
    use MutationSpec::*;

    match (a, b) {
        // === Field operations ===
        // AddField to same struct with DIFFERENT field names = no conflict (parallel safe)
        (
            AddField {
                target: target_a,
                field_name: field_a,
                ..
            },
            AddField {
                target: target_b,
                field_name: field_b,
                ..
            },
        ) => target_conflicts(target_a, target_b) && field_a == field_b,
        // AddField vs RemoveField, or RemoveField vs RemoveField always check target+field
        (
            AddField {
                target: target_a,
                field_name: field_a,
                ..
            },
            RemoveField {
                target: target_b,
                field_name: field_b,
                ..
            },
        )
        | (
            RemoveField {
                target: target_a,
                field_name: field_a,
                ..
            },
            AddField {
                target: target_b,
                field_name: field_b,
                ..
            },
        )
        | (
            RemoveField {
                target: target_a,
                field_name: field_a,
                ..
            },
            RemoveField {
                target: target_b,
                field_name: field_b,
                ..
            },
        ) => target_conflicts(target_a, target_b) && field_a == field_b,

        // === Variant operations ===
        // AddVariant to same enum with DIFFERENT variant names = no conflict
        (
            AddVariant {
                target: target_a,
                variant_name: variant_a,
                ..
            },
            AddVariant {
                target: target_b,
                variant_name: variant_b,
                ..
            },
        ) => target_conflicts(target_a, target_b) && variant_a == variant_b,
        (
            AddVariant {
                target: target_a,
                variant_name: variant_a,
                ..
            },
            RemoveVariant {
                target: target_b,
                variant_name: variant_b,
                ..
            },
        )
        | (
            RemoveVariant {
                target: target_a,
                variant_name: variant_a,
                ..
            },
            AddVariant {
                target: target_b,
                variant_name: variant_b,
                ..
            },
        )
        | (
            RemoveVariant {
                target: target_a,
                variant_name: variant_a,
                ..
            },
            RemoveVariant {
                target: target_b,
                variant_name: variant_b,
                ..
            },
        ) => target_conflicts(target_a, target_b) && variant_a == variant_b,

        // === Method operations ===
        // AddMethod to same impl with DIFFERENT method names = no conflict
        (
            AddMethod {
                target: target_a,
                method_name: method_a,
                ..
            },
            AddMethod {
                target: target_b,
                method_name: method_b,
                ..
            },
        ) => target_conflicts(target_a, target_b) && method_a == method_b,
        (
            AddMethod {
                target: target_a,
                method_name: method_a,
                ..
            },
            RemoveMethod {
                target: target_b,
                method_name: method_b,
                ..
            },
        )
        | (
            RemoveMethod {
                target: target_a,
                method_name: method_a,
                ..
            },
            AddMethod {
                target: target_b,
                method_name: method_b,
                ..
            },
        )
        | (
            RemoveMethod {
                target: target_a,
                method_name: method_a,
                ..
            },
            RemoveMethod {
                target: target_b,
                method_name: method_b,
                ..
            },
        ) => target_conflicts(target_a, target_b) && method_a == method_b,

        // === Module operations ===
        (
            RemoveMod {
                target: target_a, ..
            },
            RemoveMod {
                target: target_b, ..
            },
        )
        | (
            RemoveMod {
                target: target_a, ..
            },
            CreateMod {
                target: target_b, ..
            },
        )
        | (
            CreateMod {
                target: target_a, ..
            },
            RemoveMod {
                target: target_b, ..
            },
        )
        | (
            CreateMod {
                target: target_a, ..
            },
            CreateMod {
                target: target_b, ..
            },
        ) => target_conflicts(target_a, target_b),

        // === Rename operations ===
        (
            Rename {
                target: target_a, ..
            },
            Rename {
                target: target_b, ..
            },
        ) => target_conflicts(target_a, target_b),

        // === Derive operations ===
        (
            AddDerive {
                target: target_a, ..
            },
            AddDerive {
                target: target_b, ..
            },
        )
        | (
            AddDerive {
                target: target_a, ..
            },
            RemoveDerive {
                target: target_b, ..
            },
        )
        | (
            RemoveDerive {
                target: target_a, ..
            },
            AddDerive {
                target: target_b, ..
            },
        )
        | (
            RemoveDerive {
                target: target_a, ..
            },
            RemoveDerive {
                target: target_b, ..
            },
        ) => target_conflicts(target_a, target_b),

        // === Visibility operations ===
        (
            ChangeVisibility {
                target: target_a, ..
            },
            ChangeVisibility {
                target: target_b, ..
            },
        ) => target_conflicts(target_a, target_b),

        // === Remove item operations ===
        (
            RemoveItem {
                target: target_a, ..
            },
            RemoveItem {
                target: target_b, ..
            },
        ) => target_conflicts(target_a, target_b),

        // === Trait operations ===
        (
            ExtractTrait {
                target: target_a, ..
            },
            ExtractTrait {
                target: target_b, ..
            },
        )
        | (
            ExtractTrait {
                target: target_a, ..
            },
            InlineTrait {
                target: target_b, ..
            },
        )
        | (
            InlineTrait {
                target: target_a, ..
            },
            ExtractTrait {
                target: target_b, ..
            },
        )
        | (
            InlineTrait {
                target: target_a, ..
            },
            InlineTrait {
                target: target_b, ..
            },
        ) => target_conflicts(target_a, target_b),

        // === EnumToTrait ===
        (
            EnumToTrait {
                target: target_a, ..
            },
            EnumToTrait {
                target: target_b, ..
            },
        ) => target_conflicts(target_a, target_b),

        // === Duplicate operations ===
        (
            DuplicateFunction {
                target: target_a, ..
            },
            DuplicateFunction {
                target: target_b, ..
            },
        )
        | (
            DuplicateStruct {
                target: target_a, ..
            },
            DuplicateStruct {
                target: target_b, ..
            },
        )
        | (
            DuplicateEnum {
                target: target_a, ..
            },
            DuplicateEnum {
                target: target_b, ..
            },
        )
        | (
            DuplicateModTree {
                target: target_a, ..
            },
            DuplicateModTree {
                target: target_b, ..
            },
        ) => target_conflicts(target_a, target_b),

        // === MoveItem (special: has source + target) ===
        (
            MoveItem {
                source: source_a,
                target: target_a,
                ..
            },
            MoveItem {
                source: source_b,
                target: target_b,
                ..
            },
        ) => {
            // Conflict if either source or target conflicts
            target_conflicts(source_a, source_b) || target_conflicts(target_a, target_b)
        }

        // === Struct literal field operations ===
        (
            AddStructLiteralField {
                target: target_a, ..
            },
            AddStructLiteralField {
                target: target_b, ..
            },
        )
        | (
            AddStructLiteralField {
                target: target_a, ..
            },
            RemoveStructLiteralField {
                target: target_b, ..
            },
        )
        | (
            RemoveStructLiteralField {
                target: target_a, ..
            },
            AddStructLiteralField {
                target: target_b, ..
            },
        )
        | (
            RemoveStructLiteralField {
                target: target_a, ..
            },
            RemoveStructLiteralField {
                target: target_b, ..
            },
        ) => target_conflicts(target_a, target_b),

        // === Cross-variant conflicts ===
        // Operations on same target but different variant types can conflict
        // Example: AddField + RemoveItem on same struct
        (
            AddField {
                target: target_a, ..
            },
            RemoveItem {
                target: target_b, ..
            },
        )
        | (
            RemoveItem {
                target: target_a, ..
            },
            AddField {
                target: target_b, ..
            },
        )
        | (
            AddMethod {
                target: target_a, ..
            },
            RemoveItem {
                target: target_b, ..
            },
        )
        | (
            RemoveItem {
                target: target_a, ..
            },
            AddMethod {
                target: target_b, ..
            },
        )
        | (
            AddVariant {
                target: target_a, ..
            },
            RemoveItem {
                target: target_b, ..
            },
        )
        | (
            RemoveItem {
                target: target_a, ..
            },
            AddVariant {
                target: target_b, ..
            },
        )
        | (
            AddDerive {
                target: target_a, ..
            },
            RemoveItem {
                target: target_b, ..
            },
        )
        | (
            RemoveItem {
                target: target_a, ..
            },
            AddDerive {
                target: target_b, ..
            },
        )
        | (
            ChangeVisibility {
                target: target_a, ..
            },
            RemoveItem {
                target: target_b, ..
            },
        )
        | (
            RemoveItem {
                target: target_a, ..
            },
            ChangeVisibility {
                target: target_b, ..
            },
        )
        | (
            Rename {
                target: target_a, ..
            },
            RemoveItem {
                target: target_b, ..
            },
        )
        | (
            RemoveItem {
                target: target_a, ..
            },
            Rename {
                target: target_b, ..
            },
        ) => target_conflicts(target_a, target_b),

        // === Project-wide operations (no target_symbol) ===
        // These always conflict with each other (conservative)
        (AddItem { .. }, AddItem { .. }) => true, // Module-level, path-based
        (OrganizeImports { .. }, OrganizeImports { .. }) => true,

        // === Idiom operations (module-scoped) ===
        // These have module_id but no specific target_symbol
        // Conflict if same module
        (LoopToIterator { module_id: m_a, .. }, LoopToIterator { module_id: m_b, .. })
        | (UnwrapToQuestion { module_id: m_a, .. }, UnwrapToQuestion { module_id: m_b, .. })
        | (AssignOp { module_id: m_a, .. }, AssignOp { module_id: m_b, .. })
        | (BoolSimplify { module_id: m_a, .. }, BoolSimplify { module_id: m_b, .. })
        | (CloneOnCopy { module_id: m_a, .. }, CloneOnCopy { module_id: m_b, .. })
        | (CollapsibleIf { module_id: m_a, .. }, CollapsibleIf { module_id: m_b, .. })
        | (NoOpArmToTodo { module_id: m_a, .. }, NoOpArmToTodo { module_id: m_b, .. })
        | (ComparisonToMethod { module_id: m_a, .. }, ComparisonToMethod { module_id: m_b, .. })
        | (RedundantClosure { module_id: m_a, .. }, RedundantClosure { module_id: m_b, .. })
        | (IntroduceVariable { module_id: m_a, .. }, IntroduceVariable { module_id: m_b, .. })
        | (ManualMap { module_id: m_a, .. }, ManualMap { module_id: m_b, .. })
        | (MatchToIfLet { module_id: m_a, .. }, MatchToIfLet { module_id: m_b, .. })
        | (FilterNext { module_id: m_a, .. }, FilterNext { module_id: m_b, .. })
        | (MapUnwrapOr { module_id: m_a, .. }, MapUnwrapOr { module_id: m_b, .. }) => m_a == m_b,

        // === Statement operations (function-scoped) ===
        // ReplaceExpr, RemoveStatement, ReplaceStatement have Option<SymbolId> fn_id
        (
            ReplaceExpr {
                fn_id: f_a,
                module_id: m_a,
                ..
            },
            ReplaceExpr {
                fn_id: f_b,
                module_id: m_b,
                ..
            },
        )
        | (
            RemoveStatement {
                fn_id: f_a,
                module_id: m_a,
                ..
            },
            RemoveStatement {
                fn_id: f_b,
                module_id: m_b,
                ..
            },
        )
        | (
            ReplaceStatement {
                fn_id: f_a,
                module_id: m_a,
                ..
            },
            ReplaceStatement {
                fn_id: f_b,
                module_id: m_b,
                ..
            },
        ) => {
            // Conflict if same function or both target same module (None = all functions)
            (f_a.is_some() && f_a == f_b) || (f_a.is_none() && f_b.is_none() && m_a == m_b)
        }

        // InsertStatement has non-optional fn_id
        (InsertStatement { fn_id: f_a, .. }, InsertStatement { fn_id: f_b, .. }) => f_a == f_b,

        // === Match arm operations (function-scoped) ===
        (AddMatchArm { target: t_a, .. }, AddMatchArm { target: t_b, .. })
        | (RemoveMatchArm { target: t_a, .. }, RemoveMatchArm { target: t_b, .. })
        | (ReplaceMatchArm { target: t_a, .. }, ReplaceMatchArm { target: t_b, .. }) => t_a == t_b,

        // === Type operations ===
        (ReplaceType { .. }, ReplaceType { .. }) => true, // Project-wide

        // === Spec operations ===
        (AddSpec { .. }, AddSpec { .. }) => true, // Project-wide

        // === Plugin operations ===
        (PluginTransform { .. }, PluginTransform { .. }) => true, // Project-wide

        // === Additional cross-variant conflicts ===
        // Same target operations of different types (e.g., AddDerive + ChangeVisibility)
        (
            AddField {
                target: target_a, ..
            },
            AddDerive {
                target: target_b, ..
            },
        )
        | (
            AddField {
                target: target_a, ..
            },
            RemoveDerive {
                target: target_b, ..
            },
        )
        | (
            AddField {
                target: target_a, ..
            },
            ChangeVisibility {
                target: target_b, ..
            },
        )
        | (
            AddField {
                target: target_a, ..
            },
            Rename {
                target: target_b, ..
            },
        )
        | (
            RemoveField {
                target: target_a, ..
            },
            AddDerive {
                target: target_b, ..
            },
        )
        | (
            RemoveField {
                target: target_a, ..
            },
            RemoveDerive {
                target: target_b, ..
            },
        )
        | (
            RemoveField {
                target: target_a, ..
            },
            ChangeVisibility {
                target: target_b, ..
            },
        )
        | (
            RemoveField {
                target: target_a, ..
            },
            Rename {
                target: target_b, ..
            },
        )
        | (
            AddVariant {
                target: target_a, ..
            },
            AddDerive {
                target: target_b, ..
            },
        )
        | (
            AddVariant {
                target: target_a, ..
            },
            RemoveDerive {
                target: target_b, ..
            },
        )
        | (
            AddVariant {
                target: target_a, ..
            },
            ChangeVisibility {
                target: target_b, ..
            },
        )
        | (
            AddVariant {
                target: target_a, ..
            },
            Rename {
                target: target_b, ..
            },
        )
        | (
            RemoveVariant {
                target: target_a, ..
            },
            AddDerive {
                target: target_b, ..
            },
        )
        | (
            RemoveVariant {
                target: target_a, ..
            },
            RemoveDerive {
                target: target_b, ..
            },
        )
        | (
            RemoveVariant {
                target: target_a, ..
            },
            ChangeVisibility {
                target: target_b, ..
            },
        )
        | (
            RemoveVariant {
                target: target_a, ..
            },
            Rename {
                target: target_b, ..
            },
        )
        | (
            AddMethod {
                target: target_a, ..
            },
            AddDerive {
                target: target_b, ..
            },
        )
        | (
            AddMethod {
                target: target_a, ..
            },
            RemoveDerive {
                target: target_b, ..
            },
        )
        | (
            AddMethod {
                target: target_a, ..
            },
            ChangeVisibility {
                target: target_b, ..
            },
        )
        | (
            AddMethod {
                target: target_a, ..
            },
            Rename {
                target: target_b, ..
            },
        )
        | (
            RemoveMethod {
                target: target_a, ..
            },
            AddDerive {
                target: target_b, ..
            },
        )
        | (
            RemoveMethod {
                target: target_a, ..
            },
            RemoveDerive {
                target: target_b, ..
            },
        )
        | (
            RemoveMethod {
                target: target_a, ..
            },
            ChangeVisibility {
                target: target_b, ..
            },
        )
        | (
            RemoveMethod {
                target: target_a, ..
            },
            Rename {
                target: target_b, ..
            },
        )
        | (
            AddDerive {
                target: target_a, ..
            },
            ChangeVisibility {
                target: target_b, ..
            },
        )
        | (
            AddDerive {
                target: target_a, ..
            },
            Rename {
                target: target_b, ..
            },
        )
        | (
            RemoveDerive {
                target: target_a, ..
            },
            ChangeVisibility {
                target: target_b, ..
            },
        )
        | (
            RemoveDerive {
                target: target_a, ..
            },
            Rename {
                target: target_b, ..
            },
        )
        | (
            ChangeVisibility {
                target: target_a, ..
            },
            AddDerive {
                target: target_b, ..
            },
        )
        | (
            ChangeVisibility {
                target: target_a, ..
            },
            RemoveDerive {
                target: target_b, ..
            },
        )
        | (
            ChangeVisibility {
                target: target_a, ..
            },
            Rename {
                target: target_b, ..
            },
        )
        | (
            Rename {
                target: target_a, ..
            },
            AddField {
                target: target_b, ..
            },
        )
        | (
            Rename {
                target: target_a, ..
            },
            RemoveField {
                target: target_b, ..
            },
        )
        | (
            Rename {
                target: target_a, ..
            },
            AddVariant {
                target: target_b, ..
            },
        )
        | (
            Rename {
                target: target_a, ..
            },
            RemoveVariant {
                target: target_b, ..
            },
        )
        | (
            Rename {
                target: target_a, ..
            },
            AddMethod {
                target: target_b, ..
            },
        )
        | (
            Rename {
                target: target_a, ..
            },
            RemoveMethod {
                target: target_b, ..
            },
        )
        | (
            Rename {
                target: target_a, ..
            },
            AddDerive {
                target: target_b, ..
            },
        )
        | (
            Rename {
                target: target_a, ..
            },
            RemoveDerive {
                target: target_b, ..
            },
        )
        | (
            Rename {
                target: target_a, ..
            },
            ChangeVisibility {
                target: target_b, ..
            },
        ) => target_conflicts(target_a, target_b),

        // === Different variant types = no conflict by default ===
        // Exception: Already handled above
        _ => false,
    }
}

/// Find all conflicting spec pairs in a list.
///
/// Returns pairs of indices (i, j) where specs[i] conflicts with specs[j].
///
/// # Examples
///
/// ```
/// use ryo_executor::executor::find_conflicting_pairs;
/// use ryo_executor::{MutationSpec, MutationTargetSymbol};
/// use ryo_symbol::SymbolId;
///
/// let id1 = SymbolId::parse("1v1").unwrap();
///
/// let specs = vec![
///     MutationSpec::AddField {
///         target: MutationTargetSymbol::ById(id1),
///         field_name: "name".into(),
///         field_type: "String".into(),
///         visibility: Default::default(),
///     },
///     MutationSpec::AddField {
///         target: MutationTargetSymbol::ById(id1),
///         field_name: "name".into(),  // Same field name = conflict
///         field_type: "i32".into(),
///         visibility: Default::default(),
///     },
/// ];
///
/// let conflicts = find_conflicting_pairs(&specs);
/// // specs[0] and specs[1] conflict (same target AND same field name)
/// assert_eq!(conflicts, vec![(0, 1)]);
/// ```
pub fn find_conflicting_pairs(specs: &[MutationSpec]) -> Vec<(usize, usize)> {
    let mut conflicts = Vec::new();
    for i in 0..specs.len() {
        for j in (i + 1)..specs.len() {
            if specs_conflict(&specs[i], &specs[j]) {
                conflicts.push((i, j));
            }
        }
    }
    conflicts
}

/// Partition specs into conflict-free groups using Union-Find.
///
/// Specs in the same group may conflict with each other.
/// Specs in different groups are guaranteed to be independent.
///
/// # Algorithm
///
/// Uses Union-Find to efficiently group specs that transitively conflict:
/// - If A conflicts with B, and B conflicts with C, then A, B, C are in same group
/// - Groups can be executed sequentially, while different groups can run in parallel
///
/// # Returns
///
/// Vector of groups, where each group is a vector of spec indices.
///
/// # Examples
///
/// ```
/// use ryo_executor::executor::group_by_conflicts;
/// use ryo_executor::{MutationSpec, MutationTargetSymbol};
/// use ryo_symbol::SymbolId;
///
/// let id1 = SymbolId::parse("1v1").unwrap();
/// let id2 = SymbolId::parse("2v1").unwrap();
///
/// let specs = vec![
///     MutationSpec::AddField {
///         target: MutationTargetSymbol::ById(id1),
///         field_name: "name".into(),
///         field_type: "String".into(),
///         visibility: Default::default(),
///     },
///     MutationSpec::AddField {
///         target: MutationTargetSymbol::ById(id2),
///         field_name: "email".into(),
///         field_type: "String".into(),
///         visibility: Default::default(),
///     },
/// ];
///
/// let groups = group_by_conflicts(&specs);
/// // Two independent groups (different targets)
/// assert_eq!(groups.len(), 2);
/// ```
pub fn group_by_conflicts(specs: &[MutationSpec]) -> Vec<Vec<usize>> {
    if specs.is_empty() {
        return vec![];
    }

    // Union-Find structure
    let mut parent: Vec<usize> = (0..specs.len()).collect();
    let mut rank: Vec<usize> = vec![0; specs.len()];

    fn find(parent: &mut [usize], i: usize) -> usize {
        if parent[i] != i {
            parent[i] = find(parent, parent[i]); // Path compression
        }
        parent[i]
    }

    fn union(parent: &mut [usize], rank: &mut [usize], i: usize, j: usize) {
        let root_i = find(parent, i);
        let root_j = find(parent, j);
        if root_i != root_j {
            // Union by rank
            if rank[root_i] < rank[root_j] {
                parent[root_i] = root_j;
            } else if rank[root_i] > rank[root_j] {
                parent[root_j] = root_i;
            } else {
                parent[root_j] = root_i;
                rank[root_i] += 1;
            }
        }
    }

    // Union specs that conflict
    for i in 0..specs.len() {
        for j in (i + 1)..specs.len() {
            if specs_conflict(&specs[i], &specs[j]) {
                union(&mut parent, &mut rank, i, j);
            }
        }
    }

    // Group by root
    let mut groups: HashMap<usize, Vec<usize>> = HashMap::new();
    for i in 0..specs.len() {
        let root = find(&mut parent, i);
        groups.entry(root).or_default().push(i);
    }

    groups.into_values().collect()
}

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

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

    #[test]
    fn test_target_conflicts_same_id() {
        let id1 = dummy_id(1);
        let target_a = MutationTargetSymbol::ById(id1);
        let target_b = MutationTargetSymbol::ById(id1);

        assert!(target_conflicts(&target_a, &target_b));
    }

    #[test]
    fn test_target_conflicts_different_ids() {
        let id1 = dummy_id(1);
        let id2 = dummy_id(2);
        let target_a = MutationTargetSymbol::ById(id1);
        let target_b = MutationTargetSymbol::ById(id2);

        assert!(!target_conflicts(&target_a, &target_b));
    }

    #[test]
    fn test_specs_conflict_same_target_same_field() {
        let id1 = dummy_id(1);
        let spec_a = MutationSpec::AddField {
            target: MutationTargetSymbol::ById(id1),
            field_name: "name".into(),
            field_type: "String".into(),
            visibility: Default::default(),
        };
        let spec_b = MutationSpec::AddField {
            target: MutationTargetSymbol::ById(id1),
            field_name: "name".into(), // Same field name = conflict
            field_type: "String".into(),
            visibility: Default::default(),
        };

        assert!(specs_conflict(&spec_a, &spec_b));
    }

    #[test]
    fn test_specs_no_conflict_same_target_different_fields() {
        let id1 = dummy_id(1);
        let spec_a = MutationSpec::AddField {
            target: MutationTargetSymbol::ById(id1),
            field_name: "name".into(),
            field_type: "String".into(),
            visibility: Default::default(),
        };
        let spec_b = MutationSpec::AddField {
            target: MutationTargetSymbol::ById(id1),
            field_name: "email".into(), // Different field name = no conflict
            field_type: "String".into(),
            visibility: Default::default(),
        };

        assert!(!specs_conflict(&spec_a, &spec_b));
    }

    #[test]
    fn test_specs_conflict_different_targets() {
        let id1 = dummy_id(1);
        let id2 = dummy_id(2);
        let spec_a = MutationSpec::AddField {
            target: MutationTargetSymbol::ById(id1),
            field_name: "name".into(),
            field_type: "String".into(),
            visibility: Default::default(),
        };
        let spec_b = MutationSpec::AddField {
            target: MutationTargetSymbol::ById(id2),
            field_name: "email".into(),
            field_type: "String".into(),
            visibility: Default::default(),
        };

        assert!(!specs_conflict(&spec_a, &spec_b));
    }

    #[test]
    fn test_group_by_conflicts_independent() {
        let id1 = dummy_id(1);
        let id2 = dummy_id(2);

        let specs = vec![
            MutationSpec::AddField {
                target: MutationTargetSymbol::ById(id1),
                field_name: "name".into(),
                field_type: "String".into(),
                visibility: Default::default(),
            },
            MutationSpec::AddField {
                target: MutationTargetSymbol::ById(id2),
                field_name: "email".into(),
                field_type: "String".into(),
                visibility: Default::default(),
            },
        ];

        let groups = group_by_conflicts(&specs);
        assert_eq!(groups.len(), 2); // Two independent groups
    }

    #[test]
    fn test_group_by_conflicts_conflicting() {
        let id1 = dummy_id(1);

        let specs = vec![
            MutationSpec::AddField {
                target: MutationTargetSymbol::ById(id1),
                field_name: "name".into(),
                field_type: "String".into(),
                visibility: Default::default(),
            },
            MutationSpec::AddField {
                target: MutationTargetSymbol::ById(id1),
                field_name: "name".into(), // Same field name = conflict
                field_type: "i32".into(),
                visibility: Default::default(),
            },
        ];

        let groups = group_by_conflicts(&specs);
        assert_eq!(groups.len(), 1); // One group (both conflict)
        assert_eq!(groups[0].len(), 2);
    }

    #[test]
    fn test_cross_variant_conflict() {
        let id1 = dummy_id(1);

        let spec_add = MutationSpec::AddField {
            target: MutationTargetSymbol::ById(id1),
            field_name: "name".into(),
            field_type: "String".into(),
            visibility: Default::default(),
        };

        let spec_remove = MutationSpec::RemoveItem {
            target: MutationTargetSymbol::ById(id1),
            item_kind: ryo_source::ItemKind::Struct,
        };

        // AddField + RemoveItem on same target should conflict
        assert!(specs_conflict(&spec_add, &spec_remove));
    }
}