Design Decision: Type-erased names in ReductionGraph topology

[GiggleLiu]

Context

When visualizing and querying the reduction graph, we faced an issue where generic types with different type parameters (e.g., SpinGlass<i32> vs SpinGlass<f64>) were treated as separate nodes, even though they represent the same problem class.

This caused:

1. Duplicate nodes in the visualization with identical labels
2. Path queries failing when source/target types had different weight parameters
3. Confusion about whether MaxCut<i32> -> SpinGlass<f64> is a valid reduction path

Decision

We refactored ReductionGraph to use type-erased base names for the graph topology:

• Graph nodes store base names (e.g., "SpinGlass") instead of TypeId
• Multiple concrete types map to the same node: SpinGlass<i32>, SpinGlass<f64> → "SpinGlass"
• Path finding works regardless of weight type parameters

New API

// Generic API (extracts base name internally)
graph.find_paths::<MaxCut<i32>, SpinGlass<f64>>();  // Works!
graph.has_direct_reduction::<MaxCut<i32>, SpinGlass<f64>>();  // Works!

// String-based API
graph.find_paths_by_name("MaxCut", "SpinGlass");
graph.has_direct_reduction_by_name("Factoring", "CircuitSAT");

Potential Issues

1. Loss of type-level precision

The graph no longer distinguishes between SpinGlass<i32> and SpinGlass<f64>. If a reduction only works for specific type parameters, this information is lost in the topology.

Mitigation: The actual ReduceTo trait implementations still enforce type constraints at compile time.

2. Runtime type casting not implemented

While the topology now supports cross-type queries, the actual reduction execution still requires matching types. Users might expect:

let result: SpinGlass<f64> = reduce_along_path::<MaxCut<i32>, SpinGlass<f64>>(maxcut);

But this doesn't exist yet.

Future work: Implement auto-casting in reduction execution when types are convertible (e.g., i32 -> f64).

3. Base name extraction is string-based

We rely on consistent naming in the register! macro. If someone registers:

SpinGlass<i32> => "SpinGlass",
SpinGlass<f64> => "Ising",  // Different name!

They would create separate nodes.

Mitigation: Could add compile-time checks or use a trait to derive base names.

4. KSatisfiability loses the K parameter

KSatisfiability<3, i32> becomes "KSatisfiability", losing the information that it's specifically 3-SAT.

Consideration: Should KSatisfiability<3> and KSatisfiability<4> be different nodes? Currently they're merged.

Related Commits

• cee4c8f - refactor: Use type-erased names for ReductionGraph topology
• e6a588c - fix: Unify SpinGlass types in ReductionGraph visualization

References

• PR docs: Add reduction classification and detailed survey #9: docs/reduction-classification-survey branch

[GiggleLiu]

Approaches to Extract Function/Method Tables in Rust

Rust doesn't have runtime reflection, but the compiler has full access to type information at compile time. Here are approaches to extract function signatures programmatically:

1. Rustdoc JSON Output (Recommended)

# Generate JSON documentation
RUSTC_BOOTSTRAP=1 RUSTDOCFLAGS="-Z unstable-options --output-format json" cargo doc --no-deps

# Query with jq - example: count ReduceTo implementations
cat target/doc/problemreductions.json | jq '[.index | to_entries[] | select(.value.inner.impl.trait.id? == 267)] | length'
# Output: 19

The JSON contains all public API info: functions, traits, impls, signatures, docs.

Pros: Complete API info, machine-readable
Cons: Nightly feature (needs RUSTC_BOOTSTRAP=1 on stable), complex JSON structure

2. grep/ripgrep (Simple but limited)

# Find all ReduceTo implementations
rg "impl.*ReduceTo<.*> for" --type rust -o | sort -u

Pros: Simple, works anywhere
Cons: Text-based, may miss edge cases

3. syn + quote crates (Compile-time)

Parse Rust source files programmatically:

use syn::{parse_file, Item};
let content = std::fs::read_to_string("src/lib.rs")?;
let ast = parse_file(&content)?;
for item in ast.items {
    if let Item::Impl(impl_block) = item {
        // Extract impl info
    }
}

Pros: Full AST access, precise
Cons: Requires code to parse

4. rust-analyzer LSP

Query the language server for "Find all implementations" of a trait.

Pros: IDE integration, accurate
Cons: Requires LSP setup

---

For our use case (counting/listing reduction rules), rustdoc JSON is the most complete solution. We could add a script to parse the JSON and generate summary tables for documentation.

[GiggleLiu]

@isPANN Maybe we should focus on reduction rules in this crate, then design another package, that package use rust-doc to detect the DAG, and decide potential reduction paths.

[GiggleLiu]

There is a limitation of this approach, if a user wants to extend this repo by adding new rule, it can be very hard. Is there a macro like concept in rust, such that we can automatically register when writing a function?

[GiggleLiu]

Automatic Registration via Macros

Instead of manually maintaining the reduction list in register_reductions(), we could use macros for automatic registration.

Option 1: inventory crate (Recommended)

Uses linker tricks to collect items at link time - no proc-macro crate needed:

use inventory;

pub struct ReductionEntry {
    pub source: &'static str,
    pub target: &'static str,
}

inventory::collect!(ReductionEntry);

// In each reduction module:
inventory::submit! {
    ReductionEntry { source: "IndependentSet", target: "VertexCovering" }
}

// Collect all at runtime:
impl ReductionGraph {
    fn register_all(&mut self) {
        for entry in inventory::iter::<ReductionEntry> {
            self.add_edge_by_name(entry.source, entry.target);
        }
    }
}

Pros: Simple, no proc-macro crate, distributed registration
Cons: Small runtime cost, relies on linker behavior

Option 2: Attribute macro

Create a proc-macro crate with #[register_reduction]:

#[register_reduction]
impl ReduceTo<VertexCovering<i32>> for IndependentSet<i32> {
    // ...
}

The macro extracts type names and generates inventory::submit! automatically.

Pros: Most ergonomic, type names extracted automatically
Cons: Requires separate proc-macro crate

Option 3: Build script

Parse source with syn in build.rs, find all impl ReduceTo<T> for S, generate registration code.

Pros: Zero runtime cost, compile-time only
Cons: More complex setup, must re-run on changes

---

Recommendation: Start with Option 1 (inventory) for simplicity. Upgrade to Option 2 if we want cleaner syntax.

[GiggleLiu]

Design Pattern: Strict Implementation, Flexible Usage

Rust pattern for implementing reductions on concrete types while allowing flexible usage with type conversion.

Pattern 1: Extension Trait (Recommended)

// Core trait - strict, concrete types
pub trait ReduceTo<T> {
    fn reduce_to(&self) -> ReductionResult<T>;
}

// Concrete implementation
impl ReduceTo<SpinGlass<i32>> for MaxCut<i32> {
    fn reduce_to(&self) -> ReductionResult<SpinGlass<i32>> { ... }
}

// Extension trait - adds flexible conversion
pub trait ReduceToExt<T>: ReduceTo<T> {
    fn reduce_to_as<W2>(&self) -> ReductionResult<T::WithWeight<W2>>
    where
        T: ConvertWeights<W2>;
}

// Blanket impl
impl<S, T> ReduceToExt<T> for S where S: ReduceTo<T> { ... }

// Usage: MaxCut<i32> → SpinGlass<f64>
let sg: SpinGlass<f64> = maxcut.reduce_to_as::<f64>();

Pattern 2: Free Function Wrapper

// Strict impl exists
impl ReduceTo<SpinGlass<i32>> for MaxCut<i32> { ... }

// Flexible wrapper
pub fn reduce_converting<S, T, W1, W2>(source: &S) -> T::WithWeight<W2>
where
    S: ReduceTo<T::WithWeight<W1>>,
    W2: From<W1>,
{
    source.reduce_to().convert_weights()
}

// Usage
let sg: SpinGlass<f64> = reduce_converting(&maxcut);

Pattern 3: Conversion on Problem Types

// Add weight conversion to problem types
pub trait ConvertWeights<W> {
    type Output;
    fn convert_weights(self) -> Self::Output;
}

impl<W1, W2: From<W1>> ConvertWeights<W2> for SpinGlass<W1> {
    type Output = SpinGlass<W2>;
    fn convert_weights(self) -> SpinGlass<W2> { ... }
}

// Chain: reduce then convert
let sg: SpinGlass<f64> = maxcut.reduce_to().convert_weights();

---

Recommendation: Pattern 1 (extension trait) keeps the core ReduceTo trait clean while adding a flexible ReduceToExt layer. Pattern 3 is simpler but requires manual chaining.

Note: Rust requires explicit conversions - no implicit casts. bool as i32 works, but i32 as bool requires i != 0.