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

problemreductions/rules/
registry.rs
