problemreductions/
variant.rs

1//! Variant system for type-level problem parameterization.
2//!
3//! Types declare their variant category, value, and parent via `VariantParam`.
4//! The `impl_variant_param!` macro registers types with the trait.
5//! The `variant_params!` macro composes `Problem::variant()` bodies from type parameter names.
6
7/// A type that participates in the variant system.
8///
9/// Declares its category (e.g., `"graph"`), value (e.g., `"SimpleGraph"`),
10/// and optional parent in the subtype hierarchy.
11pub trait VariantParam: 'static {
12    /// Category name (e.g., `"graph"`, `"weight"`, `"k"`).
13    const CATEGORY: &'static str;
14    /// Type name within the category (e.g., `"SimpleGraph"`, `"i32"`).
15    const VALUE: &'static str;
16    /// Parent type name in the subtype hierarchy, or `None` for root types.
17    const PARENT_VALUE: Option<&'static str>;
18}
19
20/// Types that can convert themselves to their parent in the variant hierarchy.
21pub trait CastToParent: VariantParam {
22    /// The parent type.
23    type Parent: VariantParam;
24    /// Convert this value to its parent type.
25    fn cast_to_parent(&self) -> Self::Parent;
26}
27
28/// K-value marker trait for types that represent a const-generic K parameter.
29///
30/// Types implementing this trait declare an optional K value. `None` means
31/// the type represents an arbitrary K (like KN), while `Some(k)` means
32/// a specific value (like K2, K3).
33pub trait KValue: VariantParam + Clone + 'static {
34    /// The K value, or `None` for arbitrary K.
35    const K: Option<usize>;
36}
37
38/// Implement `VariantParam` (and optionally `CastToParent` and/or `KValue`) for a type.
39///
40/// # Usage
41///
42/// ```text
43/// // Root type (no parent):
44/// impl_variant_param!(SimpleGraph, "graph");
45///
46/// // Type with parent -- cast closure required:
47/// impl_variant_param!(UnitDiskGraph, "graph", parent: SimpleGraph,
48///     cast: |g| SimpleGraph::new(g.num_vertices(), g.edges()));
49///
50/// // Root K type (no parent, with K value):
51/// impl_variant_param!(KN, "k", k: None);
52///
53/// // K type with parent + cast + K value:
54/// impl_variant_param!(K3, "k", parent: KN, cast: |_| KN, k: Some(3));
55/// ```
56#[macro_export]
57macro_rules! impl_variant_param {
58    // Root type (no parent, no cast)
59    ($ty:ty, $cat:expr) => {
60        impl $crate::variant::VariantParam for $ty {
61            const CATEGORY: &'static str = $cat;
62            const VALUE: &'static str = stringify!($ty);
63            const PARENT_VALUE: Option<&'static str> = None;
64        }
65    };
66    // Type with parent + cast closure
67    ($ty:ty, $cat:expr, parent: $parent:ty, cast: $cast:expr) => {
68        impl $crate::variant::VariantParam for $ty {
69            const CATEGORY: &'static str = $cat;
70            const VALUE: &'static str = stringify!($ty);
71            const PARENT_VALUE: Option<&'static str> = Some(stringify!($parent));
72        }
73        impl $crate::variant::CastToParent for $ty {
74            type Parent = $parent;
75            fn cast_to_parent(&self) -> $parent {
76                let f: fn(&$ty) -> $parent = $cast;
77                f(self)
78            }
79        }
80    };
81    // KValue root type (no parent, with k value)
82    ($ty:ty, $cat:expr, k: $k:expr) => {
83        $crate::impl_variant_param!($ty, $cat);
84        impl $crate::variant::KValue for $ty {
85            const K: Option<usize> = $k;
86        }
87    };
88    // KValue type with parent + cast + k value
89    ($ty:ty, $cat:expr, parent: $parent:ty, cast: $cast:expr, k: $k:expr) => {
90        $crate::impl_variant_param!($ty, $cat, parent: $parent, cast: $cast);
91        impl $crate::variant::KValue for $ty {
92            const K: Option<usize> = $k;
93        }
94    };
95}
96
97/// Compose a `Problem::variant()` body from type parameter names.
98///
99/// All variant dimensions must be types implementing `VariantParam`.
100///
101/// # Usage
102///
103/// ```text
104/// variant_params![]           // -> vec![]
105/// variant_params![G, W]       // -> vec![(G::CATEGORY, G::VALUE), ...]
106/// ```
107#[macro_export]
108macro_rules! variant_params {
109    () => { vec![] };
110    ($($T:ident),+) => {
111        vec![$((<$T as $crate::variant::VariantParam>::CATEGORY,
112              <$T as $crate::variant::VariantParam>::VALUE)),+]
113    };
114}
115
116// --- Concrete KValue types ---
117
118/// K=1 (e.g., 1-coloring).
119#[derive(Clone, Copy, Debug, Default)]
120pub struct K1;
121
122/// K=2 (e.g., 2-SAT, 2-coloring).
123#[derive(Clone, Copy, Debug, Default)]
124pub struct K2;
125
126/// K=3 (e.g., 3-SAT, 3-coloring).
127#[derive(Clone, Copy, Debug, Default)]
128pub struct K3;
129
130/// K=4 (e.g., 4-coloring).
131#[derive(Clone, Copy, Debug, Default)]
132pub struct K4;
133
134/// K=5 (e.g., 5-coloring).
135#[derive(Clone, Copy, Debug, Default)]
136pub struct K5;
137
138/// Generic K (any value). Used for reductions that apply to all K.
139#[derive(Clone, Copy, Debug, Default)]
140pub struct KN;
141
142impl_variant_param!(KN, "k", k: None);
143impl_variant_param!(K5, "k", parent: KN, cast: |_| KN, k: Some(5));
144impl_variant_param!(K4, "k", parent: KN, cast: |_| KN, k: Some(4));
145impl_variant_param!(K3, "k", parent: KN, cast: |_| KN, k: Some(3));
146impl_variant_param!(K2, "k", parent: KN, cast: |_| KN, k: Some(2));
147impl_variant_param!(K1, "k", parent: KN, cast: |_| KN, k: Some(1));
148
149#[cfg(test)]
150#[path = "unit_tests/variant.rs"]
151mod tests;
problemreductions/variant.rs

problemreductions/
variant.rs
