Universal Automaton Transposition Implementation - Phase 1 Update

Date: 2025-11-13 Status: Phase 1 COMPLETE (with architectural refinement)

Summary

Phase 1 successfully established the infrastructure for transposition and merge/split operations in the Universal automaton. All 156 tests pass with backward compatibility maintained.

Changes Made

1. Added State Associated Type to PositionVariant Trait

File: src/transducer/universal/position.rs:93-103

pub trait PositionVariant: Clone + fmt::Debug + PartialEq + Eq + std::hash::Hash {
    type State: Clone + fmt::Debug + PartialEq + Eq + std::hash::Hash + Default;
    fn variant_name() -> &'static str;
}

2. Defined Variant State Enums

TranspositionState (position.rs:119-133):

#[derive(Clone, Debug, PartialEq, Eq, Hash, Default)]
pub enum TranspositionState {
    #[default]
    Usual,        // Regular position i#e
    Transposing,  // Transposition state i#e_t
}

MergeSplitState (position.rs:151-165):

#[derive(Clone, Debug, PartialEq, Eq, Hash, Default)]
pub enum MergeSplitState {
    #[default]
    Usual,       // Regular position i#e
    Splitting,   // Split state i#e_s
}

3. Updated UniversalPosition Enum

File: position.rs:197-233

Changed from:

INonFinal { offset: i32, errors: u8, variant: PhantomData<V> }

To:

INonFinal { offset: i32, errors: u8, variant_state: V::State }

This allows tracking variant-specific state (Transposing, Splitting, Usual).

4. Added Constructor Methods

New constructors (position.rs:350-431):

• new_i_with_state() - Create I-type with custom variant state
• new_m_with_state() - Create M-type with custom variant state
• variant_state() - Accessor for variant state

Updated constructors:

• new_i() and new_m() now use V::State::default()

5. Architectural Decision: Generic Successor Dispatch

Key Insight: Rust doesn't allow calling methods from specialized impl blocks (impl UniversalPosition<Transposition>) when working with generic types (UniversalPosition<V>).

Solution: Keep a single generic successors() method in impl<V: PositionVariant> that:

• Currently uses standard logic for all variants
• Can be extended to check variant_state and dispatch to variant-specific logic

File: position.rs:476-491

pub fn successors(
    &self,
    bit_vector: &CharacteristicVector,
    max_distance: u8,
) -> Vec<Self> {
    match self {
        Self::INonFinal { offset, errors, .. } => {
            Self::successors_i_type_standard(*offset, *errors, bit_vector, max_distance)
        }
        Self::MFinal { offset, errors, .. } => {
            Self::successors_m_type_standard(*offset, *errors, bit_vector, max_distance)
        }
    }
}

Test Results

$ RUSTFLAGS="-C target-cpu=native" cargo test --lib universal
test result: ok. 156 passed; 0 failed; 0 ignored; 0 measured

Backward Compatibility: ✅ Fully maintained

• All existing tests pass
• Standard variant has zero overhead (() is zero-sized type)
• API changes are internal only

Next Steps for Phase 2

To implement transposition logic, the successors() method needs to be enhanced to check variant state:

pub fn successors(
    &self,
    bit_vector: &CharacteristicVector,
    max_distance: u8,
) -> Vec<Self> {
    match self {
        Self::INonFinal { offset, errors, variant_state } => {
            V::compute_i_successors(
                *offset,
                *errors,
                variant_state,
                bit_vector,
                max_distance,
            )
        }
        Self::MFinal { offset, errors, variant_state } => {
            V::compute_m_successors(
                *offset,
                *errors,
                variant_state,
                bit_vector,
                max_distance,
            )
        }
    }
}

Alternative Approach: Add trait methods to PositionVariant:

pub trait PositionVariant {
    type State: ...;
    fn variant_name() -> &'static str;

    // NEW: variant-specific successor generation
    fn compute_i_successors(
        offset: i32,
        errors: u8,
        variant_state: &Self::State,
        bit_vector: &CharacteristicVector,
        max_distance: u8,
    ) -> Vec<UniversalPosition<Self>>;
}

Files Modified

1. src/transducer/universal/position.rs
   • Lines 93-103: Updated PositionVariant trait
   • Lines 111-117: Updated Standard implementation
   • Lines 119-149: Added TranspositionState and Transposition
   • Lines 151-179: Added MergeSplitState and MergeAndSplit
   • Lines 197-233: Updated UniversalPosition enum
   • Lines 301-305, 343-347: Updated constructors
   • Lines 350-431: Added custom state constructors
   • Lines 440-445: Added variant_state() accessor
   • Lines 476-491: Generic successors() method

Lessons Learned

1. Rust's Type System: Specialized impl blocks are great for documentation and type-specific APIs, but generic code can't see them. Need trait-based dispatch or runtime type checking.

2. Zero-Cost Abstractions: Using associated types with () for Standard variant ensures zero runtime overhead.

3. Breaking Changes Are OK: Since Universal automaton hasn't been published, we can make breaking API changes to get the design right.

4. Incremental Development: Phase 1 establishes infrastructure; variant-specific logic comes in Phase 2. This allows validating the design before implementing complex logic.

Success Criteria (Phase 1)

• [x] Added State associated type to PositionVariant trait
• [x] Defined TranspositionState and MergeSplitState enums
• [x] Updated UniversalPosition to store variant state
• [x] Updated constructors
• [x] All 156 tests pass
• [x] Zero overhead for Standard variant
• [x] Backward compatibility maintained
• [x] Infrastructure ready for Phase 2

References

• Mitankin's Thesis: "Efficient Computation of Substring Equivalence Classes" (TCS 2011)
• Original implementation plan: docs/universal/transposition_implementation_plan.md
• Phase 1 completion: docs/universal/transposition_phase1_complete.md

Time Spent

• Phase 1 Infrastructure: ~3 hours
• Debugging compilation issues: ~1 hour
• Total: ~4 hours

Estimated Remaining Time for Full Implementation: 5-7 hours