problemreductions/registry/
variant.rs

1//! Explicit variant registration via inventory.
2
3use std::any::Any;
4use std::collections::BTreeMap;
5
6use crate::registry::dyn_problem::{DynProblem, SolveValueFn, SolveWitnessFn};
7
8/// A registered problem variant entry.
9///
10/// Submitted by [`declare_variants!`] for each concrete problem type.
11/// The reduction graph uses these entries to build nodes with complexity metadata.
12pub struct VariantEntry {
13    /// Problem name (from `Problem::NAME`).
14    pub name: &'static str,
15    /// Function returning variant key-value pairs (from `Problem::variant()`).
16    pub variant_fn: fn() -> Vec<(&'static str, &'static str)>,
17    /// Worst-case time complexity expression (e.g., `"2^num_vertices"`).
18    pub complexity: &'static str,
19    /// Compiled complexity evaluation function.
20    /// Takes a `&dyn Any` (must be `&ProblemType`), calls getter methods directly,
21    /// and returns the estimated worst-case time as f64.
22    pub complexity_eval_fn: fn(&dyn Any) -> f64,
23    /// Whether this entry is the declared default variant for its problem.
24    pub is_default: bool,
25    /// Variant-level aliases (e.g., `&["3SAT"]` for `KSatisfiability<K3>`).
26    ///
27    /// Unlike problem-level aliases (on `ProblemSchemaEntry`), these resolve to a
28    /// specific reduction-graph node, not just to a canonical problem name. The CLI
29    /// resolver tries variant-level aliases first and falls back to problem-level.
30    pub aliases: &'static [&'static str],
31    /// Factory: deserialize JSON into a boxed dynamic problem.
32    pub factory: fn(serde_json::Value) -> Result<Box<dyn DynProblem>, serde_json::Error>,
33    /// Serialize: downcast `&dyn Any` and serialize to JSON.
34    pub serialize_fn: fn(&dyn Any) -> Option<serde_json::Value>,
35    /// Solve value: downcast `&dyn Any` and brute-force solve to an aggregate string.
36    pub solve_value_fn: SolveValueFn,
37    /// Solve witness: downcast `&dyn Any` and brute-force recover a witness when available.
38    pub solve_witness_fn: SolveWitnessFn,
39}
40
41impl VariantEntry {
42    /// Get the variant by calling the function.
43    pub fn variant(&self) -> Vec<(&'static str, &'static str)> {
44        (self.variant_fn)()
45    }
46
47    /// Get the variant as a `BTreeMap<String, String>`.
48    pub fn variant_map(&self) -> BTreeMap<String, String> {
49        self.variant()
50            .into_iter()
51            .map(|(k, v)| (k.to_string(), v.to_string()))
52            .collect()
53    }
54}
55
56/// Find a variant entry by exact problem name and exact variant map.
57///
58/// No alias resolution or default fallback. Both `name` and `variant` must match exactly.
59pub fn find_variant_entry(
60    name: &str,
61    variant: &BTreeMap<String, String>,
62) -> Option<&'static VariantEntry> {
63    inventory::iter::<VariantEntry>()
64        .find(|entry| entry.name == name && entry.variant_map() == *variant)
65}
66
67/// Find a variant entry by a variant-level alias (case-insensitive).
68///
69/// A variant-level alias points at a specific reduction-graph node (e.g., `"3SAT"` →
70/// `KSatisfiability` with variant `{k: "K3"}`), unlike problem-level aliases which
71/// resolve only to a canonical problem name.
72///
73/// Returns the matched entry along with its variant map. The first match in registration
74/// order wins — duplicate variant-level aliases across problems are a declaration bug.
75pub fn find_variant_by_alias(
76    input: &str,
77) -> Option<(&'static VariantEntry, BTreeMap<String, String>)> {
78    let lower = input.to_lowercase();
79    let entry = inventory::iter::<VariantEntry>()
80        .find(|entry| entry.aliases.iter().any(|a| a.to_lowercase() == lower))?;
81    Some((entry, entry.variant_map()))
82}
83
84/// Validate all variant-level aliases registered in inventory.
85///
86/// This is intended for explicit test-time or startup invocation. It rejects
87/// duplicate variant-level aliases, aliases that collide with canonical
88/// problem names or problem-level aliases, and empty aliases for manually
89/// constructed [`VariantEntry`] values that bypass `declare_variants!`.
90pub fn validate_variant_aliases() -> Result<(), Vec<String>> {
91    let mut problem_names: BTreeMap<String, Vec<String>> = BTreeMap::new();
92
93    for problem in super::problem_type::problem_types() {
94        problem_names
95            .entry(problem.canonical_name.to_lowercase())
96            .or_default()
97            .push(format!(
98                "canonical problem name `{}`",
99                problem.canonical_name
100            ));
101
102        for alias in problem.aliases {
103            problem_names
104                .entry(alias.to_lowercase())
105                .or_default()
106                .push(format!(
107                    "problem-level alias `{alias}` for `{}`",
108                    problem.canonical_name
109                ));
110        }
111    }
112
113    let entries: Vec<_> = inventory::iter::<VariantEntry>()
114        .map(|e| (variant_label(e), e.aliases))
115        .collect();
116
117    validate_aliases_inner(&problem_names, &entries)
118}
119
120/// Core validation logic, separated for testability with mock data.
121///
122/// - `problem_names`: lowercase key → list of human-readable sources (canonical names + problem-level aliases).
123/// - `entries`: `(variant_label, aliases_slice)` per variant entry.
124pub fn validate_aliases_inner(
125    problem_names: &BTreeMap<String, Vec<String>>,
126    entries: &[(String, &[&str])],
127) -> Result<(), Vec<String>> {
128    let mut conflicts = Vec::new();
129    let mut variant_aliases: BTreeMap<String, Vec<(String, String)>> = BTreeMap::new();
130
131    for (target, aliases) in entries {
132        for alias in *aliases {
133            if alias.trim().is_empty() {
134                conflicts.push(format!(
135                    "variant-level alias on {target} is empty or whitespace-only"
136                ));
137                continue;
138            }
139
140            let lower = alias.to_lowercase();
141            if let Some(collisions) = problem_names.get(&lower) {
142                for collision in collisions {
143                    conflicts.push(format!(
144                        "variant-level alias `{alias}` on {target} conflicts with {collision}"
145                    ));
146                }
147            }
148
149            variant_aliases
150                .entry(lower)
151                .or_default()
152                .push((alias.to_string(), target.clone()));
153        }
154    }
155
156    for (lower, registrations) in variant_aliases {
157        if registrations.len() > 1 {
158            let details = registrations
159                .iter()
160                .map(|(alias, target)| format!("`{alias}` on {target}"))
161                .collect::<Vec<_>>()
162                .join("; ");
163            conflicts.push(format!(
164                "duplicate variant-level alias `{lower}` (case-insensitive): {details}"
165            ));
166        }
167    }
168
169    if conflicts.is_empty() {
170        Ok(())
171    } else {
172        conflicts.sort();
173        Err(conflicts)
174    }
175}
176
177pub fn variant_label(entry: &VariantEntry) -> String {
178    let variant = entry.variant();
179    if variant.is_empty() {
180        return entry.name.to_string();
181    }
182
183    let parts = variant
184        .iter()
185        .map(|(key, value)| format!("{key}={value}"))
186        .collect::<Vec<_>>()
187        .join(", ");
188    format!("{} {{{parts}}}", entry.name)
189}
190
191impl std::fmt::Debug for VariantEntry {
192    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
193        f.debug_struct("VariantEntry")
194            .field("name", &self.name)
195            .field("variant", &self.variant())
196            .field("complexity", &self.complexity)
197            .finish()
198    }
199}
200
201inventory::collect!(VariantEntry);
202
203#[cfg(test)]
204#[path = "../unit_tests/registry/variant.rs"]
205mod tests;
problemreductions/registry/variant.rs

problemreductions/registry/
variant.rs
