problemreductions/solvers/
registry.rs

1//! Deterministic solver capabilities for exact problem variants.
2
3use crate::registry::VariantEntry;
4use crate::rules::registry::{reduction_entries, AggregateReduceFn, ReduceFn, ReductionEntry};
5use crate::rules::DynReductionResult;
6use serde::Serialize;
7use std::any::Any;
8use std::collections::{BTreeMap, BTreeSet};
9use std::sync::OnceLock;
10
11/// Canonical identity of one concrete problem variant.
12#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Serialize)]
13pub struct ExactProblemKey {
14    pub name: String,
15    pub variant: BTreeMap<String, String>,
16}
17
18impl ExactProblemKey {
19    pub fn new(name: impl Into<String>, variant: BTreeMap<String, String>) -> Self {
20        Self {
21            name: name.into(),
22            variant,
23        }
24    }
25
26    fn from_static(step: &StaticProblemStep) -> Self {
27        Self::new(
28            step.name,
29            step.variant
30                .iter()
31                .map(|&(key, value)| (key.to_string(), value.to_string()))
32                .collect(),
33        )
34    }
35
36    /// Format the key using the catalog's canonical problem notation.
37    pub fn label(&self) -> String {
38        if self.variant.is_empty() {
39            return self.name.clone();
40        }
41        let values = self
42            .variant
43            .values()
44            .cloned()
45            .collect::<Vec<_>>()
46            .join(", ");
47        format!("{}<{values}>", self.name)
48    }
49
50    fn is_supported_ilp(&self) -> bool {
51        self.name == "ILP"
52            && matches!(
53                self.variant.get("variable").map(String::as_str),
54                Some("bool" | "i64")
55            )
56            && self.variant.get("coefficient").map(String::as_str) == Some("f64")
57    }
58}
59
60/// A compile-time path node used by fixed ILP pipeline declarations.
61#[derive(Clone, Copy)]
62pub(crate) struct StaticProblemStep {
63    pub name: &'static str,
64    pub variant: &'static [(&'static str, &'static str)],
65}
66
67/// A fixed ILP pipeline declaration.
68///
69/// Every adjacent pair is resolved to one exact witness reduction while the
70/// registry is constructed. Runtime solving executes the resolved function
71/// pointers and never searches the reduction graph.
72pub(crate) struct IlpPipelineRegistration {
73    pub(crate) path: &'static [StaticProblemStep],
74}
75
76inventory::collect!(IlpPipelineRegistration);
77
78type CustomizedSolveFn = fn(&dyn Any) -> Result<Option<serde_json::Value>, super::SolveError>;
79
80/// A dedicated solver registered for one exact problem variant.
81#[derive(Debug)]
82pub(crate) struct CustomizedSolverRegistration {
83    pub(crate) source_name: &'static str,
84    pub(crate) source_variant_fn: fn() -> Vec<(&'static str, &'static str)>,
85    pub(crate) implementation: &'static str,
86    pub(crate) solve_fn: CustomizedSolveFn,
87}
88
89impl CustomizedSolverRegistration {
90    fn source_key(&self) -> ExactProblemKey {
91        ExactProblemKey::new(
92            self.source_name,
93            (self.source_variant_fn)()
94                .into_iter()
95                .map(|(key, value)| (key.to_string(), value.to_string()))
96                .collect(),
97        )
98    }
99}
100
101inventory::collect!(CustomizedSolverRegistration);
102
103#[derive(Debug)]
104pub(crate) struct CompiledIlpPipeline {
105    path: Vec<ExactProblemKey>,
106    reducers: Vec<(ReduceFn, Option<AggregateReduceFn>)>,
107}
108
109impl CompiledIlpPipeline {
110    pub(crate) fn path(&self) -> &[ExactProblemKey] {
111        &self.path
112    }
113
114    pub(crate) fn path_labels(&self) -> Vec<String> {
115        self.path.iter().map(ExactProblemKey::label).collect()
116    }
117
118    fn solve_with<R>(
119        &self,
120        source: &dyn Any,
121        solver: &super::ILPSolver,
122        finish: impl FnOnce(
123            Box<dyn Any>,
124            Option<&dyn DynReductionResult>,
125        ) -> Result<R, super::ILPSolveError>,
126    ) -> Result<R, super::ILPSolveError> {
127        if self.reducers.is_empty() {
128            return finish(Box::new(solver.solve_dyn(source)?), None);
129        }
130
131        let mut reductions: Vec<Box<dyn DynReductionResult>> = Vec::new();
132        for (reducer, _) in &self.reducers {
133            let input = reductions
134                .last()
135                .map(|step| step.target_problem_any())
136                .unwrap_or(source);
137            reductions.push(reducer(input)?);
138        }
139
140        let target = reductions
141            .last()
142            .expect("non-empty fixed pipeline must produce a target")
143            .target_problem_any();
144        let solution = solver.solve_dyn(target)?;
145        let mut source_solution: Box<dyn Any> = Box::new(solution);
146        for (index, step) in reductions.iter().enumerate().rev() {
147            if let Some(reduce) = self.reducers[index].1 {
148                let input = if index == 0 {
149                    source
150                } else {
151                    reductions[index - 1].target_problem_any()
152                };
153                let aggregate = reduce(input)?;
154                // A numerical target optimum can establish YES through a source witness,
155                // but a missed threshold alone cannot establish NO.
156                let value = aggregate.extract_value_from_solution_dyn(source_solution.as_ref())?;
157                if value.downcast_ref::<crate::types::Or>() == Some(&crate::types::Or(false)) {
158                    return Err(super::ILPSolveError::UnresolvedDecision(
159                        self.path[index].label(),
160                    ));
161                }
162            }
163            source_solution = step.extract_solution_dyn(source_solution.as_ref())?;
164        }
165        finish(source_solution, Some(reductions[0].as_ref()))
166    }
167
168    pub(crate) fn solve(
169        &self,
170        source: &dyn Any,
171        solver: &super::ILPSolver,
172    ) -> Result<serde_json::Value, super::ILPSolveError> {
173        self.solve_with(source, solver, |solution, first_reduction| {
174            if let Some(reduction) = first_reduction {
175                return reduction
176                    .source_solution_json(solution.as_ref())
177                    .map_err(super::ILPSolveError::from);
178            }
179            Ok(serde_json::to_value(
180                *solution
181                    .downcast::<Vec<i64>>()
182                    .expect("ILP backend returned the wrong solution type"),
183            )
184            .expect("ILP solution serialization failed"))
185        })
186    }
187
188    pub(crate) fn solve_typed<S: 'static>(
189        &self,
190        source: &dyn Any,
191        solver: &super::ILPSolver,
192    ) -> Result<S, super::ILPSolveError> {
193        self.solve_with(source, solver, |solution, _| {
194            solution
195                .downcast::<S>()
196                .map(|solution| *solution)
197                .map_err(|_| {
198                    super::ILPSolveError::PipelineTypeMismatch(
199                        self.path
200                            .first()
201                            .expect("compiled pipeline has a source")
202                            .label(),
203                    )
204                })
205        })
206    }
207}
208
209#[derive(Clone, Copy)]
210pub(crate) struct RegisteredSolverCapabilities<'a> {
211    pub(crate) customized: Option<&'static CustomizedSolverRegistration>,
212    pub(crate) ilp: Option<&'a CompiledIlpPipeline>,
213    pub(crate) brute_force: Option<&'static super::BruteForceRegistration>,
214}
215
216impl std::fmt::Debug for RegisteredSolverCapabilities<'_> {
217    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
218        f.debug_struct("SolverCapabilities")
219            .field(
220                "customized",
221                &self.customized.map(|entry| entry.implementation),
222            )
223            .field("ilp", &self.ilp.map(CompiledIlpPipeline::path))
224            .field("brute_force", &self.brute_force.is_some())
225            .finish()
226    }
227}
228
229/// Read-only metadata for a registered customized solver.
230#[derive(Clone, Debug, PartialEq, Eq, Serialize)]
231pub struct CustomizedSolverCapability {
232    pub implementation: &'static str,
233}
234
235/// Read-only metadata for a registered fixed ILP pipeline.
236#[derive(Clone, Debug, PartialEq, Eq, Serialize)]
237pub struct IlpSolverCapability {
238    path: Vec<ExactProblemKey>,
239}
240
241impl IlpSolverCapability {
242    pub fn path(&self) -> &[ExactProblemKey] {
243        &self.path
244    }
245
246    pub fn path_labels(&self) -> Vec<String> {
247        self.path.iter().map(ExactProblemKey::label).collect()
248    }
249}
250
251/// Read-only solver capabilities for one exact problem variant.
252#[derive(Clone, Debug, PartialEq, Eq, Serialize)]
253pub struct SolverCapabilities {
254    pub customized: Option<CustomizedSolverCapability>,
255    pub ilp: Option<IlpSolverCapability>,
256    pub brute_force: bool,
257}
258
259#[derive(Debug, Default)]
260pub(crate) struct SolverCapabilityRegistry {
261    customized: BTreeMap<ExactProblemKey, &'static CustomizedSolverRegistration>,
262    ilp: BTreeMap<ExactProblemKey, CompiledIlpPipeline>,
263    brute_force: BTreeMap<ExactProblemKey, &'static super::BruteForceRegistration>,
264}
265
266impl SolverCapabilityRegistry {
267    pub(crate) fn lookup(&self, key: &ExactProblemKey) -> RegisteredSolverCapabilities<'_> {
268        RegisteredSolverCapabilities {
269            customized: self.customized.get(key).copied(),
270            ilp: self.ilp.get(key),
271            brute_force: self.brute_force.get(key).copied(),
272        }
273    }
274}
275
276#[derive(Debug, thiserror::Error)]
277pub enum RegistryBuildError {
278    #[error("solver registration references unknown exact variant {0}")]
279    UnknownVariant(String),
280    #[error("duplicate customized solver registration for {0}")]
281    DuplicateCustomized(String),
282    #[error("duplicate ILP pipeline registration for {0}")]
283    DuplicateIlp(String),
284    #[error("duplicate brute-force registration for {0}")]
285    DuplicateBruteForce(String),
286    #[error("exact variant {0} has no registered solver capability")]
287    MissingSolverCapability(String),
288    #[error("ILP pipeline must contain at least one node")]
289    EmptyPipeline,
290    #[error("ILP pipeline for {0} does not end at an f64-coefficient ILP")]
291    UnsupportedTarget(String),
292    #[error("ILP pipeline for {0} continues after reaching a supported ILP node")]
293    ContinuesAfterIlp(String),
294    #[error("ILP pipeline edge {source_label} -> {target_label} resolves to {matches} witness reductions")]
295    InvalidEdge {
296        source_label: String,
297        target_label: String,
298        matches: usize,
299    },
300}
301
302fn registered_variant_keys() -> BTreeSet<ExactProblemKey> {
303    inventory::iter::<VariantEntry>()
304        .map(|entry| ExactProblemKey::new(entry.name, entry.variant_map()))
305        .collect()
306}
307
308fn edge_key(entry: &ReductionEntry, source: bool) -> ExactProblemKey {
309    let (name, variant) = if source {
310        (entry.source_name, entry.source_variant())
311    } else {
312        (entry.target_name, entry.target_variant())
313    };
314    ExactProblemKey::new(
315        name,
316        variant
317            .into_iter()
318            .map(|(key, value)| (key.to_string(), value.to_string()))
319            .collect(),
320    )
321}
322
323fn build_registry(
324    variants: &BTreeSet<ExactProblemKey>,
325    customized_entries: impl IntoIterator<Item = &'static CustomizedSolverRegistration>,
326    pipeline_entries: impl IntoIterator<Item = &'static IlpPipelineRegistration>,
327    brute_force_entries: impl IntoIterator<Item = &'static super::BruteForceRegistration>,
328    reductions: &[&'static ReductionEntry],
329) -> Result<SolverCapabilityRegistry, RegistryBuildError> {
330    let mut registry = SolverCapabilityRegistry::default();
331    let mut reduction_index =
332        BTreeMap::<(ExactProblemKey, ExactProblemKey), Vec<&'static ReductionEntry>>::new();
333    for entry in reductions
334        .iter()
335        .copied()
336        .filter(|entry| entry.reduce_fn.is_some())
337    {
338        reduction_index
339            .entry((edge_key(entry, true), edge_key(entry, false)))
340            .or_default()
341            .push(entry);
342    }
343
344    for customized in customized_entries {
345        let source = customized.source_key();
346        if !variants.contains(&source) {
347            return Err(RegistryBuildError::UnknownVariant(source.label()));
348        }
349        if registry
350            .customized
351            .insert(source.clone(), customized)
352            .is_some()
353        {
354            return Err(RegistryBuildError::DuplicateCustomized(source.label()));
355        }
356    }
357
358    for brute_force in brute_force_entries {
359        let source = ExactProblemKey::new(
360            brute_force.source_name,
361            crate::export::variant_to_map((brute_force.source_variant_fn)()),
362        );
363        if !variants.contains(&source) {
364            return Err(RegistryBuildError::UnknownVariant(source.label()));
365        }
366        if registry
367            .brute_force
368            .insert(source.clone(), brute_force)
369            .is_some()
370        {
371            return Err(RegistryBuildError::DuplicateBruteForce(source.label()));
372        }
373    }
374
375    for registration in pipeline_entries {
376        let path = registration
377            .path
378            .iter()
379            .map(ExactProblemKey::from_static)
380            .collect::<Vec<_>>();
381        let source = path
382            .first()
383            .cloned()
384            .ok_or(RegistryBuildError::EmptyPipeline)?;
385
386        for step in &path {
387            if !variants.contains(step) {
388                return Err(RegistryBuildError::UnknownVariant(step.label()));
389            }
390        }
391        if !path.last().is_some_and(ExactProblemKey::is_supported_ilp) {
392            return Err(RegistryBuildError::UnsupportedTarget(source.label()));
393        }
394        if path[..path.len() - 1]
395            .iter()
396            .any(ExactProblemKey::is_supported_ilp)
397        {
398            return Err(RegistryBuildError::ContinuesAfterIlp(source.label()));
399        }
400
401        let mut reducers = Vec::with_capacity(path.len().saturating_sub(1));
402        for pair in path.windows(2) {
403            let matches = reduction_index
404                .get(&(pair[0].clone(), pair[1].clone()))
405                .map(Vec::as_slice)
406                .unwrap_or_default();
407            if matches.len() != 1 {
408                return Err(RegistryBuildError::InvalidEdge {
409                    source_label: pair[0].label(),
410                    target_label: pair[1].label(),
411                    matches: matches.len(),
412                });
413            }
414            reducers.push((
415                matches[0]
416                    .reduce_fn
417                    .expect("indexed only entries with reduce_fn"),
418                matches[0].reduce_aggregate_fn,
419            ));
420        }
421
422        if registry
423            .ilp
424            .insert(source.clone(), CompiledIlpPipeline { path, reducers })
425            .is_some()
426        {
427            return Err(RegistryBuildError::DuplicateIlp(source.label()));
428        }
429    }
430
431    for variant in variants {
432        if !registry.customized.contains_key(variant)
433            && !registry.ilp.contains_key(variant)
434            && !registry.brute_force.contains_key(variant)
435        {
436            return Err(RegistryBuildError::MissingSolverCapability(variant.label()));
437        }
438    }
439
440    Ok(registry)
441}
442
443static REGISTRY: OnceLock<Result<SolverCapabilityRegistry, RegistryBuildError>> = OnceLock::new();
444
445pub(crate) fn solver_capability_registry(
446) -> Result<&'static SolverCapabilityRegistry, &'static RegistryBuildError> {
447    REGISTRY
448        .get_or_init(|| {
449            build_registry(
450                &registered_variant_keys(),
451                inventory::iter::<CustomizedSolverRegistration>(),
452                inventory::iter::<IlpPipelineRegistration>(),
453                inventory::iter::<super::BruteForceRegistration>(),
454                &reduction_entries(),
455            )
456        })
457        .as_ref()
458}
459
460/// Return read-only solver metadata for one exact problem variant.
461pub fn solver_capabilities(
462    key: &ExactProblemKey,
463) -> Result<SolverCapabilities, &'static RegistryBuildError> {
464    let registered = solver_capability_registry()?.lookup(key);
465    Ok(SolverCapabilities {
466        customized: registered
467            .customized
468            .map(|entry| CustomizedSolverCapability {
469                implementation: entry.implementation,
470            }),
471        ilp: registered.ilp.map(|pipeline| IlpSolverCapability {
472            path: pipeline.path.clone(),
473        }),
474        brute_force: registered.brute_force.is_some(),
475    })
476}
477
478pub(crate) fn brute_force_registration(
479    key: &ExactProblemKey,
480) -> Result<Option<&'static super::BruteForceRegistration>, &'static RegistryBuildError> {
481    Ok(solver_capability_registry()?.lookup(key).brute_force)
482}
483
484/// Return the finite Cartesian dimensions registered for a loaded problem.
485#[doc(hidden)]
486pub fn brute_force_dimensions(
487    problem: &crate::registry::LoadedDynProblem,
488) -> Result<Option<Vec<usize>>, &'static RegistryBuildError> {
489    let key = ExactProblemKey::new(problem.problem_name(), problem.variant_map());
490    Ok(brute_force_registration(&key)?
491        .map(|registration| (registration.dimensions_fn)(problem.as_any())))
492}
493
494#[cfg(test)]
495#[path = "../unit_tests/solvers/registry.rs"]
496mod tests;
problemreductions/solvers/registry.rs

problemreductions/solvers/
registry.rs
