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/// Result of reducing a source problem to a target problem.
172///
173/// This trait encapsulates the target problem and provides methods
174/// to extract solutions back to the source problem space.
175pub trait ReductionResult {
176    /// The source problem type.
177    type Source: Problem;
178    /// The target problem type.
179    type Target: Problem;
180
181    /// Get a reference to the target problem.
182    fn target_problem(&self) -> &Self::Target;
183
184    /// Extract a solution from target problem space to source problem space.
185    ///
186    /// # Arguments
187    /// * `target_solution` - A solution to the target problem
188    ///
189    /// # Returns
190    /// The corresponding solution in the source problem space
191    fn extract_solution(
192        &self,
193        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
194    ) -> ExtractionResult<<Self::Source as crate::traits::Problem>::Solution>;
195}
196
197/// Trait for problems that can be reduced to target type T.
198///
199/// # Example
200/// ```text
201/// // Example showing reduction workflow
202/// use problemreductions::prelude::*;
203/// use problemreductions::rules::ReduceTo;
204///
205/// let sat_problem: Satisfiability = Satisfiability::new(
206///     3,  // 3 variables
207///     vec![
208///         CNFClause::new(vec![0, 1]),     // (x0 OR x1)
209///         CNFClause::new(vec![1, 2]),     // (x1 OR x2)
210///     ]
211/// );
212///
213/// // Reduce to Independent Set
214/// let reduction = sat_problem.reduce_to().expect("reduction should succeed");
215/// let is_problem = reduction.target_problem();
216///
217/// // Solve and extract solutions
218/// let solver = BruteForce::new();
219/// let solutions = solver.find_all_witnesses(is_problem).unwrap();
220/// let sat_solutions: Vec<_> = solutions.iter()
221///     .map(|s| reduction.extract_solution(s))
222///     .collect();
223/// ```
224pub trait ReduceTo<T: Problem>: Problem {
225    /// The reduction result type.
226    type Result: ReductionResult<Source = Self, Target = T>;
227
228    /// Attach this reduction edge to a target-construction failure.
229    fn target_construction(error: crate::registry::ConstructionError) -> ReductionError
230    where
231        Self: Sized,
232    {
233        ReductionError::construction::<Self, T>(error)
234    }
235
236    /// Convert a structural count used by the target's exact integer algebra.
237    fn exact_i64(value: usize, operation: impl Into<String>) -> Result<i64, ReductionError>
238    where
239        Self: Sized,
240    {
241        i64::try_from(value).map_err(|_| ReductionError::integer_overflow::<Self, T>(operation))
242    }
243
244    /// Reduce this problem to the target problem type.
245    fn reduce_to(&self) -> Result<Self::Result, ReductionError>;
246}
247
248/// Result of reducing a source problem to a target problem for aggregate values.
249///
250/// Unlike [`ReductionResult`], this trait maps aggregate values back from target
251/// space to source space instead of mapping witness configurations.
252pub trait AggregateReductionResult {
253    /// The source problem type.
254    type Source: Problem;
255    /// The target problem type.
256    type Target: Problem;
257
258    /// Get a reference to the target problem.
259    fn target_problem(&self) -> &Self::Target;
260
261    /// Extract an aggregate value from target problem space back to source space.
262    fn extract_value(
263        &self,
264        target_value: <Self::Target as crate::traits::Problem>::Value,
265    ) -> <Self::Source as crate::traits::Problem>::Value;
266}
267
268/// Trait for problems that can be reduced to target type T for aggregate-value
269/// workflows.
270pub trait ReduceToAggregate<T: Problem>: Problem {
271    /// The reduction result type.
272    type Result: AggregateReductionResult<Source = Self, Target = T>;
273
274    /// Reduce this problem to the target problem type.
275    fn reduce_to_aggregate(&self) -> Result<Self::Result, ReductionError>;
276}
277
278/// Reduction result for an explicit conversion between variants of one model.
279///
280/// The target witness is also the source witness.
281#[derive(Debug, Clone)]
282pub struct VariantReductionResult<S: Problem, T: Problem> {
283    target: T,
284    _phantom: PhantomData<S>,
285}
286
287impl<S: Problem, T: Problem> VariantReductionResult<S, T> {
288    /// Store the constructed target variant.
289    pub fn new(target: T) -> Self {
290        Self {
291            target,
292            _phantom: PhantomData,
293        }
294    }
295}
296
297impl<S, T> ReductionResult for VariantReductionResult<S, T>
298where
299    S: Problem,
300    T: Problem<Solution = S::Solution>,
301    S::Solution: Clone,
302{
303    type Source = S;
304    type Target = T;
305
306    fn target_problem(&self) -> &Self::Target {
307        &self.target
308    }
309
310    fn extract_solution(&self, target_solution: &T::Solution) -> ExtractionResult<S::Solution> {
311        validate_target_solution(self.target_problem(), target_solution)?;
312        Ok(target_solution.clone())
313    }
314}
315
316impl<S: Problem, T: Problem<Value = S::Value>> AggregateReductionResult
317    for VariantReductionResult<S, T>
318{
319    type Source = S;
320    type Target = T;
321
322    fn target_problem(&self) -> &Self::Target {
323        &self.target
324    }
325
326    fn extract_value(&self, target_value: T::Value) -> S::Value {
327        target_value
328    }
329}
330
331/// Type-erased reduction result for runtime-discovered paths.
332///
333/// Implemented automatically for all `ReductionResult` types via blanket impl.
334/// Used internally by `ReductionChain`.
335pub trait DynReductionResult {
336    /// Get the target problem as a type-erased reference.
337    fn target_problem_any(&self) -> &dyn Any;
338    /// Extract a solution from target space to source space.
339    fn extract_solution_dyn(&self, target_solution: &dyn Any) -> ExtractionResult<Box<dyn Any>>;
340    /// Serialize a source-space solution after the complete extraction chain.
341    fn source_solution_json(
342        &self,
343        source_solution: &dyn Any,
344    ) -> ExtractionResult<serde_json::Value>;
345    /// Deserialize the concrete target witness at the dynamic boundary.
346    fn target_solution_from_json(
347        &self,
348        target_solution: serde_json::Value,
349    ) -> ExtractionResult<Box<dyn Any>>;
350}
351
352impl<R: ReductionResult + 'static> DynReductionResult for R
353where
354    R::Target: 'static,
355    <R::Target as Problem>::Solution: 'static,
356    <R::Target as Problem>::Solution: serde::de::DeserializeOwned,
357    <R::Source as Problem>::Solution: 'static,
358    <R::Source as Problem>::Solution: serde::Serialize,
359{
360    fn target_problem_any(&self) -> &dyn Any {
361        self.target_problem() as &dyn Any
362    }
363    fn extract_solution_dyn(&self, target_solution: &dyn Any) -> ExtractionResult<Box<dyn Any>> {
364        let target_solution = target_solution
365            .downcast_ref::<<R::Target as Problem>::Solution>()
366            .ok_or_else(|| {
367                ExtractionError::invalid(format!(
368                    "target solution type mismatch: expected {}",
369                    std::any::type_name::<<R::Target as Problem>::Solution>()
370                ))
371            })?;
372        self.extract_solution(target_solution)
373            .map(|solution| Box::new(solution) as Box<dyn Any>)
374            .map_err(|error| error.for_reduction::<R::Source, R::Target>())
375    }
376
377    fn source_solution_json(
378        &self,
379        source_solution: &dyn Any,
380    ) -> ExtractionResult<serde_json::Value> {
381        let source_solution = source_solution
382            .downcast_ref::<<R::Source as Problem>::Solution>()
383            .ok_or_else(|| ExtractionError::invalid("source solution type mismatch"))?;
384        serde_json::to_value(source_solution).map_err(|error| {
385            ExtractionError::invalid(format!("source solution serialization failed: {error}"))
386        })
387    }
388
389    fn target_solution_from_json(
390        &self,
391        target_solution: serde_json::Value,
392    ) -> ExtractionResult<Box<dyn Any>> {
393        serde_json::from_value::<<R::Target as Problem>::Solution>(target_solution)
394            .map(|solution| Box::new(solution) as Box<dyn Any>)
395            .map_err(|error| {
396                ExtractionError::invalid(format!("target solution deserialization failed: {error}"))
397            })
398    }
399}
400
401/// Type-erased aggregate reduction result for runtime-discovered paths.
402pub trait DynAggregateReductionResult {
403    /// Get the target problem as a type-erased reference.
404    fn target_problem_any(&self) -> &dyn Any;
405    /// Extract an aggregate value from target space to source space.
406    fn extract_value_dyn(&self, target_value: serde_json::Value) -> serde_json::Value;
407    /// Map the value of a target solution without erasing the source value's type.
408    /// The caller must establish that the solution realizes the target aggregate
409    /// before interpreting the result as the source aggregate.
410    fn extract_value_from_solution_dyn(
411        &self,
412        target_solution: &dyn Any,
413    ) -> ExtractionResult<Box<dyn Any>>;
414}
415
416impl<R: AggregateReductionResult + 'static> DynAggregateReductionResult for R
417where
418    R::Target: 'static,
419    <R::Target as Problem>::Solution: 'static,
420    <R::Target as Problem>::Value: Serialize + DeserializeOwned,
421    <R::Source as Problem>::Value: Serialize + 'static,
422{
423    fn target_problem_any(&self) -> &dyn Any {
424        self.target_problem() as &dyn Any
425    }
426
427    fn extract_value_dyn(&self, target_value: serde_json::Value) -> serde_json::Value {
428        let target_value = serde_json::from_value(target_value)
429            .expect("DynAggregateReductionResult target value deserialize failed");
430        let source_value = self.extract_value(target_value);
431        serde_json::to_value(source_value)
432            .expect("DynAggregateReductionResult source value serialize failed")
433    }
434
435    fn extract_value_from_solution_dyn(
436        &self,
437        target_solution: &dyn Any,
438    ) -> ExtractionResult<Box<dyn Any>> {
439        let target_solution = target_solution
440            .downcast_ref::<<R::Target as Problem>::Solution>()
441            .ok_or_else(|| {
442                ExtractionError::invalid(format!(
443                    "target solution type mismatch: expected {}",
444                    std::any::type_name::<<R::Target as Problem>::Solution>()
445                ))
446            })?;
447        let target_value = self.target_problem().evaluate(target_solution)?;
448        Ok(Box::new(self.extract_value(target_value)))
449    }
450}
451
452#[cfg(test)]
453#[path = "../unit_tests/rules/traits.rs"]
454mod tests;
problemreductions/rules/traits.rs

problemreductions/rules/
traits.rs
