problemreductions/solvers/
registry.rs

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

problemreductions/solvers/
registry.rs
