problemreductions/rules/
registry.rs

1//! Automatic reduction registration via inventory.
2
3use crate::expr::Expr;
4use crate::parameters::{ParameterRelation, ParameterTransform, ParameterTransformError};
5use crate::rules::traits::{DynAggregateReductionResult, DynReductionResult};
6use std::any::Any;
7use std::collections::HashSet;
8
9/// One target parameter that cannot be propagated through a reduction.
10#[derive(Clone, Copy, Debug, PartialEq, Eq, serde::Serialize)]
11pub struct UnavailableParameterField {
12    pub field: &'static str,
13    pub reason: &'static str,
14}
15
16/// Raw symbolic declaration emitted by the reduction proc macro.
17#[derive(Clone, Debug, Default)]
18pub struct ReductionParameterDeclarations {
19    pub relation: Option<ParameterRelation>,
20    pub fields: Vec<(&'static str, Expr)>,
21    pub unavailable: Vec<UnavailableParameterField>,
22}
23
24/// Validated parameter metadata for one reduction edge.
25#[derive(Clone, Debug)]
26pub struct ReductionParameterContract {
27    transform: Option<ParameterTransform>,
28    unavailable: Vec<UnavailableParameterField>,
29}
30
31impl ReductionParameterContract {
32    pub fn new(
33        edge: impl Into<Box<str>>,
34        declarations: ReductionParameterDeclarations,
35    ) -> Result<Self, ParameterContractError> {
36        let edge = edge.into();
37        let formula_names: HashSet<_> = declarations
38            .fields
39            .iter()
40            .map(|(field, _)| *field)
41            .collect();
42        let mut unavailable_names = HashSet::new();
43        for unavailable in &declarations.unavailable {
44            if unavailable.reason.trim().is_empty() {
45                return Err(ParameterContractError::EmptyUnavailableReason {
46                    edge,
47                    field: unavailable.field.into(),
48                });
49            }
50            if !unavailable_names.insert(unavailable.field)
51                || formula_names.contains(unavailable.field)
52            {
53                return Err(ParameterContractError::DuplicateClassification {
54                    edge,
55                    field: unavailable.field.into(),
56                });
57            }
58        }
59        let transform = match (declarations.relation, declarations.fields.is_empty()) {
60            (Some(relation), false) => Some(ParameterTransform::new(
61                edge,
62                relation,
63                declarations.fields,
64            )?),
65            (None, true) if !declarations.unavailable.is_empty() => None,
66            (None, true) => return Err(ParameterContractError::EmptyContract { edge }),
67            (Some(_), true) => return Err(ParameterContractError::EmptyTransform { edge }),
68            (None, false) => return Err(ParameterContractError::MissingRelation { edge }),
69        };
70        Ok(Self {
71            transform,
72            unavailable: declarations.unavailable,
73        })
74    }
75
76    pub fn transform(&self) -> Option<&ParameterTransform> {
77        self.transform.as_ref()
78    }
79
80    pub fn unavailable(&self) -> &[UnavailableParameterField] {
81        &self.unavailable
82    }
83}
84
85#[derive(Clone, Debug, PartialEq, Eq)]
86pub enum ParameterContractError {
87    Transform(ParameterTransformError),
88    EmptyContract { edge: Box<str> },
89    EmptyTransform { edge: Box<str> },
90    MissingRelation { edge: Box<str> },
91    DuplicateClassification { edge: Box<str>, field: Box<str> },
92    EmptyUnavailableReason { edge: Box<str>, field: Box<str> },
93}
94
95impl std::fmt::Display for ParameterContractError {
96    fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
97        match self {
98            Self::Transform(error) => write!(formatter, "invalid parameter transform: {error}"),
99            Self::EmptyContract { edge } => write!(
100                formatter,
101                "reduction `{edge}` has no parameter formulas or unavailable fields"
102            ),
103            Self::EmptyTransform { edge } => {
104                write!(
105                    formatter,
106                    "reduction `{edge}` declares an empty parameter transform"
107                )
108            }
109            Self::MissingRelation { edge } => write!(
110                formatter,
111                "reduction `{edge}` declares parameter formulas without a relation"
112            ),
113            Self::DuplicateClassification { edge, field } => {
114                write!(
115                    formatter,
116                    "reduction `{edge}` classifies target field `{field}` more than once"
117                )
118            }
119            Self::EmptyUnavailableReason { edge, field } => write!(
120                formatter,
121                "reduction `{edge}` marks target field `{field}` unavailable without a reason"
122            ),
123        }
124    }
125}
126
127impl std::error::Error for ParameterContractError {}
128
129impl From<ParameterTransformError> for ParameterContractError {
130    fn from(error: ParameterTransformError) -> Self {
131        Self::Transform(error)
132    }
133}
134
135/// Witness/config reduction executor stored in the inventory.
136pub type ReduceFn =
137    fn(&dyn Any) -> Result<Box<dyn DynReductionResult>, crate::rules::ReductionError>;
138
139/// Aggregate/value reduction executor stored in the inventory.
140pub type AggregateReduceFn =
141    fn(&dyn Any) -> Result<Box<dyn DynAggregateReductionResult>, crate::rules::ReductionError>;
142
143/// Execution capabilities carried by a reduction edge.
144#[derive(Clone, Copy, Debug, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
145pub struct EdgeCapabilities {
146    pub witness: bool,
147    pub aggregate: bool,
148    /// Turing (multi-query) reduction: solving the source requires multiple
149    /// adaptive queries to the target (e.g., binary search over a decision bound).
150    #[serde(default)]
151    pub turing: bool,
152}
153
154impl EdgeCapabilities {
155    pub(crate) const fn from_executors(
156        reduce_fn: Option<ReduceFn>,
157        reduce_aggregate_fn: Option<AggregateReduceFn>,
158        turing: bool,
159    ) -> Self {
160        Self {
161            witness: reduce_fn.is_some(),
162            aggregate: reduce_aggregate_fn.is_some(),
163            turing,
164        }
165    }
166}
167
168/// A registered reduction entry for static inventory registration.
169/// Uses function pointers to lazily derive variant fields from `Problem::variant()`.
170pub struct ReductionEntry {
171    /// Base name of source problem (e.g., "MaximumIndependentSet").
172    pub source_name: &'static str,
173    /// Base name of target problem (e.g., "MinimumVertexCover").
174    pub target_name: &'static str,
175    /// Function to derive source variant attributes from `Problem::variant()`.
176    pub source_variant_fn: fn() -> Vec<(&'static str, &'static str)>,
177    /// Function to derive target variant attributes from `Problem::variant()`.
178    pub target_variant_fn: fn() -> Vec<(&'static str, &'static str)>,
179    /// The rule's single parameter relation, formulas, and unavailable target fields.
180    pub parameter_declarations_fn: fn() -> ReductionParameterDeclarations,
181    /// Module path where the reduction is defined (from `module_path!()`).
182    pub module_path: &'static str,
183    /// Type-erased reduction executor.
184    /// Takes a `&dyn Any` (must be `&SourceType`), calls `ReduceTo::reduce_to()`,
185    /// and returns either a boxed `DynReductionResult` or the edge's `ReductionError`.
186    pub reduce_fn: Option<ReduceFn>,
187    /// Type-erased aggregate reduction executor.
188    /// Takes a `&dyn Any` (must be `&SourceType`), calls
189    /// `ReduceToAggregate::reduce_to_aggregate()`, and returns either a boxed
190    /// `DynAggregateReductionResult` or the edge's `ReductionError`.
191    pub reduce_aggregate_fn: Option<AggregateReduceFn>,
192    /// Whether this is a Turing (multi-query) reduction.
193    pub turing: bool,
194}
195
196impl ReductionEntry {
197    pub fn parameter_contract(&self) -> Result<ReductionParameterContract, ParameterContractError> {
198        let edge: Box<str> = format!("{} -> {}", self.source_name, self.target_name).into();
199        ReductionParameterContract::new(edge, (self.parameter_declarations_fn)())
200    }
201
202    /// Get the source variant by calling the function.
203    pub fn source_variant(&self) -> Vec<(&'static str, &'static str)> {
204        (self.source_variant_fn)()
205    }
206
207    /// Get the target variant by calling the function.
208    pub fn target_variant(&self) -> Vec<(&'static str, &'static str)> {
209        (self.target_variant_fn)()
210    }
211
212    /// Return the modes backed by this entry's executors.
213    pub fn capabilities(&self) -> EdgeCapabilities {
214        EdgeCapabilities::from_executors(self.reduce_fn, self.reduce_aggregate_fn, self.turing)
215    }
216
217    /// Check if this reduction involves only the base (unweighted) variants.
218    pub fn is_base_reduction(&self) -> bool {
219        let source = self.source_variant();
220        let target = self.target_variant();
221        let source_unweighted = source
222            .iter()
223            .find(|(k, _)| *k == "weight")
224            .map(|(_, v)| *v == "One")
225            .unwrap_or(true);
226        let target_unweighted = target
227            .iter()
228            .find(|(k, _)| *k == "weight")
229            .map(|(_, v)| *v == "One")
230            .unwrap_or(true);
231        source_unweighted && target_unweighted
232    }
233}
234
235impl std::fmt::Debug for ReductionEntry {
236    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
237        f.debug_struct("ReductionEntry")
238            .field("source_name", &self.source_name)
239            .field("target_name", &self.target_name)
240            .field("source_variant", &self.source_variant())
241            .field("target_variant", &self.target_variant())
242            .field("parameter_contract", &self.parameter_contract())
243            .field("module_path", &self.module_path)
244            .field("capabilities", &self.capabilities())
245            .finish()
246    }
247}
248
249inventory::collect!(ReductionEntry);
250
251/// Return all registered reduction entries.
252pub fn reduction_entries() -> Vec<&'static ReductionEntry> {
253    inventory::iter::<ReductionEntry>().collect()
254}
255
256/// Validate reduction parameter expressions against problem-owned endpoint schemas.
257pub fn validate_reduction_parameter_schemas() -> Result<(), Vec<String>> {
258    let mut errors = Vec::new();
259
260    for entry in inventory::iter::<ReductionEntry> {
261        let source_variant = crate::export::variant_to_map(entry.source_variant());
262        let target_variant = crate::export::variant_to_map(entry.target_variant());
263        let Some(source) = crate::registry::find_variant_entry(entry.source_name, &source_variant)
264        else {
265            errors.push(format!(
266                "{} -> {} references an unregistered source variant {source_variant:?}",
267                entry.source_name, entry.target_name
268            ));
269            continue;
270        };
271        let Some(target) = crate::registry::find_variant_entry(entry.target_name, &target_variant)
272        else {
273            errors.push(format!(
274                "{} -> {} references an unregistered target variant {target_variant:?}",
275                entry.source_name, entry.target_name
276            ));
277            continue;
278        };
279
280        let source_fields = source
281            .parameter_names()
282            .iter()
283            .copied()
284            .collect::<std::collections::BTreeSet<_>>();
285        let target_fields = target
286            .parameter_names()
287            .iter()
288            .copied()
289            .collect::<std::collections::BTreeSet<_>>();
290        let declarations = (entry.parameter_declarations_fn)();
291
292        for field in declarations
293            .fields
294            .iter()
295            .flat_map(|(_, expression)| expression.variables())
296        {
297            if !source_fields.contains(field) {
298                errors.push(format!(
299                    "{} -> {} references unknown source parameter `{field}`; declared: {source_fields:?}",
300                    entry.source_name, entry.target_name
301                ));
302            }
303        }
304
305        let declared_target_fields = declarations
306            .fields
307            .iter()
308            .map(|(field, _)| *field)
309            .chain(declarations.unavailable.iter().map(|field| field.field))
310            .collect::<std::collections::BTreeSet<_>>();
311        for field in &declared_target_fields {
312            if !target_fields.contains(field) {
313                errors.push(format!(
314                    "{} -> {} declares unknown target parameter `{field}`; declared: {target_fields:?}",
315                    entry.source_name, entry.target_name
316                ));
317            }
318        }
319        for field in target_fields.difference(&declared_target_fields) {
320            errors.push(format!(
321                "{} -> {} omits target parameter `{field}`",
322                entry.source_name, entry.target_name
323            ));
324        }
325    }
326
327    if errors.is_empty() {
328        Ok(())
329    } else {
330        errors.sort();
331        Err(errors)
332    }
333}
334
335#[cfg(test)]
336#[path = "../unit_tests/rules/registry.rs"]
337mod tests;
problemreductions/rules/registry.rs

problemreductions/rules/
registry.rs
