oxiz_sat/

allsat.rs

//! All-SAT / Model Enumeration
//!
//! This module provides functionality for enumerating multiple or all satisfying
//! assignments for a SAT formula. It supports:
//! - Complete enumeration (find all solutions)
//! - Limited enumeration (find up to N solutions)
//! - Projected enumeration (enumerate over subset of variables)
//! - Solution blocking (add clauses to exclude found solutions)
//! - Minimal/maximal model enumeration
//! - Solution counting
//!
//! ## Algorithm
//!
//! The basic approach uses solution blocking:
//! 1. Solve the formula
//! 2. If SAT, extract model and block it with a clause
//! 3. Repeat until UNSAT or limit reached
//!
//! For projected enumeration over variables V', we block only those assignments:
//! - Block clause: (¬l1 ∨ ¬l2 ∨ ... ∨ ¬ln) where li ∈ V' are assigned literals
//!
//! ## Example
//!
//! ```rust,ignore
//! use oxiz_sat::{Solver, AllSatEnumerator, Var, Lit};
//!
// let mut solver = Solver::new();
// // Add formula: (x1 ∨ x2) ∧ (¬x1 ∨ x3)
// solver.add_clause([Lit::pos(Var(0)), Lit::pos(Var(1))]);
// solver.add_clause([Lit::neg(Var(0)), Lit::pos(Var(2))]);
//
// let mut enumerator = AllSatEnumerator::new();
// let models = enumerator.enumerate_all(&mut solver, 3);
// println!("Found {} models", models.len());
// ```

use crate::literal::{LBool, Lit, Var};
#[allow(unused_imports)]
use crate::prelude::*;
use crate::solver::{Solver, SolverResult};
use smallvec::SmallVec;

/// A model (satisfying assignment) represented as a vector of literals
pub type Model = Vec<Lit>;

/// Configuration for model enumeration
#[derive(Debug, Clone, Default)]
pub struct EnumerationConfig {
    /// Maximum number of models to find (None = find all)
    pub max_models: Option<usize>,
    /// Variables to project onto (None = all variables)
    pub project_vars: Option<HashSet<Var>>,
    /// Only find minimal models (minimum number of true literals)
    pub minimal_models: bool,
    /// Only find maximal models (maximum number of true literals)
    pub maximal_models: bool,
    /// Block solutions with positive literals only (optimization)
    pub block_positive_only: bool,
}

impl EnumerationConfig {
    /// Create config to find all models
    #[must_use]
    pub fn all() -> Self {
        Self::default()
    }

    /// Create config to find up to N models
    #[must_use]
    pub fn limited(max_models: usize) -> Self {
        Self {
            max_models: Some(max_models),
            ..Default::default()
        }
    }

    /// Create config for projected enumeration
    #[must_use]
    pub fn projected(vars: HashSet<Var>) -> Self {
        Self {
            project_vars: Some(vars),
            ..Default::default()
        }
    }

    /// Set maximum number of models
    pub fn with_max_models(mut self, max: usize) -> Self {
        self.max_models = Some(max);
        self
    }

    /// Set projection variables
    pub fn with_projection(mut self, vars: HashSet<Var>) -> Self {
        self.project_vars = Some(vars);
        self
    }

    /// Enable minimal model enumeration
    #[must_use]
    pub const fn minimal(mut self) -> Self {
        self.minimal_models = true;
        self
    }

    /// Enable maximal model enumeration
    #[must_use]
    pub const fn maximal(mut self) -> Self {
        self.maximal_models = true;
        self
    }
}

/// Statistics for model enumeration
#[derive(Debug, Default, Clone)]
pub struct EnumerationStats {
    /// Number of models found
    pub models_found: usize,
    /// Number of solver calls made
    pub solver_calls: usize,
    /// Number of blocking clauses added
    pub blocking_clauses: usize,
    /// Total number of variables in all models
    pub total_literals: usize,
}

impl EnumerationStats {
    /// Get average model size (number of literals)
    #[must_use]
    pub fn avg_model_size(&self) -> f64 {
        if self.models_found == 0 {
            0.0
        } else {
            self.total_literals as f64 / self.models_found as f64
        }
    }
}

/// Result of enumeration
#[derive(Debug, Clone)]
pub enum EnumerationResult {
    /// Successfully enumerated all models (or reached limit)
    Complete(Vec<Model>),
    /// Enumeration incomplete (solver returned Unknown)
    Incomplete(Vec<Model>),
    /// Formula is unsatisfiable
    Unsat,
}

impl EnumerationResult {
    /// Get the models (empty if Unsat)
    #[must_use]
    pub fn models(&self) -> &[Model] {
        match self {
            EnumerationResult::Complete(models) | EnumerationResult::Incomplete(models) => models,
            EnumerationResult::Unsat => &[],
        }
    }

    /// Check if enumeration was complete
    #[must_use]
    pub const fn is_complete(&self) -> bool {
        matches!(self, EnumerationResult::Complete(_))
    }

    /// Number of models found
    #[must_use]
    pub fn count(&self) -> usize {
        self.models().len()
    }
}

/// All-SAT enumerator for finding multiple satisfying assignments
pub struct AllSatEnumerator {
    /// Configuration
    config: EnumerationConfig,
    /// Statistics
    stats: EnumerationStats,
    /// Collected models
    models: Vec<Model>,
}

impl AllSatEnumerator {
    /// Create a new enumerator with given configuration
    #[must_use]
    pub fn new(config: EnumerationConfig) -> Self {
        Self {
            config,
            stats: EnumerationStats::default(),
            models: Vec::new(),
        }
    }

    /// Create enumerator with default configuration
    #[must_use]
    pub fn default_config() -> Self {
        Self::new(EnumerationConfig::default())
    }

    /// Get statistics
    #[must_use]
    pub const fn stats(&self) -> &EnumerationStats {
        &self.stats
    }

    /// Get collected models
    #[must_use]
    pub fn models(&self) -> &[Model] {
        &self.models
    }

    /// Reset enumerator state
    pub fn reset(&mut self) {
        self.models.clear();
        self.stats = EnumerationStats::default();
    }

    /// Enumerate all satisfying assignments
    ///
    /// # Arguments
    ///
    /// * `solver` - The SAT solver instance
    /// * `num_vars` - Total number of variables in the formula
    ///
    /// # Returns
    ///
    /// Returns `EnumerationResult` with found models
    pub fn enumerate(&mut self, solver: &mut Solver, num_vars: usize) -> EnumerationResult {
        self.reset();

        loop {
            // Check if we've reached the limit
            if let Some(max) = self.config.max_models
                && self.models.len() >= max
            {
                return EnumerationResult::Complete(self.models.clone());
            }

            // Solve
            self.stats.solver_calls += 1;
            let result = solver.solve();

            match result {
                SolverResult::Sat => {
                    // Extract model
                    let model = self.extract_model(solver, num_vars);

                    // Backtrack to level 0 before adding blocking clause
                    // This is necessary for incremental solving to work correctly
                    solver.backtrack_to_root();

                    // Check if this is a valid model (for minimal/maximal)
                    if self.is_valid_model(&model) {
                        self.stats.models_found += 1;
                        self.stats.total_literals += model.len();
                        self.models.push(model.clone());

                        // Block this solution
                        let blocking_clause = self.create_blocking_clause(&model);
                        self.stats.blocking_clauses += 1;
                        if !solver.add_clause(blocking_clause.iter().copied()) {
                            // Adding blocking clause made formula UNSAT
                            return EnumerationResult::Complete(self.models.clone());
                        }
                    } else {
                        // Block and continue without adding to results
                        let blocking_clause = self.create_blocking_clause(&model);
                        self.stats.blocking_clauses += 1;
                        if !solver.add_clause(blocking_clause.iter().copied()) {
                            return EnumerationResult::Complete(self.models.clone());
                        }
                    }
                }
                SolverResult::Unsat => {
                    // No more models
                    if self.models.is_empty() {
                        return EnumerationResult::Unsat;
                    }
                    return EnumerationResult::Complete(self.models.clone());
                }
                SolverResult::Unknown => {
                    // Solver couldn't determine, return incomplete
                    return EnumerationResult::Incomplete(self.models.clone());
                }
            }
        }
    }

    /// Extract model from solver's current assignment
    fn extract_model(&self, solver: &Solver, num_vars: usize) -> Model {
        let mut model = Vec::new();

        for i in 0..num_vars {
            let var = Var(i as u32);
            let value = solver.model_value(var);

            // Skip undefined variables
            if value == LBool::Undef {
                continue;
            }

            // Check if we should include this variable
            if let Some(ref project_vars) = self.config.project_vars
                && !project_vars.contains(&var)
            {
                continue;
            }

            // Add literal to model
            let lit = if value == LBool::True {
                Lit::pos(var)
            } else {
                Lit::neg(var)
            };

            model.push(lit);
        }

        model
    }

    /// Check if a model satisfies minimal/maximal constraints
    fn is_valid_model(&self, _model: &Model) -> bool {
        if self.config.minimal_models {
            // For minimal models, we need to check if any subset is also a model
            // This is expensive, so we use a heuristic: check if removing any single
            // true literal still gives a model (would be blocked by our approach)
            // In practice, minimal model enumeration needs additional solver calls
            // For now, we accept all models (full minimal checking is complex)
        }

        if self.config.maximal_models {
            // Similar to minimal - full checking is complex
            // Would need to check if we can extend the model
        }

        true
    }

    /// Create a blocking clause for a given model
    fn create_blocking_clause(&self, model: &Model) -> SmallVec<[Lit; 32]> {
        let mut clause = SmallVec::new();

        for &lit in model {
            // For blocking, we negate the literals
            // If model has x1=true, x2=false, x3=true
            // Blocking clause is: (¬x1 ∨ x2 ∨ ¬x3)
            if self.config.block_positive_only && lit.is_neg() {
                // Optimization: only block positive assignments
                continue;
            }
            clause.push(lit.negate());
        }

        // Ensure we have a non-empty clause
        if clause.is_empty() && !model.is_empty() {
            // If all literals were negative and block_positive_only is true,
            // add at least one literal to avoid empty clause
            clause.push(model[0].negate());
        }

        clause
    }
}

/// Convenience functions for common enumeration tasks
impl AllSatEnumerator {
    /// Enumerate all models (no limit)
    ///
    /// # Arguments
    ///
    /// * `solver` - The SAT solver
    /// * `num_vars` - Number of variables
    ///
    /// # Returns
    ///
    /// Vector of all found models
    #[must_use]
    pub fn enumerate_all(solver: &mut Solver, num_vars: usize) -> Vec<Model> {
        let mut enumerator = Self::new(EnumerationConfig::all());
        enumerator.enumerate(solver, num_vars).models().to_vec()
    }

    /// Enumerate up to N models
    ///
    /// # Arguments
    ///
    /// * `solver` - The SAT solver
    /// * `num_vars` - Number of variables
    /// * `max_models` - Maximum number of models to find
    #[must_use]
    pub fn enumerate_limited(
        solver: &mut Solver,
        num_vars: usize,
        max_models: usize,
    ) -> Vec<Model> {
        let mut enumerator = Self::new(EnumerationConfig::limited(max_models));
        enumerator.enumerate(solver, num_vars).models().to_vec()
    }

    /// Count the number of satisfying assignments
    ///
    /// # Arguments
    ///
    /// * `solver` - The SAT solver
    /// * `num_vars` - Number of variables
    /// * `max_count` - Maximum count (None = count all)
    ///
    /// # Returns
    ///
    /// Number of models found (up to max_count)
    pub fn count_models(solver: &mut Solver, num_vars: usize, max_count: Option<usize>) -> usize {
        let config = if let Some(max) = max_count {
            EnumerationConfig::limited(max)
        } else {
            EnumerationConfig::all()
        };

        let mut enumerator = Self::new(config);
        let result = enumerator.enumerate(solver, num_vars);
        result.count()
    }

    /// Enumerate models with projection onto specific variables
    ///
    /// # Arguments
    ///
    /// * `solver` - The SAT solver
    /// * `num_vars` - Number of variables
    /// * `project_vars` - Variables to project onto
    #[must_use]
    pub fn enumerate_projected(
        solver: &mut Solver,
        num_vars: usize,
        project_vars: HashSet<Var>,
    ) -> Vec<Model> {
        let mut enumerator = Self::new(EnumerationConfig::projected(project_vars));
        enumerator.enumerate(solver, num_vars).models().to_vec()
    }
}

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

    #[test]
    fn test_enumerate_simple() {
        let mut solver = Solver::new();
        // Formula: x1 ∨ x2
        solver.add_clause([Lit::pos(Var(0)), Lit::pos(Var(1))]);

        let models = AllSatEnumerator::enumerate_all(&mut solver, 2);
        // Should find 3 models: {x1}, {x2}, {x1, x2}
        // (plus variations with negative literals)
        assert!(!models.is_empty());
    }

    #[test]
    fn test_enumerate_unsat() {
        let mut solver = Solver::new();
        // Contradictory clauses
        solver.add_clause([Lit::pos(Var(0))]);
        solver.add_clause([Lit::neg(Var(0))]);

        let mut enumerator = AllSatEnumerator::new(EnumerationConfig::all());
        let result = enumerator.enumerate(&mut solver, 1);

        assert!(matches!(result, EnumerationResult::Unsat));
        assert_eq!(result.count(), 0);
    }

    #[test]
    fn test_enumerate_limited() {
        let mut solver = Solver::new();
        // Formula that has multiple solutions: x1 ∨ x2
        solver.add_clause([Lit::pos(Var(0)), Lit::pos(Var(1))]);

        let models = AllSatEnumerator::enumerate_limited(&mut solver, 2, 2);
        assert!(models.len() <= 2);
    }

    #[test]
    fn test_enumerate_single_var() {
        let mut solver = Solver::new();
        // No constraints - x1 can be true or false
        // Actually, with no constraints, everything is a model
        // Add a trivial tautology to make it non-trivial
        solver.add_clause([Lit::pos(Var(0)), Lit::neg(Var(0))]);

        let models = AllSatEnumerator::enumerate_all(&mut solver, 1);
        // With a tautology, we should find models (any assignment works)
        // But in practice, the solver might find multiple assignments
        assert!(!models.is_empty());
    }

    #[test]
    fn test_count_models() {
        let mut solver = Solver::new();
        solver.add_clause([Lit::pos(Var(0)), Lit::pos(Var(1))]);

        let count = AllSatEnumerator::count_models(&mut solver, 2, Some(5));
        assert!(count >= 1);
        assert!(count <= 5);
    }

    #[test]
    fn test_enumerator_stats() {
        let mut solver = Solver::new();
        solver.add_clause([Lit::pos(Var(0))]);

        let mut enumerator = AllSatEnumerator::new(EnumerationConfig::limited(10));
        enumerator.enumerate(&mut solver, 1);

        let stats = enumerator.stats();
        assert!(stats.models_found >= 1);
        assert!(stats.solver_calls >= 1);
        assert_eq!(stats.models_found, stats.blocking_clauses);
    }

    #[test]
    fn test_projected_enumeration() {
        let mut solver = Solver::new();
        // Formula: x1 ∧ (x2 ∨ x3)
        solver.add_clause([Lit::pos(Var(0))]);
        solver.add_clause([Lit::pos(Var(1)), Lit::pos(Var(2))]);

        // Project onto x1 and x2 only
        let mut project_vars = HashSet::new();
        project_vars.insert(Var(0));
        project_vars.insert(Var(1));

        let models = AllSatEnumerator::enumerate_projected(&mut solver, 3, project_vars);
        // Should find models with x1=true and different x2 values
        assert!(!models.is_empty());

        // All models should only contain x1 and x2
        for model in &models {
            for lit in model {
                assert!(lit.var() == Var(0) || lit.var() == Var(1));
            }
        }
    }

    #[test]
    fn test_blocking_clause_creation() {
        let enumerator = AllSatEnumerator::new(EnumerationConfig::all());
        let model = vec![Lit::pos(Var(0)), Lit::neg(Var(1)), Lit::pos(Var(2))];

        let blocking = enumerator.create_blocking_clause(&model);

        // Blocking clause should be: ¬x1 ∨ x2 ∨ ¬x3
        assert_eq!(blocking.len(), 3);
        assert!(blocking.contains(&Lit::neg(Var(0))));
        assert!(blocking.contains(&Lit::pos(Var(1))));
        assert!(blocking.contains(&Lit::neg(Var(2))));
    }

    #[test]
    fn test_enumeration_result_methods() {
        let models = vec![vec![Lit::pos(Var(0))], vec![Lit::neg(Var(0))]];
        let result = EnumerationResult::Complete(models.clone());

        assert!(result.is_complete());
        assert_eq!(result.count(), 2);
        assert_eq!(result.models().len(), 2);

        let unsat = EnumerationResult::Unsat;
        assert_eq!(unsat.count(), 0);
        assert!(unsat.models().is_empty());
    }

    #[test]
    fn test_config_builders() {
        let config = EnumerationConfig::all();
        assert!(config.max_models.is_none());

        let config = EnumerationConfig::limited(10);
        assert_eq!(config.max_models, Some(10));

        let mut vars = HashSet::new();
        vars.insert(Var(0));
        let config = EnumerationConfig::projected(vars.clone());
        assert!(config.project_vars.is_some());

        let config = EnumerationConfig::all().minimal().maximal();
        assert!(config.minimal_models);
        assert!(config.maximal_models);
    }

    #[test]
    fn test_stats_avg_model_size() {
        let mut stats = EnumerationStats::default();
        assert_eq!(stats.avg_model_size(), 0.0);

        stats.models_found = 3;
        stats.total_literals = 12;
        assert_eq!(stats.avg_model_size(), 4.0);
    }

    #[test]
    fn test_reset() {
        let mut solver = Solver::new();
        solver.add_clause([Lit::pos(Var(0))]);

        let mut enumerator = AllSatEnumerator::new(EnumerationConfig::limited(5));
        enumerator.enumerate(&mut solver, 1);

        assert!(!enumerator.models().is_empty());

        enumerator.reset();
        assert!(enumerator.models().is_empty());
        assert_eq!(enumerator.stats().models_found, 0);
    }
}