problemreductions/rules/
traits.rs

1//! Core traits for problem reductions.
2
3use crate::traits::Problem;
4use serde::de::DeserializeOwned;
5use serde::Serialize;
6use std::any::Any;
7use std::marker::PhantomData;
8
9/// Failure to construct a target instance for a registered reduction edge.
10#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
11pub enum ReductionError {
12    #[error("{source_problem} -> {target_problem}: target construction failed: {cause}")]
13    Construction {
14        source_problem: &'static str,
15        target_problem: &'static str,
16        #[source]
17        cause: crate::registry::ConstructionError,
18    },
19    #[error("{source_problem} -> {target_problem}: integer overflow while {operation}")]
20    IntegerOverflow {
21        source_problem: &'static str,
22        target_problem: &'static str,
23        operation: String,
24    },
25    #[error("{source_problem} -> {target_problem}: non-finite value while {operation}")]
26    NonFiniteResult {
27        source_problem: &'static str,
28        target_problem: &'static str,
29        operation: String,
30    },
31    #[error("{source_problem} -> {target_problem}: {cause}")]
32    InexactFloatConversion {
33        source_problem: &'static str,
34        target_problem: &'static str,
35        #[source]
36        cause: crate::types::ExactI64ToF64Error,
37    },
38    #[error("{source_problem} -> {target_problem}: {message}")]
39    InvalidTarget {
40        source_problem: &'static str,
41        target_problem: &'static str,
42        message: String,
43    },
44    #[error(
45        "{source_problem} -> {target_problem}: reduction executor expected source type `{expected}`"
46    )]
47    SourceTypeMismatch {
48        source_problem: &'static str,
49        target_problem: &'static str,
50        expected: &'static str,
51    },
52}
53
54impl ReductionError {
55    pub(crate) fn for_reduction<S: Problem, T: Problem>(self) -> Self {
56        match self {
57            Self::Construction { cause, .. } => Self::construction::<S, T>(cause),
58            Self::IntegerOverflow { operation, .. } => Self::integer_overflow::<S, T>(operation),
59            Self::NonFiniteResult { operation, .. } => Self::non_finite_result::<S, T>(operation),
60            Self::InexactFloatConversion { cause, .. } => {
61                Self::inexact_float_conversion::<S, T>(cause)
62            }
63            Self::InvalidTarget { message, .. } => Self::invalid_target::<S, T>(message),
64            Self::SourceTypeMismatch { expected, .. } => Self::SourceTypeMismatch {
65                source_problem: S::NAME,
66                target_problem: T::NAME,
67                expected,
68            },
69        }
70    }
71
72    /// Report that a type-erased executor received the wrong source problem type.
73    pub fn source_type_mismatch<S: Problem, T: Problem>() -> Self {
74        Self::SourceTypeMismatch {
75            source_problem: S::NAME,
76            target_problem: T::NAME,
77            expected: std::any::type_name::<S>(),
78        }
79    }
80
81    /// Report integer overflow while constructing a reduction target.
82    pub fn integer_overflow<S: Problem, T: Problem>(operation: impl Into<String>) -> Self {
83        Self::IntegerOverflow {
84            source_problem: S::NAME,
85            target_problem: T::NAME,
86            operation: operation.into(),
87        }
88    }
89
90    /// Report that an exact integer cannot be represented in a floating-point target field.
91    pub fn inexact_float_conversion<S: Problem, T: Problem>(
92        cause: crate::types::ExactI64ToF64Error,
93    ) -> Self {
94        Self::InexactFloatConversion {
95            source_problem: S::NAME,
96            target_problem: T::NAME,
97            cause,
98        }
99    }
100
101    /// Report non-finite arithmetic while constructing a reduction target.
102    pub fn non_finite_result<S: Problem, T: Problem>(operation: impl Into<String>) -> Self {
103        Self::NonFiniteResult {
104            source_problem: S::NAME,
105            target_problem: T::NAME,
106            operation: operation.into(),
107        }
108    }
109
110    /// Report that derived data cannot form a valid reduction target.
111    pub fn invalid_target<S: Problem, T: Problem>(message: impl Into<String>) -> Self {
112        Self::InvalidTarget {
113            source_problem: S::NAME,
114            target_problem: T::NAME,
115            message: message.into(),
116        }
117    }
118
119    /// Preserve a target constructor's validation error with edge context.
120    pub fn construction<S: Problem, T: Problem>(cause: crate::registry::ConstructionError) -> Self {
121        Self::Construction {
122            source_problem: S::NAME,
123            target_problem: T::NAME,
124            cause,
125        }
126    }
127}
128
129/// Failure to map a target witness back into the source configuration space.
130#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
131pub enum ExtractionError {
132    #[error("{0}")]
133    InvalidTargetSolution(String),
134    #[error("{source_problem} -> {target_problem}: {message}")]
135    Reduction {
136        source_problem: &'static str,
137        target_problem: &'static str,
138        message: String,
139    },
140    #[error("target evaluation failed during extraction: {0}")]
141    Evaluation(#[from] crate::traits::EvaluationError),
142}
143
144impl ExtractionError {
145    pub fn invalid(message: impl Into<String>) -> Self {
146        Self::InvalidTargetSolution(message.into())
147    }
148
149    fn for_reduction<S: Problem, T: Problem>(self) -> Self {
150        match self {
151            Self::InvalidTargetSolution(message) => Self::Reduction {
152                source_problem: S::NAME,
153                target_problem: T::NAME,
154                message,
155            },
156            error => error,
157        }
158    }
159}
160
161pub type ExtractionResult<T> = std::result::Result<T, ExtractionError>;
162
163/// Validate a typed target solution and return its evaluated value for reuse.
164pub(crate) fn validate_target_solution<P: Problem>(
165    target: &P,
166    solution: &P::Solution,
167) -> ExtractionResult<P::Value> {
168    Ok(target.evaluate(solution)?)
169}
170
171/// Validate once, then require the evaluated target to certify a source witness.
172/// The rule supplies its feasibility predicate or value-map threshold and rejection reason.
173/// A rejected candidate is an extraction error, not a completed infeasibility result.
174pub(crate) fn validate_target_witness<P: Problem>(
175    target: &P,
176    solution: &P::Solution,
177    certifies_source: impl FnOnce(P::Value) -> bool,
178    message: &str,
179) -> ExtractionResult<()> {
180    let value = validate_target_solution(target, solution)?;
181    if !certifies_source(value) {
182        return Err(ExtractionError::invalid(message));
183    }
184    Ok(())
185}
186
187/// Result of reducing a source problem to a target problem.
188///
189/// This trait encapsulates the target problem and provides methods
190/// to extract solutions back to the source problem space.
191/// Construction must preserve existence: a feasible source has a feasible target.
192/// Consequently, established target infeasibility implies source infeasibility,
193/// without a witness or an aggregate-value mapping.
194pub trait ReductionResult {
195    /// The source problem type.
196    type Source: Problem;
197    /// The target problem type.
198    type Target: Problem;
199
200    /// Get a reference to the target problem.
201    fn target_problem(&self) -> &Self::Target;
202
203    /// Extract a solution from target problem space to source problem space.
204    ///
205    /// # Arguments
206    /// * `target_solution` - A solution to the target problem
207    ///
208    /// # Returns
209    /// The corresponding solution in the source problem space
210    fn extract_solution(
211        &self,
212        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
213    ) -> ExtractionResult<<Self::Source as crate::traits::Problem>::Solution>;
214}
215
216/// Trait for problems that can be reduced to target type T.
217///
218/// # Example
219/// ```text
220/// // Example showing reduction workflow
221/// use problemreductions::prelude::*;
222/// use problemreductions::rules::ReduceTo;
223///
224/// let sat_problem: Satisfiability = Satisfiability::new(
225///     3,  // 3 variables
226///     vec![
227///         CNFClause::new(vec![0, 1]),     // (x0 OR x1)
228///         CNFClause::new(vec![1, 2]),     // (x1 OR x2)
229///     ]
230/// );
231///
232/// // Reduce to Independent Set
233/// let reduction = sat_problem.reduce_to().expect("reduction should succeed");
234/// let is_problem = reduction.target_problem();
235///
236/// // Solve and extract solutions
237/// let solver = BruteForce::new();
238/// let solutions = solver.find_all_witnesses(is_problem).unwrap();
239/// let sat_solutions: Vec<_> = solutions.iter()
240///     .map(|s| reduction.extract_solution(s))
241///     .collect();
242/// ```
243pub trait ReduceTo<T: Problem>: Problem {
244    /// The reduction result type.
245    type Result: ReductionResult<Source = Self, Target = T>;
246
247    /// Attach this reduction edge to a target-construction failure.
248    fn target_construction(error: crate::registry::ConstructionError) -> ReductionError
249    where
250        Self: Sized,
251    {
252        ReductionError::construction::<Self, T>(error)
253    }
254
255    /// Convert a structural count used by the target's exact integer algebra.
256    fn exact_i64(value: usize, operation: impl Into<String>) -> Result<i64, ReductionError>
257    where
258        Self: Sized,
259    {
260        i64::try_from(value).map_err(|_| ReductionError::integer_overflow::<Self, T>(operation))
261    }
262
263    /// Reduce this problem to the target problem type.
264    fn reduce_to(&self) -> Result<Self::Result, ReductionError>;
265}
266
267/// Result of reducing a source problem to a target problem for aggregate values.
268///
269/// Unlike [`ReductionResult`], this trait maps aggregate values back from target
270/// space to source space instead of mapping witness configurations.
271pub trait AggregateReductionResult {
272    /// The source problem type.
273    type Source: Problem;
274    /// The target problem type.
275    type Target: Problem;
276
277    /// Get a reference to the target problem.
278    fn target_problem(&self) -> &Self::Target;
279
280    /// Extract an aggregate value from target problem space back to source space.
281    ///
282    /// The caller supplies the completed target aggregate: an exact optimum,
283    /// exhaustive YES/NO, count, or universal fold. Evaluating one candidate is
284    /// not a substitute for that aggregate when establishing NO or optimality.
285    /// A decision rule may also use its map to certify a candidate witness.
286    /// Each rule defines its own map;
287    /// source and target value types alone do not establish equivalence.
288    fn extract_value(
289        &self,
290        target_value: <Self::Target as crate::traits::Problem>::Value,
291    ) -> <Self::Source as crate::traits::Problem>::Value;
292}
293
294/// Trait for problems that can be reduced to target type T for aggregate-value
295/// workflows.
296pub trait ReduceToAggregate<T: Problem>: Problem {
297    /// The reduction result type.
298    type Result: AggregateReductionResult<Source = Self, Target = T>;
299
300    /// Reduce this problem to the target problem type.
301    fn reduce_to_aggregate(&self) -> Result<Self::Result, ReductionError>;
302}
303
304/// Reduction result for an explicit conversion between variants of one model.
305///
306/// The target witness is also the source witness.
307#[derive(Debug, Clone)]
308pub struct VariantReductionResult<S: Problem, T: Problem> {
309    target: T,
310    _phantom: PhantomData<S>,
311}
312
313impl<S: Problem, T: Problem> VariantReductionResult<S, T> {
314    /// Store the constructed target variant.
315    pub fn new(target: T) -> Self {
316        Self {
317            target,
318            _phantom: PhantomData,
319        }
320    }
321}
322
323impl<S, T> ReductionResult for VariantReductionResult<S, T>
324where
325    S: Problem,
326    T: Problem<Solution = S::Solution>,
327    S::Solution: Clone,
328{
329    type Source = S;
330    type Target = T;
331
332    fn target_problem(&self) -> &Self::Target {
333        &self.target
334    }
335
336    fn extract_solution(&self, target_solution: &T::Solution) -> ExtractionResult<S::Solution> {
337        validate_target_solution(self.target_problem(), target_solution)?;
338        Ok(target_solution.clone())
339    }
340}
341
342impl<S: Problem, T: Problem<Value = S::Value>> AggregateReductionResult
343    for VariantReductionResult<S, T>
344{
345    type Source = S;
346    type Target = T;
347
348    fn target_problem(&self) -> &Self::Target {
349        &self.target
350    }
351
352    fn extract_value(&self, target_value: T::Value) -> S::Value {
353        target_value
354    }
355}
356
357/// Type-erased reduction result for runtime-discovered paths.
358///
359/// Implemented automatically for all `ReductionResult` types via blanket impl.
360/// Used internally by `ReductionChain`.
361pub trait DynReductionResult {
362    /// Borrow the executed concrete result, including its optional value mapping.
363    fn as_any(&self) -> &dyn Any;
364    /// Get the target problem as a type-erased reference.
365    fn target_problem_any(&self) -> &dyn Any;
366    /// Extract a solution from target space to source space.
367    fn extract_solution_dyn(&self, target_solution: &dyn Any) -> ExtractionResult<Box<dyn Any>>;
368    /// Serialize a source-space solution after the complete extraction chain.
369    fn source_solution_json(
370        &self,
371        source_solution: &dyn Any,
372    ) -> ExtractionResult<serde_json::Value>;
373    /// Deserialize the concrete target witness at the dynamic boundary.
374    fn target_solution_from_json(
375        &self,
376        target_solution: serde_json::Value,
377    ) -> ExtractionResult<Box<dyn Any>>;
378}
379
380impl<R: ReductionResult + 'static> DynReductionResult for R
381where
382    R::Target: 'static,
383    <R::Target as Problem>::Solution: 'static,
384    <R::Target as Problem>::Solution: serde::de::DeserializeOwned,
385    <R::Source as Problem>::Solution: 'static,
386    <R::Source as Problem>::Solution: serde::Serialize,
387{
388    fn as_any(&self) -> &dyn Any {
389        self
390    }
391    fn target_problem_any(&self) -> &dyn Any {
392        self.target_problem() as &dyn Any
393    }
394    fn extract_solution_dyn(&self, target_solution: &dyn Any) -> ExtractionResult<Box<dyn Any>> {
395        let target_solution = target_solution
396            .downcast_ref::<<R::Target as Problem>::Solution>()
397            .ok_or_else(|| {
398                ExtractionError::invalid(format!(
399                    "target solution type mismatch: expected {}",
400                    std::any::type_name::<<R::Target as Problem>::Solution>()
401                ))
402            })?;
403        self.extract_solution(target_solution)
404            .map(|solution| Box::new(solution) as Box<dyn Any>)
405            .map_err(|error| error.for_reduction::<R::Source, R::Target>())
406    }
407
408    fn source_solution_json(
409        &self,
410        source_solution: &dyn Any,
411    ) -> ExtractionResult<serde_json::Value> {
412        let source_solution = source_solution
413            .downcast_ref::<<R::Source as Problem>::Solution>()
414            .ok_or_else(|| ExtractionError::invalid("source solution type mismatch"))?;
415        serde_json::to_value(source_solution).map_err(|error| {
416            ExtractionError::invalid(format!("source solution serialization failed: {error}"))
417        })
418    }
419
420    fn target_solution_from_json(
421        &self,
422        target_solution: serde_json::Value,
423    ) -> ExtractionResult<Box<dyn Any>> {
424        serde_json::from_value::<<R::Target as Problem>::Solution>(target_solution)
425            .map(|solution| Box::new(solution) as Box<dyn Any>)
426            .map_err(|error| {
427                ExtractionError::invalid(format!("target solution deserialization failed: {error}"))
428            })
429    }
430}
431
432/// Borrow the value mapping of the same result used for witness extraction.
433pub fn aggregate_view<R>(
434    result: &dyn DynReductionResult,
435) -> ExtractionResult<&dyn DynAggregateReductionResult>
436where
437    R: DynAggregateReductionResult + 'static,
438{
439    result
440        .as_any()
441        .downcast_ref::<R>()
442        .map(|result| result as &dyn DynAggregateReductionResult)
443        .ok_or_else(|| ExtractionError::invalid("executed reduction type mismatch"))
444}
445
446/// Type-erased aggregate reduction result for runtime-discovered paths.
447pub trait DynAggregateReductionResult {
448    /// Get the target problem as a type-erased reference.
449    fn target_problem_any(&self) -> &dyn Any;
450    /// Extract an aggregate value from target space to source space.
451    fn extract_value_dyn(
452        &self,
453        target_value: serde_json::Value,
454    ) -> ExtractionResult<serde_json::Value>;
455    /// Map the value of a target solution to a serialized source aggregate.
456    /// The caller must establish that the solution realizes the target aggregate
457    /// before interpreting the result as the source aggregate.
458    fn extract_value_from_solution_dyn(
459        &self,
460        target_solution: &dyn Any,
461    ) -> ExtractionResult<serde_json::Value>;
462}
463
464impl<R: AggregateReductionResult + 'static> DynAggregateReductionResult for R
465where
466    R::Target: 'static,
467    <R::Target as Problem>::Solution: 'static,
468    <R::Target as Problem>::Value: Serialize + DeserializeOwned,
469    <R::Source as Problem>::Value: Serialize + 'static,
470{
471    fn target_problem_any(&self) -> &dyn Any {
472        self.target_problem() as &dyn Any
473    }
474
475    fn extract_value_dyn(
476        &self,
477        target_value: serde_json::Value,
478    ) -> ExtractionResult<serde_json::Value> {
479        let target_value = serde_json::from_value(target_value).map_err(|error| {
480            ExtractionError::invalid(format!("target aggregate deserialization failed: {error}"))
481        })?;
482        let source_value = self.extract_value(target_value);
483        serde_json::to_value(source_value).map_err(|error| {
484            ExtractionError::invalid(format!("source aggregate serialization failed: {error}"))
485        })
486    }
487
488    fn extract_value_from_solution_dyn(
489        &self,
490        target_solution: &dyn Any,
491    ) -> ExtractionResult<serde_json::Value> {
492        let target_solution = target_solution
493            .downcast_ref::<<R::Target as Problem>::Solution>()
494            .ok_or_else(|| {
495                ExtractionError::invalid(format!(
496                    "target solution type mismatch: expected {}",
497                    std::any::type_name::<<R::Target as Problem>::Solution>()
498                ))
499            })?;
500        let target_value = self.target_problem().evaluate(target_solution)?;
501        serde_json::to_value(self.extract_value(target_value)).map_err(|error| {
502            ExtractionError::invalid(format!("source aggregate serialization failed: {error}"))
503        })
504    }
505}
506
507#[cfg(test)]
508#[path = "../unit_tests/rules/traits.rs"]
509pub(crate) mod tests;
problemreductions/rules/traits.rs

problemreductions/rules/
traits.rs
