rez-next-solver 0.3.0

//! Search state representation for A* dependency resolution
//!
//! This module defines the SearchState structure that represents a state
//! in the dependency resolution search space, along with utilities for
//! state management and comparison.

use rez_next_package::{Package, PackageRequirement};
use serde::{Deserialize, Serialize};
use std::collections::HashMap;
use std::hash::{Hash, Hasher};

/// Represents a dependency conflict within the A* search
#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq)]
pub struct DependencyConflict {
    /// Name of the conflicting package
    pub package_name: String,

    /// Conflicting requirement strings
    pub conflicting_requirements: Vec<String>,

    /// Severity (0.0 = minor, 1.0 = major)  — serialized as bits
    pub severity_bits: u64,

    /// Type of conflict
    pub conflict_type: ConflictType,
}

impl DependencyConflict {
    pub fn severity(&self) -> f64 {
        f64::from_bits(self.severity_bits)
    }

    pub fn new(
        package_name: String,
        conflicting_requirements: Vec<String>,
        severity: f64,
        conflict_type: ConflictType,
    ) -> Self {
        Self {
            package_name,
            conflicting_requirements,
            severity_bits: severity.to_bits(),
            conflict_type,
        }
    }
}

/// Types of dependency conflicts
#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq, Hash)]
pub enum ConflictType {
    /// Version range conflicts
    VersionConflict,
    /// Circular dependency
    CircularDependency,
    /// Missing package
    MissingPackage,
    /// Platform incompatibility
    PlatformConflict,
}

/// Represents a state in the dependency resolution search space
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct SearchState {
    /// Packages that have been resolved in this state
    pub resolved_packages: HashMap<String, Package>,

    /// Requirements that still need to be resolved (stored as strings for hashing)
    pub pending_requirements: Vec<PackageRequirement>,

    /// Current conflicts in this state
    pub conflicts: Vec<DependencyConflict>,

    /// Actual cost from start state to this state (g(n))
    pub cost_so_far: f64,

    /// Estimated total cost (f(n) = g(n) + h(n))
    pub estimated_total_cost: f64,

    /// Depth in the search tree
    pub depth: usize,

    /// Parent state ID for path reconstruction
    pub parent_id: Option<u64>,

    /// Unique identifier for this state
    pub state_id: u64,

    /// Hash of the state for quick comparison
    state_hash: u64,
}

impl SearchState {
    /// Create a new initial search state
    pub fn new_initial(requirements: Vec<PackageRequirement>) -> Self {
        let mut state = Self {
            resolved_packages: HashMap::new(),
            pending_requirements: requirements,
            conflicts: Vec::new(),
            cost_so_far: 0.0,
            estimated_total_cost: 0.0,
            depth: 0,
            parent_id: None,
            state_id: 0,
            state_hash: 0,
        };

        state.update_hash();
        state.state_id = state.state_hash;
        state
    }

    /// Create a new state from a parent state
    pub fn new_from_parent(
        parent: &SearchState,
        resolved_package: Package,
        new_requirements: Vec<PackageRequirement>,
        additional_cost: f64,
    ) -> Self {
        let mut resolved_packages = parent.resolved_packages.clone();
        resolved_packages.insert(resolved_package.name.clone(), resolved_package);

        let mut pending_requirements = parent.pending_requirements.clone();
        pending_requirements.extend(new_requirements);

        let mut state = Self {
            resolved_packages,
            pending_requirements,
            conflicts: parent.conflicts.clone(),
            cost_so_far: parent.cost_so_far + additional_cost,
            estimated_total_cost: 0.0,
            depth: parent.depth + 1,
            parent_id: Some(parent.state_id),
            state_id: 0,
            state_hash: 0,
        };

        state.update_hash();
        state.state_id = state.state_hash;
        state
    }

    /// Check if this state represents a goal (all requirements resolved)
    pub fn is_goal(&self) -> bool {
        self.pending_requirements.is_empty() && self.conflicts.is_empty()
    }

    /// Check if this state is valid (no unresolvable conflicts)
    pub fn is_valid(&self) -> bool {
        for conflict in &self.conflicts {
            match conflict.conflict_type {
                ConflictType::MissingPackage => return false,
                ConflictType::CircularDependency => return false,
                _ => {}
            }
        }
        true
    }

    /// Get the next requirement to resolve
    pub fn get_next_requirement(&self) -> Option<&PackageRequirement> {
        self.pending_requirements.first()
    }

    /// Add a conflict to this state
    pub fn add_conflict(&mut self, conflict: DependencyConflict) {
        self.conflicts.push(conflict);
        self.update_hash();
    }

    /// Remove a requirement from pending list by name
    pub fn remove_requirement(&mut self, requirement: &PackageRequirement) {
        self.pending_requirements
            .retain(|req| req.name != requirement.name);
        self.update_hash();
    }

    /// Update the state hash for comparison
    fn update_hash(&mut self) {
        use std::collections::hash_map::DefaultHasher;

        let mut hasher = DefaultHasher::new();

        // Hash resolved packages (sorted for determinism)
        let mut package_names: Vec<_> = self.resolved_packages.keys().collect();
        package_names.sort();
        for name in package_names {
            name.hash(&mut hasher);
            if let Some(pkg) = self.resolved_packages.get(name) {
                if let Some(ref ver) = pkg.version {
                    ver.as_str().hash(&mut hasher);
                }
            }
        }

        // Hash pending requirements (sorted for determinism)
        let mut req_strings: Vec<String> = self
            .pending_requirements
            .iter()
            .map(|req| req.to_string())
            .collect();
        req_strings.sort();
        for req_str in &req_strings {
            req_str.hash(&mut hasher);
        }

        // Hash conflicts
        for conflict in &self.conflicts {
            conflict.package_name.hash(&mut hasher);
            conflict.conflict_type.hash(&mut hasher);
        }

        self.state_hash = hasher.finish();
    }

    /// Get state hash for quick comparison
    pub fn get_hash(&self) -> u64 {
        self.state_hash
    }

    /// Calculate the complexity of this state (for algorithm selection)
    pub fn calculate_complexity(&self) -> usize {
        self.resolved_packages.len() + self.pending_requirements.len() + self.conflicts.len() * 2
    }
}

impl PartialEq for SearchState {
    fn eq(&self, other: &Self) -> bool {
        self.state_hash == other.state_hash
    }
}

impl Eq for SearchState {}

impl Hash for SearchState {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.state_hash.hash(state);
    }
}

impl PartialOrd for SearchState {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for SearchState {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        // Consistent with Eq (state_hash-based): used for BinaryHeap closed_set dedup.
        // A* priority ordering is handled by OrdByEstimatedCost wrapper in astar_search.rs.
        self.state_hash.cmp(&other.state_hash)
    }
}

/// Wrapper for use in BinaryHeap that orders SearchStates by estimated_total_cost (A* min-heap).
///
/// `BinaryHeap` is a max-heap in Rust, so we flip the comparison so that the state with the
/// **lowest** `estimated_total_cost` wins (i.e., comparing `other` vs `self`).
///
/// Eq is defined consistently with Ord: two entries are equal iff their cost bits and state_hash
/// are identical, satisfying the `a == b ↔ a.cmp(b) == Equal` contract required by Clippy.
#[derive(Debug)]
pub struct OrdByEstimatedCost(pub SearchState);

impl PartialEq for OrdByEstimatedCost {
    fn eq(&self, other: &Self) -> bool {
        self.0.estimated_total_cost.to_bits() == other.0.estimated_total_cost.to_bits()
            && self.0.state_hash == other.0.state_hash
    }
}

impl Eq for OrdByEstimatedCost {}

impl PartialOrd for OrdByEstimatedCost {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for OrdByEstimatedCost {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        // Use integer bit comparison to avoid f64-related Clippy lints.
        // NaN is handled by treating it as u64::MAX (worst priority).
        // Reversed (other vs self) so that the entry with the lowest cost is
        // popped first from Rust's max-heap BinaryHeap.
        let self_bits = self.0.estimated_total_cost.to_bits();
        let other_bits = other.0.estimated_total_cost.to_bits();
        other_bits
            .cmp(&self_bits)
            .then_with(|| self.0.state_hash.cmp(&other.0.state_hash))
    }
}

/// State pool for memory management
pub struct StatePool {
    pool: Vec<SearchState>,
    max_size: usize,
}

impl StatePool {
    /// Create a new state pool
    pub fn new(max_size: usize) -> Self {
        Self {
            pool: Vec::with_capacity(max_size),
            max_size,
        }
    }

    /// Get a state from the pool or create a new one
    pub fn get_state(&mut self) -> SearchState {
        self.pool
            .pop()
            .unwrap_or_else(|| SearchState::new_initial(Vec::new()))
    }

    /// Return a state to the pool
    pub fn return_state(&mut self, mut state: SearchState) {
        if self.pool.len() < self.max_size {
            state.resolved_packages.clear();
            state.pending_requirements.clear();
            state.conflicts.clear();
            state.cost_so_far = 0.0;
            state.estimated_total_cost = 0.0;
            state.depth = 0;
            state.parent_id = None;
            state.state_id = 0;
            state.state_hash = 0;
            self.pool.push(state);
        }
    }

    /// Get current pool size
    pub fn size(&self) -> usize {
        self.pool.len()
    }
}

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

    fn make_req(name: &str) -> PackageRequirement {
        PackageRequirement::new(name.to_string())
    }

    #[test]
    fn test_search_state_creation() {
        let req = make_req("test_package");
        let state = SearchState::new_initial(vec![req]);
        assert_eq!(state.pending_requirements.len(), 1);
        assert_eq!(state.resolved_packages.len(), 0);
        assert_eq!(state.depth, 0);
        assert!(!state.is_goal());
    }

    #[test]
    fn test_state_hash_consistency() {
        let req = make_req("test_package");
        let state1 = SearchState::new_initial(vec![req.clone()]);
        let state2 = SearchState::new_initial(vec![req]);
        assert_eq!(state1.get_hash(), state2.get_hash());
        assert_eq!(state1, state2);
    }

    #[test]
    fn test_goal_state_empty_requirements() {
        let state = SearchState::new_initial(vec![]);
        assert!(
            state.is_goal(),
            "Empty requirements with no conflicts is a goal"
        );
    }

    #[test]
    fn test_state_validity_missing_package_conflict() {
        let mut state = SearchState::new_initial(vec![]);
        state.add_conflict(DependencyConflict::new(
            "missing_pkg".to_string(),
            vec![],
            1.0,
            ConflictType::MissingPackage,
        ));
        assert!(
            !state.is_valid(),
            "MissingPackage conflict makes state invalid"
        );
    }

    #[test]
    fn test_state_validity_version_conflict_still_valid() {
        let mut state = SearchState::new_initial(vec![]);
        state.add_conflict(DependencyConflict::new(
            "pkg".to_string(),
            vec!["pkg-1.0".to_string(), "pkg-2.0".to_string()],
            0.5,
            ConflictType::VersionConflict,
        ));
        // VersionConflict doesn't make state invalid (resolvable)
        assert!(
            state.is_valid(),
            "VersionConflict alone does not invalidate state"
        );
    }

    #[test]
    fn test_state_pool() {
        let mut pool = StatePool::new(5);
        assert_eq!(pool.size(), 0);

        let state = pool.get_state();
        pool.return_state(state);
        assert_eq!(pool.size(), 1);

        let _state = pool.get_state();
        assert_eq!(pool.size(), 0);
    }

    #[test]
    fn test_state_ordering_lower_cost_higher_priority() {
        let mut s1 = SearchState::new_initial(vec![]);
        s1.estimated_total_cost = 5.0;
        let mut s2 = SearchState::new_initial(vec![make_req("x")]);
        s2.estimated_total_cost = 10.0;
        // OrdByEstimatedCost wraps SearchState so that BinaryHeap pops lowest cost first.
        use std::collections::BinaryHeap;
        let mut heap: BinaryHeap<OrdByEstimatedCost> = BinaryHeap::new();
        heap.push(OrdByEstimatedCost(s1));
        heap.push(OrdByEstimatedCost(s2));
        let top = heap.pop().unwrap().0;
        assert_eq!(
            top.estimated_total_cost, 5.0,
            "Lower cost should have higher priority"
        );
    }

    #[test]
    fn test_remove_requirement() {
        let req1 = make_req("pkg_a");
        let req2 = make_req("pkg_b");
        let mut state = SearchState::new_initial(vec![req1.clone(), req2.clone()]);
        assert_eq!(state.pending_requirements.len(), 2);
        state.remove_requirement(&req1);
        assert_eq!(state.pending_requirements.len(), 1);
        assert_eq!(state.pending_requirements[0].name, "pkg_b");
    }
}