derive_defs/

resolver.rs

//! Definition resolver with inheritance support.
//!
//! This module handles resolving `extends` relationships between definitions,
//! including cycle detection and merging of traits and attributes.
//!
//! # Resolution Algorithm
//!
//! Uses topological sort (Kahn's algorithm) for:
//! 1. Cycle detection
//! 2. Deterministic resolution order (parents before children)
//! 3. Efficient O(V + E) complexity
//!
//! # Example
//!
//! ```toml
//! [defs.base]
//! traits = ["Debug", "Clone"]
//!
//! [defs.child]
//! extends = "base"
//! traits = ["PartialEq", "Clone"]  # Clone will be deduplicated
//! ```
//!
//! After resolution, `child` will have traits: `["Debug", "Clone", "PartialEq"]`

use std::collections::{HashMap, HashSet, VecDeque};

use crate::parser::{Config, Def};
use crate::validation;
use crate::{Error, Result};

/// A fully resolved definition with all inheritance applied.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ResolvedDef {
    /// The name of the definition.
    pub name: String,

    /// List of derive traits (including inherited).
    pub traits: Vec<String>,

    /// Additional attributes (including inherited).
    pub attrs: Vec<String>,
}

/// Resolved configuration with all definitions fully expanded.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ResolvedConfig {
    /// All resolved definitions.
    pub defs: HashMap<String, ResolvedDef>,
}

/// Resolve all definitions using topological sort.
///
/// # Algorithm
///
/// 1. Build dependency graph (def -> parent)
/// 2. Calculate in-degrees
/// 3. Kahn's algorithm for topological sort
/// 4. If nodes remain → cycle detected
/// 5. Resolve in topological order
///
/// # Errors
///
/// Returns an error if:
/// - A circular dependency is detected
/// - A parent definition does not exist
///
/// # Example
///
/// ```
/// use derive_defs::parser;
/// use derive_defs::resolver;
///
/// let toml = r#"
/// [defs.base]
/// traits = ["Debug", "Clone"]
///
/// [defs.child]
/// extends = "base"
/// traits = ["PartialEq"]
/// "#;
///
/// let config = parser::parse(toml).unwrap();
/// let resolved = resolver::resolve(&config).unwrap();
///
/// let child = resolved.defs.get("child").unwrap();
/// assert_eq!(child.traits, vec!["Debug", "Clone", "PartialEq"]);
/// ```
/// # Panics
///
/// Panics if the internal graph structure is corrupted (should never happen).
pub fn resolve(config: &Config) -> Result<ResolvedConfig> {
    let defs = &config.defs;

    // Validate all parents exist before building graph
    for (name, def) in defs {
        if let Some(ref parent) = def.extends
            && !defs.contains_key(parent)
        {
            return Err(Error::UndefinedParent {
                def: name.clone(),
                parent: parent.clone(),
            });
        }
    }

    // Build adjacency list: parent -> [children]
    let mut graph: HashMap<&str, Vec<&str>> = HashMap::new();
    let mut in_degree: HashMap<&str, usize> = HashMap::new();

    for name in defs.keys() {
        in_degree.insert(name, 0);
    }

    for (name, def) in defs {
        if let Some(ref parent) = def.extends {
            graph.entry(parent).or_default().push(name);
            *in_degree.entry(name).or_insert(0) += 1;
        }
    }

    // Kahn's algorithm
    let mut queue: VecDeque<&str> = in_degree
        .iter()
        .filter(|(_, deg)| **deg == 0)
        .map(|(name, _)| *name)
        .collect();

    let mut topo_order: Vec<&str> = Vec::with_capacity(defs.len());

    while let Some(node) = queue.pop_front() {
        topo_order.push(node);

        if let Some(children) = graph.get(node) {
            for &child in children {
                let deg = in_degree.get_mut(child).unwrap();
                *deg -= 1;
                if *deg == 0 {
                    queue.push_back(child);
                }
            }
        }
    }

    // Check for cycles
    if topo_order.len() != defs.len() {
        let remaining: Vec<_> = in_degree
            .keys()
            .filter(|&&name| !topo_order.contains(&name))
            .copied()
            .collect();
        return Err(Error::CircularDependency(format_cycle(&remaining, defs)));
    }

    // Resolve in topological order
    let mut resolved = HashMap::with_capacity(defs.len());

    for name in topo_order {
        let def = defs.get(name).unwrap();
        let resolved_def = resolve_single(name, def, defs, &resolved)?;
        resolved.insert(name.to_string(), resolved_def);
    }

    Ok(ResolvedConfig { defs: resolved })
}

/// Resolve a single definition by merging with parent.
fn resolve_single(
    name: &str,
    def: &Def,
    _defs: &HashMap<String, Def>,
    resolved: &HashMap<String, ResolvedDef>,
) -> Result<ResolvedDef> {
    let (traits, attrs) = if let Some(ref parent_name) = def.extends {
        let parent = resolved
            .get(parent_name)
            .ok_or_else(|| Error::Validation(format!("parent '{parent_name}' not resolved")))?;

        (
            merge_unique(&parent.traits, &def.traits),
            merge_unique(&parent.attrs, &def.attrs),
        )
    } else {
        (def.traits.clone(), def.attrs.clone())
    };

    // Validate trait names
    validation::validate_trait_names(&traits)?;

    Ok(ResolvedDef {
        name: name.to_string(),
        traits,
        attrs,
    })
}

/// Merge two slices, keeping unique items with parent items first.
fn merge_unique(parent: &[String], child: &[String]) -> Vec<String> {
    let mut seen = HashSet::with_capacity(parent.len() + child.len());
    let mut result = Vec::with_capacity(parent.len() + child.len());

    for item in parent.iter().chain(child.iter()) {
        if seen.insert(item.clone()) {
            result.push(item.clone());
        }
    }

    result
}

/// Format cycle for error message.
fn format_cycle(nodes: &[&str], _defs: &HashMap<String, Def>) -> String {
    if nodes.is_empty() {
        return "unknown".to_string();
    }

    // For now, just list involved nodes
    // A full cycle reconstruction would require more complex graph traversal
    nodes.join(" → ")
}

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

    #[test]
    fn test_resolve_basic() {
        let toml = r#"
[defs.base]
traits = ["Debug", "Clone"]

[defs.child]
extends = "base"
traits = ["PartialEq"]
"#;

        let config = parser::parse(toml).unwrap();
        let resolved = resolve(&config).unwrap();

        let child = resolved.defs.get("child").unwrap();
        assert_eq!(child.traits, vec!["Debug", "Clone", "PartialEq"]);
    }

    #[test]
    fn test_resolve_chain() {
        let toml = r#"
[defs.a]
traits = ["Debug"]

[defs.b]
extends = "a"
traits = ["Clone"]

[defs.c]
extends = "b"
traits = ["PartialEq"]
"#;

        let config = parser::parse(toml).unwrap();
        let resolved = resolve(&config).unwrap();

        let c = resolved.defs.get("c").unwrap();
        assert_eq!(c.traits, vec!["Debug", "Clone", "PartialEq"]);
    }

    #[test]
    fn test_resolve_diamond() {
        // Diamond inheritance pattern
        let toml = r#"
[defs.base]
traits = ["Debug"]

[defs.left]
extends = "base"
traits = ["Clone"]

[defs.right]
extends = "base"
traits = ["PartialEq"]

[defs.bottom]
extends = "left"
traits = ["Hash"]
"#;

        let config = parser::parse(toml).unwrap();
        let resolved = resolve(&config).unwrap();

        let bottom = resolved.defs.get("bottom").unwrap();
        // Should have: Debug (from base), Clone (from left), Hash (from bottom)
        assert_eq!(bottom.traits, vec!["Debug", "Clone", "Hash"]);
    }

    #[test]
    fn test_resolve_circular() {
        let toml = r#"
[defs.a]
extends = "b"
traits = ["Debug"]

[defs.b]
extends = "c"
traits = ["Clone"]

[defs.c]
extends = "a"
traits = ["PartialEq"]
"#;

        let config = parser::parse(toml).unwrap();
        let result = resolve(&config);

        assert!(result.is_err());
        let err = result.unwrap_err().to_string();
        assert!(err.contains("circular"));
    }

    #[test]
    fn test_resolve_self_reference() {
        let toml = r#"
[defs.a]
extends = "a"
traits = ["Debug"]
"#;

        let config = parser::parse(toml).unwrap();
        let result = resolve(&config);

        assert!(result.is_err());
        let err = result.unwrap_err().to_string();
        assert!(err.contains("circular"));
    }

    #[test]
    fn test_resolve_undefined_parent() {
        let toml = r#"
[defs.child]
extends = "nonexistent"
traits = ["Debug"]
"#;

        let config = parser::parse(toml).unwrap();
        let result = resolve(&config);

        assert!(result.is_err());
        let err = result.unwrap_err().to_string();
        assert!(err.contains("nonexistent"));
    }

    #[test]
    fn test_resolve_deduplication() {
        let toml = r#"
[defs.base]
traits = ["Debug", "Clone"]

[defs.child]
extends = "base"
traits = ["Clone", "PartialEq"]
"#;

        let config = parser::parse(toml).unwrap();
        let resolved = resolve(&config).unwrap();

        let child = resolved.defs.get("child").unwrap();
        // Clone should appear only once
        assert_eq!(child.traits, vec!["Debug", "Clone", "PartialEq"]);
    }

    #[test]
    fn test_resolve_with_attrs() {
        let toml = r#"
[defs.base]
traits = ["Debug"]
attrs = ['#[serde(rename_all = "camelCase")]']

[defs.child]
extends = "base"
traits = ["Clone"]
attrs = ['#[serde(default)]']
"#;

        let config = parser::parse(toml).unwrap();
        let resolved = resolve(&config).unwrap();

        let child = resolved.defs.get("child").unwrap();
        assert_eq!(child.traits, vec!["Debug", "Clone"]);
        assert_eq!(child.attrs.len(), 2);
        assert!(
            child
                .attrs
                .contains(&"#[serde(rename_all = \"camelCase\")]".to_string())
        );
        assert!(child.attrs.contains(&"#[serde(default)]".to_string()));
    }

    #[test]
    fn test_resolve_empty() {
        let config = parser::parse("").unwrap();
        let resolved = resolve(&config).unwrap();
        assert!(resolved.defs.is_empty());
    }

    #[test]
    fn test_resolve_multiple_roots() {
        let toml = r#"
[defs.a]
traits = ["Debug"]

[defs.b]
traits = ["Clone"]

[defs.c]
extends = "a"
traits = ["PartialEq"]
"#;

        let config = parser::parse(toml).unwrap();
        let resolved = resolve(&config).unwrap();

        assert_eq!(resolved.defs.len(), 3);
        assert_eq!(resolved.defs["a"].traits, vec!["Debug"]);
        assert_eq!(resolved.defs["b"].traits, vec!["Clone"]);
        assert_eq!(resolved.defs["c"].traits, vec!["Debug", "PartialEq"]);
    }
}