zinit 0.3.7

//! Service dependency graph management using petgraph.

use std::collections::{HashMap, HashSet};
use std::fs;
use std::path::Path;
use std::time::{SystemTime, UNIX_EPOCH};

use petgraph::Direction;
use petgraph::algo::{is_cyclic_directed, toposort};
use petgraph::graph::{DiGraph, NodeIndex};
use petgraph::visit::EdgeRef;

use crate::sdk::{
    DepType, DependencyDef, ReloadResult, ServiceConfig, ServiceState, TargetConfig, validate,
};

use super::error::{BlockedReason, GraphError, GraphResult};

/// Get current time in milliseconds since epoch.
fn now_millis() -> u64 {
    SystemTime::now()
        .duration_since(UNIX_EPOCH)
        .unwrap_or_default()
        .as_millis() as u64
}

/// Unique identifier for a service in the graph.
pub type ServiceId = NodeIndex;

/// A service or target in the dependency graph.
#[derive(Debug, Clone)]
pub struct Service {
    pub name: String,
    pub config: ServiceConfigKind,
    pub state: ServiceState,
    /// Number of restart attempts since last successful run.
    pub restart_count: u32,
    /// Current restart delay in milliseconds (for exponential backoff).
    pub current_restart_delay_ms: u64,
    /// Timestamp when service was last started (unix millis).
    pub started_at: Option<u64>,
    /// Timestamp of last state change (unix millis).
    pub last_state_change: u64,
    /// Last exit code if the service exited.
    pub last_exit_code: Option<i32>,
    /// Last signal that killed the service.
    pub last_exit_signal: Option<i32>,
    /// Whether this service was added at runtime (not from disk config).
    pub ephemeral: bool,
}

/// The kind of service configuration.
#[derive(Debug, Clone)]
#[allow(clippy::large_enum_variant)]
pub enum ServiceConfigKind {
    Service(ServiceConfig),
    Target(TargetConfig),
}

impl Service {
    /// Create a new service from a service config.
    pub fn from_service(config: ServiceConfig) -> Self {
        let initial_delay = config.lifecycle.restart_delay_ms;
        Self {
            name: config.service.name.clone(),
            config: ServiceConfigKind::Service(config),
            state: ServiceState::Inactive,
            restart_count: 0,
            current_restart_delay_ms: initial_delay,
            started_at: None,
            last_state_change: now_millis(),
            last_exit_code: None,
            last_exit_signal: None,
            ephemeral: false,
        }
    }

    /// Create a new service from a service config (marked as ephemeral).
    pub fn from_service_ephemeral(config: ServiceConfig) -> Self {
        let mut service = Self::from_service(config);
        service.ephemeral = true;
        service
    }

    /// Create a new target service.
    pub fn from_target(config: TargetConfig) -> Self {
        Self {
            name: config.target.name.clone(),
            config: ServiceConfigKind::Target(config),
            state: ServiceState::Inactive,
            restart_count: 0,
            current_restart_delay_ms: 0, // Targets don't restart
            started_at: None,
            last_state_change: now_millis(),
            last_exit_code: None,
            last_exit_signal: None,
            ephemeral: false,
        }
    }

    /// Update the last state change timestamp.
    pub fn touch_state_change(&mut self) {
        self.last_state_change = now_millis();
    }

    /// Record service started.
    pub fn record_started(&mut self) {
        self.started_at = Some(now_millis());
        self.touch_state_change();
    }

    /// Record service exit.
    pub fn record_exit(&mut self, exit_code: Option<i32>, signal: Option<i32>) {
        self.last_exit_code = exit_code;
        self.last_exit_signal = signal;
        self.touch_state_change();
    }

    /// Check if this is a target (virtual service).
    pub fn is_target(&self) -> bool {
        matches!(self.config, ServiceConfigKind::Target(_))
    }

    /// Get the dependencies definition.
    pub fn dependencies(&self) -> &DependencyDef {
        match &self.config {
            ServiceConfigKind::Service(c) => &c.dependencies,
            ServiceConfigKind::Target(c) => &c.dependencies,
        }
    }

    /// Get the service config if this is a real service.
    pub fn service_config(&self) -> Option<&ServiceConfig> {
        match &self.config {
            ServiceConfigKind::Service(c) => Some(c),
            ServiceConfigKind::Target(_) => None,
        }
    }

    /// Get the desired status for this service.
    /// Returns `Status::Start` for targets (they should always be "active").
    pub fn desired_status(&self) -> crate::sdk::Status {
        match &self.config {
            ServiceConfigKind::Service(c) => c.service.status,
            ServiceConfigKind::Target(_) => crate::sdk::Status::Start,
        }
    }

    /// Check if service should be auto-started based on its desired status.
    pub fn should_autostart(&self) -> bool {
        self.desired_status().should_autostart()
    }

    /// Get the service class for this service.
    /// Returns `ServiceClass::User` for targets.
    pub fn service_class(&self) -> crate::sdk::ServiceClass {
        match &self.config {
            ServiceConfigKind::Service(c) => c.service.class,
            ServiceConfigKind::Target(_) => crate::sdk::ServiceClass::User,
        }
    }

    /// Check if this is a system (protected) service.
    pub fn is_protected(&self) -> bool {
        self.service_class().is_system()
    }

    /// Check if this is a critical service/target.
    /// If true, failure triggers emergency shell in PID1 mode.
    pub fn is_critical(&self) -> bool {
        match &self.config {
            ServiceConfigKind::Service(c) => c.service.critical,
            ServiceConfigKind::Target(c) => c.target.critical,
        }
    }

    /// Check if service should be restarted based on status, policy, exit state, and limits.
    pub fn should_restart(&self, exit_code: Option<i32>) -> bool {
        let config = match self.service_config() {
            Some(c) => c,
            None => return false, // Targets don't restart
        };

        // Check desired status first - if "stop" or "ignore", never auto-restart
        if !self.should_autostart() {
            return false;
        }

        // Check policy
        use crate::sdk::RestartPolicy;
        let policy_allows = match config.lifecycle.restart {
            RestartPolicy::Always => true,
            RestartPolicy::OnFailure => exit_code != Some(0),
            RestartPolicy::Never => false,
        };

        if !policy_allows {
            return false;
        }

        // Check max restarts (0 = unlimited)
        let max = config.lifecycle.max_restarts;
        if max > 0 && self.restart_count >= max {
            return false;
        }

        true
    }

    /// Get next restart delay with exponential backoff.
    /// Returns None if max_restarts exceeded or policy says no restart.
    /// Increments restart_count and updates current_restart_delay_ms.
    pub fn next_restart_delay(&mut self, exit_code: Option<i32>) -> Option<u64> {
        if !self.should_restart(exit_code) {
            return None;
        }

        let delay = self.current_restart_delay_ms;

        // Exponential backoff: double for next time, capped at max
        if let Some(config) = self.service_config() {
            self.current_restart_delay_ms =
                (self.current_restart_delay_ms * 2).min(config.lifecycle.restart_delay_max_ms);
        }

        self.restart_count += 1;

        Some(delay)
    }

    /// Reset backoff when service becomes healthy (reaches Running state).
    pub fn reset_backoff(&mut self) {
        self.restart_count = 0;
        if let Some(config) = self.service_config() {
            self.current_restart_delay_ms = config.lifecycle.restart_delay_ms;
        }
    }

    /// Try to reset backoff if service has been running long enough.
    /// Returns true if backoff was reset, false if not (service didn't run long enough).
    /// The stability period prevents backoff reset for services that crash immediately.
    pub fn try_reset_backoff(&mut self) -> bool {
        let config = match self.service_config() {
            Some(c) => c,
            None => return false, // Targets don't have backoff
        };

        let stability_period = config.lifecycle.stability_period_ms;
        let now = now_millis();

        // Check if service has been running for at least the stability period
        if let Some(started_at) = self.started_at {
            let running_time = now.saturating_sub(started_at);
            if running_time >= stability_period {
                tracing::debug!(
                    service = %self.name,
                    running_time_ms = running_time,
                    stability_period_ms = stability_period,
                    "service stable, resetting backoff"
                );
                self.reset_backoff();
                return true;
            } else {
                tracing::debug!(
                    service = %self.name,
                    running_time_ms = running_time,
                    stability_period_ms = stability_period,
                    current_delay = self.current_restart_delay_ms,
                    restart_count = self.restart_count,
                    "service unstable, keeping backoff"
                );
            }
        }

        false
    }
}

/// The service dependency graph.
#[derive(Debug)]
pub struct ServiceGraph {
    graph: DiGraph<Service, DepType>,
    by_name: HashMap<String, ServiceId>,
}

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

impl ServiceGraph {
    /// Create an empty service graph.
    pub fn new() -> Self {
        Self {
            graph: DiGraph::new(),
            by_name: HashMap::new(),
        }
    }

    /// Load services from a configuration directory.
    /// Returns the graph and a list of (service_name, missing_dependency) pairs.
    pub fn load_from_directory(path: &Path) -> GraphResult<(Self, Vec<(String, String)>)> {
        let mut graph = Self::new();
        graph.load_services_from_path(path, None, &HashSet::new())?;
        let missing_deps = graph.link_dependencies()?;
        graph.validate()?;
        Ok((graph, missing_deps))
    }

    /// Load services from system directory, marking them as class=system.
    /// Returns the list of loaded service names.
    pub fn load_from_system_directory(&mut self, path: &Path) -> GraphResult<Vec<String>> {
        if !path.exists() {
            return Ok(vec![]);
        }

        let before_count = self.by_name.len();
        self.load_services_from_path(
            path,
            Some(crate::sdk::ServiceClass::System),
            &HashSet::new(),
        )?;

        // Collect names of newly added services
        let names: Vec<String> = self.by_name.keys().skip(before_count).cloned().collect();

        tracing::info!(
            path = %path.display(),
            count = names.len(),
            "loaded system services"
        );

        Ok(names)
    }

    /// Load services from user directory, skipping services in the skip set.
    pub fn load_from_user_directory(
        &mut self,
        path: &Path,
        skip: &HashSet<String>,
    ) -> GraphResult<()> {
        if !path.exists() {
            return Ok(());
        }

        self.load_services_from_path(path, None, skip)?;
        Ok(())
    }

    /// Internal helper to load services from a path.
    /// If `class_override` is Some, all services get that class.
    /// Services with names in `skip` are not loaded.
    fn load_services_from_path(
        &mut self,
        path: &Path,
        class_override: Option<crate::sdk::ServiceClass>,
        skip: &HashSet<String>,
    ) -> GraphResult<()> {
        if !path.exists() {
            return Ok(());
        }

        let entries = fs::read_dir(path)
            .map_err(|e| GraphError::ServiceNotFound(format!("cannot read directory: {}", e)))?;

        for entry in entries.flatten() {
            let file_path = entry.path();
            if file_path.extension().is_some_and(|e| e == "toml") {
                let content = fs::read_to_string(&file_path).map_err(|e| {
                    GraphError::ServiceNotFound(format!(
                        "cannot read {}: {}",
                        file_path.display(),
                        e
                    ))
                })?;

                // Try parsing as service first, then as target
                if let Ok(mut config) = ServiceConfig::parse(&content) {
                    // Check skip list
                    if skip.contains(&config.service.name) {
                        tracing::warn!(
                            service = %config.service.name,
                            "skipping user service (shadowed by system service)"
                        );
                        continue;
                    }

                    // Apply class override if specified
                    if let Some(class) = class_override {
                        config.service.class = class;
                    }

                    let errors = validate::validate_service(&config);
                    if errors.is_empty() {
                        self.add_service(Service::from_service(config))?;
                    } else {
                        tracing::warn!(
                            "skipping invalid service {}: {}",
                            file_path.display(),
                            errors.join(", ")
                        );
                    }
                } else if let Ok(config) = TargetConfig::parse(&content) {
                    // Check skip list for targets too
                    if skip.contains(&config.target.name) {
                        tracing::warn!(
                            target = %config.target.name,
                            "skipping user target (shadowed by system target)"
                        );
                        continue;
                    }

                    let errors = validate::validate_target(&config);
                    if errors.is_empty() {
                        self.add_service(Service::from_target(config))?;
                    } else {
                        tracing::warn!(
                            "skipping invalid target {}: {}",
                            file_path.display(),
                            errors.join(", ")
                        );
                    }
                } else {
                    tracing::warn!("skipping unparseable config: {}", file_path.display());
                }
            }
        }

        Ok(())
    }

    /// Add a service to the graph.
    pub fn add_service(&mut self, service: Service) -> GraphResult<ServiceId> {
        if self.by_name.contains_key(&service.name) {
            return Err(GraphError::ServiceAlreadyExists(service.name));
        }

        let name = service.name.clone();
        let id = self.graph.add_node(service);
        self.by_name.insert(name, id);
        Ok(id)
    }

    /// Link all dependencies between services.
    /// Returns a list of (service_name, missing_dependency) pairs for services
    /// that reference non-existent dependencies. These services should be marked
    /// as failed with a MissingDependency reason.
    pub fn link_dependencies(&mut self) -> GraphResult<Vec<(String, String)>> {
        // Collect all dependency relationships first
        let mut edges_to_add = Vec::new();
        let mut missing_deps = Vec::new();

        for id in self.graph.node_indices() {
            let service = &self.graph[id];
            let service_name = service.name.clone();
            let deps = service.dependencies().clone();

            // after: edge from dependency to dependent (dep must complete before this)
            for dep_name in &deps.after {
                if let Some(&dep_id) = self.by_name.get(dep_name) {
                    edges_to_add.push((dep_id, id, DepType::After));
                }
                // Skip missing dependencies for 'after' (soft dependency)
            }

            // requires: edge from dependency to dependent
            for dep_name in &deps.requires {
                if let Some(&dep_id) = self.by_name.get(dep_name) {
                    edges_to_add.push((dep_id, id, DepType::Requires));
                } else {
                    // Collect missing dependency instead of erroring
                    missing_deps.push((service_name.clone(), dep_name.clone()));
                    tracing::warn!(
                        service = %service_name,
                        dependency = %dep_name,
                        "service has missing required dependency"
                    );
                }
            }

            // wants: edge from dependency to dependent (soft)
            for dep_name in &deps.wants {
                if let Some(&dep_id) = self.by_name.get(dep_name) {
                    edges_to_add.push((dep_id, id, DepType::Wants));
                }
                // Skip missing dependencies for 'wants' (soft dependency)
            }

            // conflicts: bidirectional edges
            for conflict_name in &deps.conflicts {
                if let Some(&conflict_id) = self.by_name.get(conflict_name) {
                    edges_to_add.push((id, conflict_id, DepType::Conflicts));
                    edges_to_add.push((conflict_id, id, DepType::Conflicts));
                }
                // Skip missing conflicts
            }
        }

        // Add all edges
        for (from, to, dep_type) in edges_to_add {
            // Avoid duplicate edges
            let already_exists = self
                .graph
                .edges_connecting(from, to)
                .any(|e| *e.weight() == dep_type);
            if !already_exists {
                self.graph.add_edge(from, to, dep_type);
            }
        }

        Ok(missing_deps)
    }

    /// Validate the graph (check for cycles).
    pub fn validate(&self) -> GraphResult<()> {
        // Filter out conflict edges - they're bidirectional and don't represent
        // dependency ordering, so they would create false positive cycles
        let filtered: DiGraph<(), ()> = self.graph.filter_map(
            |_, _| Some(()),
            |_, weight| {
                if *weight != DepType::Conflicts {
                    Some(())
                } else {
                    None
                }
            },
        );

        if is_cyclic_directed(&filtered) {
            let cycle = self.find_cycle(&filtered);
            if !cycle.is_empty() {
                return Err(GraphError::CyclicDependency(cycle));
            }
        }
        Ok(())
    }

    /// Find a cycle in the graph (for error reporting).
    fn find_cycle(&self, filtered: &DiGraph<(), ()>) -> Vec<String> {
        // Use Tarjan's algorithm via petgraph
        use petgraph::algo::kosaraju_scc;
        let sccs = kosaraju_scc(filtered);
        for scc in sccs {
            if scc.len() > 1 {
                return scc
                    .iter()
                    .filter_map(|id| self.graph.node_weight(*id))
                    .map(|s| s.name.clone())
                    .collect();
            }
        }
        vec![]
    }

    /// Get a service by ID.
    pub fn get(&self, id: ServiceId) -> Option<&Service> {
        self.graph.node_weight(id)
    }

    /// Get a mutable service by ID.
    pub fn get_mut(&mut self, id: ServiceId) -> Option<&mut Service> {
        self.graph.node_weight_mut(id)
    }

    /// Get a service ID by name.
    pub fn get_by_name(&self, name: &str) -> Option<ServiceId> {
        self.by_name.get(name).copied()
    }

    /// Get all service IDs.
    pub fn all_services(&self) -> impl Iterator<Item = ServiceId> + '_ {
        self.graph.node_indices()
    }

    /// Get the number of services.
    pub fn len(&self) -> usize {
        self.graph.node_count()
    }

    /// Check if the graph is empty.
    pub fn is_empty(&self) -> bool {
        self.graph.node_count() == 0
    }

    /// Get dependencies of a service.
    pub fn dependencies(&self, id: ServiceId) -> Vec<(ServiceId, DepType)> {
        self.graph
            .edges_directed(id, Direction::Incoming)
            .filter(|e| *e.weight() != DepType::Conflicts)
            .map(|e| (e.source(), *e.weight()))
            .collect()
    }

    /// Get services that depend on this service.
    pub fn dependents(&self, id: ServiceId) -> Vec<ServiceId> {
        self.graph
            .edges_directed(id, Direction::Outgoing)
            .filter(|e| *e.weight() != DepType::Conflicts)
            .map(|e| e.target())
            .collect()
    }

    /// Get services that conflict with this service.
    pub fn conflicts(&self, id: ServiceId) -> Vec<ServiceId> {
        self.graph
            .edges_directed(id, Direction::Outgoing)
            .filter(|e| *e.weight() == DepType::Conflicts)
            .map(|e| e.target())
            .collect()
    }

    /// Get start order using topological sort.
    pub fn start_order(&self) -> Vec<ServiceId> {
        // Create a filtered graph without conflict edges
        let filtered: DiGraph<(), ()> = self.graph.filter_map(
            |_, _| Some(()),
            |_e, weight| {
                if *weight != DepType::Conflicts {
                    Some(())
                } else {
                    None
                }
            },
        );

        match toposort(&filtered, None) {
            Ok(order) => order,
            Err(_) => {
                // Cycle detected, return arbitrary order
                self.graph.node_indices().collect()
            }
        }
    }

    /// Get shutdown order (reverse of start order).
    /// Dependents are stopped before their dependencies.
    pub fn shutdown_order(&self) -> Vec<ServiceId> {
        let mut order = self.start_order();
        order.reverse();
        order
    }

    /// Get all services that transitively depend on this service.
    /// Returns in reverse topological order (most-dependent first, i.e., leaves first).
    /// This is suitable for shutdown cascading: stop the returned services in order,
    /// then stop the target service.
    pub fn all_dependents_ordered(&self, id: ServiceId) -> Vec<ServiceId> {
        let mut result = Vec::new();
        let mut visited = HashSet::new();
        self.collect_dependents_recursive(id, &mut result, &mut visited);
        result
    }

    /// Recursively collect all dependents in post-order (children before parents).
    fn collect_dependents_recursive(
        &self,
        id: ServiceId,
        result: &mut Vec<ServiceId>,
        visited: &mut HashSet<ServiceId>,
    ) {
        for dependent_id in self.dependents(id) {
            if visited.insert(dependent_id) {
                // Recurse first (post-order: most dependent services first)
                self.collect_dependents_recursive(dependent_id, result, visited);
                result.push(dependent_id);
            }
        }
    }

    /// Check if a service can start (all requires satisfied, no conflicts running).
    pub fn can_start(&self, id: ServiceId) -> Result<(), BlockedReason> {
        let mut waiting_on = Vec::new();
        let mut conflicts_with = Vec::new();

        // Check required dependencies
        for edge in self.graph.edges_directed(id, Direction::Incoming) {
            let dep_id = edge.source();
            let dep_type = *edge.weight();
            let dep = &self.graph[dep_id];

            match dep_type {
                DepType::Requires => {
                    if !dep.state.is_satisfied() {
                        waiting_on.push(dep.name.clone());
                    }
                }
                DepType::After => {
                    // 'after' only requires the service to have been attempted
                    // (not necessarily running)
                    if matches!(
                        dep.state,
                        ServiceState::Inactive | ServiceState::Blocked { .. }
                    ) {
                        waiting_on.push(dep.name.clone());
                    }
                }
                DepType::Wants => {
                    // 'wants' doesn't block startup
                }
                DepType::Conflicts => {
                    // Handled separately
                }
            }
        }

        // Check conflicts
        for conflict_id in self.conflicts(id) {
            let conflict = &self.graph[conflict_id];
            if conflict.state.is_active() {
                conflicts_with.push(conflict.name.clone());
            }
        }

        if waiting_on.is_empty() && conflicts_with.is_empty() {
            Ok(())
        } else if !waiting_on.is_empty() && !conflicts_with.is_empty() {
            Err(BlockedReason::Both {
                waiting_on,
                conflicts_with,
            })
        } else if !waiting_on.is_empty() {
            Err(BlockedReason::WaitingOn(waiting_on))
        } else {
            Err(BlockedReason::ConflictsWith(conflicts_with))
        }
    }

    /// Check if all 'requires' dependencies are satisfied.
    pub fn all_requires_satisfied(&self, id: ServiceId) -> bool {
        for edge in self.graph.edges_directed(id, Direction::Incoming) {
            if *edge.weight() == DepType::Requires {
                let dep = &self.graph[edge.source()];
                if !dep.state.is_satisfied() {
                    return false;
                }
            }
        }
        true
    }

    /// Remove a service from the graph.
    pub fn remove_service(&mut self, name: &str) -> GraphResult<()> {
        let id = self
            .by_name
            .get(name)
            .copied()
            .ok_or_else(|| GraphError::ServiceNotFound(name.to_string()))?;

        // Check for dependents
        let dependents: Vec<String> = self
            .dependents(id)
            .iter()
            .map(|dep_id| self.graph[*dep_id].name.clone())
            .collect();

        if !dependents.is_empty() {
            return Err(GraphError::HasDependents {
                service: name.to_string(),
                dependents,
            });
        }

        self.by_name.remove(name);
        self.graph.remove_node(id);
        Ok(())
    }

    /// Reload configuration from directory and compute diff.
    /// Preserves runtime state (PIDs, service states, restart counts) for unchanged services.
    pub fn reload_from_directory(&mut self, path: &Path) -> GraphResult<ReloadResult> {
        let (mut new_graph, missing_deps) = Self::load_from_directory(path)?;
        let mut diff = self.compute_diff(&new_graph);
        diff.config_errors = missing_deps.clone();

        // Preserve runtime state for services that exist in both graphs
        self.preserve_runtime_state(&mut new_graph);

        // Mark services with missing dependencies as Failed
        new_graph.mark_missing_deps_failed(&missing_deps);

        *self = new_graph;

        Ok(diff)
    }

    /// Reload configuration from both system and user directories.
    /// Preserves runtime state (PIDs, service states, restart counts) for unchanged services.
    /// Returns the diff and the updated set of system service names.
    pub fn reload_from_directories(
        &mut self,
        system_dir: Option<&Path>,
        user_dir: &Path,
    ) -> GraphResult<(ReloadResult, HashSet<String>)> {
        let mut new_graph = Self::new();
        let mut system_names = HashSet::new();

        // Load system services first (if path provided and exists)
        if let Some(sys_path) = system_dir
            && let Ok(names) = new_graph.load_from_system_directory(sys_path)
        {
            system_names = names.into_iter().collect();
        }

        // Load user services, skipping system ones
        new_graph.load_from_user_directory(user_dir, &system_names)?;

        // Link and validate
        let missing_deps = new_graph.link_dependencies()?;
        new_graph.validate()?;

        let mut diff = self.compute_diff(&new_graph);
        diff.config_errors = missing_deps.clone();

        // Preserve runtime state for services that exist in both graphs
        self.preserve_runtime_state(&mut new_graph);

        // Mark services with missing dependencies as Failed
        new_graph.mark_missing_deps_failed(&missing_deps);

        *self = new_graph;

        Ok((diff, system_names))
    }

    /// Preserve runtime state from self into the new graph for services that exist in both.
    /// This preserves: state, pid, restart_count, current_restart_delay_ms, started_at,
    /// last_state_change, last_exit_code, last_exit_signal.
    fn preserve_runtime_state(&self, new_graph: &mut ServiceGraph) {
        for (name, &old_id) in &self.by_name {
            if let Some(&new_id) = new_graph.by_name.get(name) {
                let old_service = &self.graph[old_id];
                if let Some(new_service) = new_graph.graph.node_weight_mut(new_id) {
                    // Copy runtime state
                    new_service.state = old_service.state.clone();
                    new_service.restart_count = old_service.restart_count;
                    new_service.current_restart_delay_ms = old_service.current_restart_delay_ms;
                    new_service.started_at = old_service.started_at;
                    new_service.last_state_change = old_service.last_state_change;
                    new_service.last_exit_code = old_service.last_exit_code;
                    new_service.last_exit_signal = old_service.last_exit_signal;

                    tracing::trace!(
                        service = %name,
                        state = %new_service.state,
                        "preserved runtime state during reload"
                    );
                }
            }
        }
    }

    /// Compute the difference between this graph and a new one.
    fn compute_diff(&self, new: &ServiceGraph) -> ReloadResult {
        let mut result = ReloadResult::default();

        // Find added services
        for name in new.by_name.keys() {
            if !self.by_name.contains_key(name) {
                result.added.push(name.clone());
            }
        }

        // Find removed services
        for name in self.by_name.keys() {
            if !new.by_name.contains_key(name) {
                result.removed.push(name.clone());
            }
        }

        // Find changed services (simplified: just check if config changed)
        for (name, &old_id) in &self.by_name {
            if let Some(&new_id) = new.by_name.get(name) {
                let old_service = &self.graph[old_id];
                let new_service = &new.graph[new_id];

                // Compare configs (simplified comparison)
                let changed = match (&old_service.config, &new_service.config) {
                    (ServiceConfigKind::Service(old), ServiceConfigKind::Service(new)) => {
                        old != new
                    }
                    (ServiceConfigKind::Target(old), ServiceConfigKind::Target(new)) => old != new,
                    _ => true, // Type changed
                };

                if changed {
                    result.changed.push(name.clone());
                }
            }
        }

        result
    }

    /// Format why a service is blocked as ASCII.
    pub fn format_why_blocked(&self, name: &str) -> Option<String> {
        let id = self.by_name.get(name)?;
        let service = &self.graph[*id];

        let mut lines = Vec::new();
        lines.push(format!(
            "{} {} ({})",
            service.state.symbol(),
            service.name,
            service.state.name()
        ));

        match self.can_start(*id) {
            Ok(()) => {
                lines.push("  Can start: all dependencies satisfied".to_string());
            }
            Err(reason) => {
                for dep_name in reason.waiting_on() {
                    if let Some(&dep_id) = self.by_name.get(&dep_name) {
                        let dep = &self.graph[dep_id];
                        lines.push(format!(
                            "  {} waiting on {} ({})",
                            "->",
                            dep.name,
                            dep.state.name()
                        ));
                    }
                }
                for conflict_name in reason.conflicts_with() {
                    if let Some(&conflict_id) = self.by_name.get(&conflict_name) {
                        let conflict = &self.graph[conflict_id];
                        lines.push(format!(
                            "  {} conflicts with {} ({})",
                            "!>",
                            conflict.name,
                            conflict.state.name()
                        ));
                    }
                }
            }
        }

        Some(lines.join("\n"))
    }

    /// Format the full dependency tree as ASCII.
    pub fn format_tree(&self) -> String {
        let mut lines = Vec::new();
        let order = self.start_order();

        for (i, id) in order.iter().enumerate() {
            let service = &self.graph[*id];
            let is_last = i == order.len() - 1;
            let prefix = if is_last { "└─" } else { "├─" };

            lines.push(format!(
                "{} {} {} ({})",
                prefix,
                service.state.symbol(),
                service.name,
                service.state.name()
            ));

            // Show dependencies
            let deps = self.dependencies(*id);
            for (j, (dep_id, dep_type)) in deps.iter().enumerate() {
                let dep = &self.graph[*dep_id];
                let dep_prefix = if is_last { "   " } else { "│  " };
                let dep_branch = if j == deps.len() - 1 {
                    "└─"
                } else {
                    "├─"
                };

                lines.push(format!(
                    "{}  {} {} {} ({})",
                    dep_prefix,
                    dep_branch,
                    dep_type,
                    dep.name,
                    dep.state.name()
                ));
            }
        }

        lines.join("\n")
    }

    /// Update service state.
    pub fn set_state(&mut self, id: ServiceId, state: ServiceState) {
        if let Some(service) = self.graph.node_weight_mut(id) {
            service.state = state;
            service.touch_state_change();
        }
    }

    /// Mark services with missing dependencies as Failed.
    /// Takes a list of (service_name, missing_dependency) pairs.
    /// Returns the count of services marked as failed.
    pub fn mark_missing_deps_failed(&mut self, missing_deps: &[(String, String)]) -> usize {
        use crate::sdk::FailureReason;
        use std::collections::HashMap as StdHashMap;

        // Group by service name (a service might have multiple missing deps)
        let mut by_service: StdHashMap<&str, Vec<&str>> = StdHashMap::new();
        for (service, dep) in missing_deps {
            by_service
                .entry(service.as_str())
                .or_default()
                .push(dep.as_str());
        }

        let mut count = 0;
        for (service_name, deps) in by_service {
            if let Some(id) = self.get_by_name(service_name) {
                // Use the first missing dependency for the error message
                let first_dep = deps[0].to_string();
                self.set_state(
                    id,
                    ServiceState::Failed {
                        reason: FailureReason::MissingDependency {
                            dependency: first_dep,
                        },
                    },
                );
                count += 1;
            }
        }
        count
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::sdk::{LifecycleDef, LoggingDef, ServiceDef, TargetDef};
    use std::collections::HashMap as StdHashMap;

    fn make_service(name: &str) -> Service {
        Service::from_service(ServiceConfig {
            service: ServiceDef {
                name: name.to_string(),
                exec: format!("/bin/{}", name),
                dir: None,
                oneshot: false,
                env: StdHashMap::new(),
                status: crate::sdk::Status::default(),
                class: crate::sdk::ServiceClass::default(),
                critical: false,
            },
            dependencies: DependencyDef::default(),
            lifecycle: LifecycleDef::default(),
            health: None,
            logging: LoggingDef::default(),
        })
    }

    fn make_service_with_deps(name: &str, requires: Vec<&str>) -> Service {
        Service::from_service(ServiceConfig {
            service: ServiceDef {
                name: name.to_string(),
                exec: format!("/bin/{}", name),
                dir: None,
                oneshot: false,
                env: StdHashMap::new(),
                status: crate::sdk::Status::default(),
                class: crate::sdk::ServiceClass::default(),
                critical: false,
            },
            dependencies: DependencyDef {
                requires: requires.iter().map(|s| s.to_string()).collect(),
                ..Default::default()
            },
            lifecycle: LifecycleDef::default(),
            health: None,
            logging: LoggingDef::default(),
        })
    }

    #[test]
    fn test_add_service() {
        let mut graph = ServiceGraph::new();
        let id = graph.add_service(make_service("test")).unwrap();
        assert!(graph.get(id).is_some());
        assert_eq!(graph.get(id).unwrap().name, "test");
    }

    #[test]
    fn test_duplicate_service() {
        let mut graph = ServiceGraph::new();
        graph.add_service(make_service("test")).unwrap();
        let result = graph.add_service(make_service("test"));
        assert!(matches!(result, Err(GraphError::ServiceAlreadyExists(_))));
    }

    #[test]
    fn test_get_by_name() {
        let mut graph = ServiceGraph::new();
        let id = graph.add_service(make_service("test")).unwrap();
        assert_eq!(graph.get_by_name("test"), Some(id));
        assert_eq!(graph.get_by_name("nonexistent"), None);
    }

    #[test]
    fn test_start_order() {
        let mut graph = ServiceGraph::new();
        graph.add_service(make_service("a")).unwrap();
        graph
            .add_service(make_service_with_deps("b", vec!["a"]))
            .unwrap();
        graph.link_dependencies().unwrap();

        let order = graph.start_order();
        let a_idx = order
            .iter()
            .position(|id| graph.get(*id).unwrap().name == "a")
            .unwrap();
        let b_idx = order
            .iter()
            .position(|id| graph.get(*id).unwrap().name == "b")
            .unwrap();
        assert!(a_idx < b_idx); // a must come before b
    }

    #[test]
    fn test_can_start_no_deps() {
        let mut graph = ServiceGraph::new();
        let id = graph.add_service(make_service("test")).unwrap();
        assert!(graph.can_start(id).is_ok());
    }

    #[test]
    fn test_can_start_unsatisfied_requires() {
        let mut graph = ServiceGraph::new();
        graph.add_service(make_service("dep")).unwrap();
        graph
            .add_service(make_service_with_deps("test", vec!["dep"]))
            .unwrap();
        graph.link_dependencies().unwrap();

        let test_id = graph.get_by_name("test").unwrap();
        let result = graph.can_start(test_id);
        assert!(matches!(result, Err(BlockedReason::WaitingOn(_))));
    }

    #[test]
    fn test_can_start_satisfied_requires() {
        let mut graph = ServiceGraph::new();
        let dep_id = graph.add_service(make_service("dep")).unwrap();
        graph
            .add_service(make_service_with_deps("test", vec!["dep"]))
            .unwrap();
        graph.link_dependencies().unwrap();

        // Set dependency to running
        graph.set_state(dep_id, ServiceState::Running { pid: 123 });

        let test_id = graph.get_by_name("test").unwrap();
        assert!(graph.can_start(test_id).is_ok());
    }

    #[test]
    fn test_target_service() {
        let target = Service::from_target(TargetConfig {
            target: TargetDef {
                name: "multi-user".to_string(),
                critical: false,
            },
            dependencies: DependencyDef::default(),
        });
        assert!(target.is_target());
        assert!(target.service_config().is_none());
    }

    #[test]
    fn test_format_tree() {
        let mut graph = ServiceGraph::new();
        graph.add_service(make_service("a")).unwrap();
        graph.add_service(make_service("b")).unwrap();

        let tree = graph.format_tree();
        assert!(tree.contains("a"));
        assert!(tree.contains("b"));
    }

    #[test]
    fn test_shutdown_order_simple() {
        // database <- app (app depends on database)
        let mut graph = ServiceGraph::new();
        graph.add_service(make_service("database")).unwrap();
        graph
            .add_service(make_service_with_deps("app", vec!["database"]))
            .unwrap();
        graph.link_dependencies().unwrap();

        let shutdown = graph.shutdown_order();
        let names: Vec<_> = shutdown
            .iter()
            .map(|id| graph.get(*id).unwrap().name.as_str())
            .collect();

        // app should come before database in shutdown order
        let app_idx = names.iter().position(|n| *n == "app").unwrap();
        let db_idx = names.iter().position(|n| *n == "database").unwrap();
        assert!(app_idx < db_idx, "app should stop before database");
    }

    #[test]
    fn test_shutdown_order_diamond() {
        // A <- B, A <- C, B <- D, C <- D (D depends on both B and C)
        let mut graph = ServiceGraph::new();
        graph.add_service(make_service("a")).unwrap();
        graph
            .add_service(make_service_with_deps("b", vec!["a"]))
            .unwrap();
        graph
            .add_service(make_service_with_deps("c", vec!["a"]))
            .unwrap();
        graph
            .add_service(make_service_with_deps("d", vec!["b", "c"]))
            .unwrap();
        graph.link_dependencies().unwrap();

        let shutdown = graph.shutdown_order();
        let names: Vec<_> = shutdown
            .iter()
            .map(|id| graph.get(*id).unwrap().name.as_str())
            .collect();

        // D should come first (most dependent)
        // Then B and C
        // Finally A (least dependent)
        let d_idx = names.iter().position(|n| *n == "d").unwrap();
        let b_idx = names.iter().position(|n| *n == "b").unwrap();
        let c_idx = names.iter().position(|n| *n == "c").unwrap();
        let a_idx = names.iter().position(|n| *n == "a").unwrap();

        assert!(d_idx < b_idx, "d should stop before b");
        assert!(d_idx < c_idx, "d should stop before c");
        assert!(b_idx < a_idx, "b should stop before a");
        assert!(c_idx < a_idx, "c should stop before a");
    }

    #[test]
    fn test_all_dependents_ordered_chain() {
        // A <- B <- C <- D (D depends on C, C depends on B, B depends on A)
        let mut graph = ServiceGraph::new();
        graph.add_service(make_service("a")).unwrap();
        graph
            .add_service(make_service_with_deps("b", vec!["a"]))
            .unwrap();
        graph
            .add_service(make_service_with_deps("c", vec!["b"]))
            .unwrap();
        graph
            .add_service(make_service_with_deps("d", vec!["c"]))
            .unwrap();
        graph.link_dependencies().unwrap();

        let a_id = graph.get_by_name("a").unwrap();
        let dependents = graph.all_dependents_ordered(a_id);
        let names: Vec<_> = dependents
            .iter()
            .map(|id| graph.get(*id).unwrap().name.as_str())
            .collect();

        // Should get D, C, B in that order (most dependent first)
        assert_eq!(names.len(), 3);
        assert_eq!(names, vec!["d", "c", "b"]);
    }

    #[test]
    fn test_all_dependents_ordered_diamond() {
        // database <- app, database <- worker
        let mut graph = ServiceGraph::new();
        graph.add_service(make_service("database")).unwrap();
        graph
            .add_service(make_service_with_deps("app", vec!["database"]))
            .unwrap();
        graph
            .add_service(make_service_with_deps("worker", vec!["database"]))
            .unwrap();
        graph.link_dependencies().unwrap();

        let db_id = graph.get_by_name("database").unwrap();
        let dependents = graph.all_dependents_ordered(db_id);
        let names: Vec<_> = dependents
            .iter()
            .map(|id| graph.get(*id).unwrap().name.as_str())
            .collect();

        // Both app and worker depend on database
        assert_eq!(names.len(), 2);
        assert!(names.contains(&"app"));
        assert!(names.contains(&"worker"));
    }

    #[test]
    fn test_all_dependents_ordered_none() {
        // app has no dependents
        let mut graph = ServiceGraph::new();
        graph.add_service(make_service("database")).unwrap();
        graph
            .add_service(make_service_with_deps("app", vec!["database"]))
            .unwrap();
        graph.link_dependencies().unwrap();

        let app_id = graph.get_by_name("app").unwrap();
        let dependents = graph.all_dependents_ordered(app_id);

        assert!(dependents.is_empty());
    }

    #[test]
    fn test_load_from_system_directory_nonexistent() {
        let mut graph = ServiceGraph::new();
        let path = std::path::Path::new("/nonexistent/path");
        let result = graph.load_from_system_directory(path);
        assert!(result.is_ok());
        assert!(result.unwrap().is_empty());
    }

    #[test]
    fn test_load_from_user_directory_with_skip() {
        // Test that services in skip set are not loaded
        let mut graph = ServiceGraph::new();

        // First add a "system" service manually
        let mut system_svc = make_service("network");
        if let ServiceConfigKind::Service(ref mut c) = system_svc.config {
            c.service.class = crate::sdk::ServiceClass::System;
        }
        graph.add_service(system_svc).unwrap();

        // Create skip set with "network"
        let skip: HashSet<String> = vec!["network".to_string()].into_iter().collect();

        // Try loading from nonexistent dir (should not error)
        let result = graph.load_from_user_directory(std::path::Path::new("/nonexistent"), &skip);
        assert!(result.is_ok());

        // "network" should still exist (wasn't removed)
        assert!(graph.get_by_name("network").is_some());
    }

    #[test]
    fn test_reload_from_directories_empty() {
        let mut graph = ServiceGraph::new();
        graph.add_service(make_service("old-service")).unwrap();

        // Reload from nonexistent directories
        let result = graph.reload_from_directories(
            Some(std::path::Path::new("/nonexistent/system")),
            std::path::Path::new("/nonexistent/user"),
        );

        assert!(result.is_ok());
        let (diff, system_names) = result.unwrap();

        // old-service should be in removed list
        assert!(diff.removed.contains(&"old-service".to_string()));
        assert!(system_names.is_empty());
    }

    #[test]
    fn test_missing_dependency_graceful() {
        // Test that missing dependencies don't cause hard errors
        let mut graph = ServiceGraph::new();

        // Add a service that requires a non-existent dependency
        graph
            .add_service(make_service_with_deps("app", vec!["missing-db"]))
            .unwrap();

        // link_dependencies should succeed but return the missing deps
        let missing = graph.link_dependencies().unwrap();

        assert_eq!(missing.len(), 1);
        assert_eq!(missing[0].0, "app");
        assert_eq!(missing[0].1, "missing-db");

        // Graph should still be valid (no cycles)
        assert!(graph.validate().is_ok());
    }

    #[test]
    fn test_mark_missing_deps_failed() {
        use crate::sdk::FailureReason;

        let mut graph = ServiceGraph::new();
        graph
            .add_service(make_service_with_deps("app", vec!["missing-db"]))
            .unwrap();

        let missing = graph.link_dependencies().unwrap();
        let count = graph.mark_missing_deps_failed(&missing);

        assert_eq!(count, 1);

        // Check that the service is now in Failed state
        let app_id = graph.get_by_name("app").unwrap();
        let app = graph.get(app_id).unwrap();

        match &app.state {
            ServiceState::Failed { reason } => match reason {
                FailureReason::MissingDependency { dependency } => {
                    assert_eq!(dependency, "missing-db");
                }
                _ => panic!("expected MissingDependency reason"),
            },
            _ => panic!("expected Failed state"),
        }
    }

    #[test]
    fn test_mixed_valid_and_missing_deps() {
        let mut graph = ServiceGraph::new();

        // Add a valid dependency
        graph.add_service(make_service("database")).unwrap();

        // Add a service with one valid and one missing dependency
        let mut svc = make_service_with_deps("app", vec!["database", "missing-cache"]);
        if let ServiceConfigKind::Service(ref mut c) = svc.config {
            c.dependencies.requires = vec!["database".to_string(), "missing-cache".to_string()];
        }
        graph.add_service(svc).unwrap();

        let missing = graph.link_dependencies().unwrap();

        // Should report the missing dependency
        assert_eq!(missing.len(), 1);
        assert_eq!(missing[0].0, "app");
        assert_eq!(missing[0].1, "missing-cache");

        // But the valid edge should still be created
        let app_id = graph.get_by_name("app").unwrap();
        let deps = graph.dependencies(app_id);
        assert_eq!(deps.len(), 1); // Only the valid dep is linked
    }

    #[test]
    fn test_preserve_runtime_state() {
        // Create an old graph with a running service
        let mut old_graph = ServiceGraph::new();
        let db_id = old_graph.add_service(make_service("database")).unwrap();
        let app_id = old_graph.add_service(make_service("app")).unwrap();

        // Set runtime state on old services
        old_graph.set_state(db_id, ServiceState::Running { pid: 1234 });
        if let Some(db) = old_graph.get_mut(db_id) {
            db.restart_count = 3;
            db.started_at = Some(1000);
            db.current_restart_delay_ms = 8000;
        }
        old_graph.set_state(app_id, ServiceState::Running { pid: 5678 });
        if let Some(app) = old_graph.get_mut(app_id) {
            app.restart_count = 1;
            app.started_at = Some(2000);
        }

        // Create a new graph with the same services (simulating reload from disk)
        let mut new_graph = ServiceGraph::new();
        new_graph.add_service(make_service("database")).unwrap();
        new_graph.add_service(make_service("app")).unwrap();
        new_graph.add_service(make_service("new-service")).unwrap();

        // New services should start as Inactive
        let new_db_id = new_graph.get_by_name("database").unwrap();
        assert!(matches!(
            new_graph.get(new_db_id).unwrap().state,
            ServiceState::Inactive
        ));

        // Preserve runtime state
        old_graph.preserve_runtime_state(&mut new_graph);

        // Check database service preserved state
        let new_db = new_graph.get(new_db_id).unwrap();
        assert!(matches!(new_db.state, ServiceState::Running { pid: 1234 }));
        assert_eq!(new_db.restart_count, 3);
        assert_eq!(new_db.started_at, Some(1000));
        assert_eq!(new_db.current_restart_delay_ms, 8000);

        // Check app service preserved state
        let new_app_id = new_graph.get_by_name("app").unwrap();
        let new_app = new_graph.get(new_app_id).unwrap();
        assert!(matches!(new_app.state, ServiceState::Running { pid: 5678 }));
        assert_eq!(new_app.restart_count, 1);
        assert_eq!(new_app.started_at, Some(2000));

        // New service should remain Inactive
        let new_svc_id = new_graph.get_by_name("new-service").unwrap();
        let new_svc = new_graph.get(new_svc_id).unwrap();
        assert!(matches!(new_svc.state, ServiceState::Inactive));
        assert_eq!(new_svc.restart_count, 0);
    }
}