Phase 2 Progress Report: Runtime-Configurable Operations

Date: 2025-11-13 Status: HISTORICAL SNAPSHOT; PHASE 2 COMPLETE AND SUPERSEDED BY PHASE 2D/3 IMPLEMENTATION

Summary

Phase 2 added runtime-configurable operation support to GeneralizedAutomaton. Later Phase 2d/3 implementation connected that infrastructure to transposition, merge, split, and restricted phonetic operations; see src/transducer/generalized/automaton.rs, src/transducer/generalized/position.rs, and src/transducer/generalized/mod.rs for the current implementation surface.

Completed Work

1. OperationSet Infrastructure ✅

Added: operations: OperationSet field to GeneralizedAutomaton

Location: src/transducer/generalized/automaton.rs:106

#[derive(Debug, Clone)]
pub struct GeneralizedAutomaton {
    /// Maximum edit distance n
    max_distance: u8,

    /// Set of operations defining the edit distance metric
    operations: OperationSet,
}

2. Constructor Methods

Default constructor - Uses standard operations:

pub fn new(max_distance: u8) -> Self {
    Self {
        max_distance,
        operations: OperationSet::standard(),
    }
}

Custom constructor - Accepts any operation set:

pub fn with_operations(max_distance: u8, operations: OperationSet) -> Self {
    Self {
        max_distance,
        operations,
    }
}

Examples:

// Standard Levenshtein (default)
let automaton = GeneralizedAutomaton::new(2);

// With transposition
let automaton = GeneralizedAutomaton::with_operations(
    2,
    OperationSet::with_transposition()
);

// Custom phonetic operations
let mut ops = OperationSet::standard();
ops.add_merge("ph", "f", 0);  // Future API
let automaton = GeneralizedAutomaton::with_operations(2, ops);

3. Validation

Test Results: All 57 existing tests pass ✅

$ cargo test --lib generalized
running 57 tests
test result: ok. 57 passed; 0 failed; 0 ignored; 0 measured

Backward Compatibility: Fully maintained

• Existing code using GeneralizedAutomaton::new() works unchanged
• Default behavior identical to Phase 1
• No breaking API changes

Architecture

Current State (Phase 2a)

GeneralizedAutomaton
  ├─ max_distance: u8
  ├─ operations: OperationSet ← NEW
  └─ Methods:
      ├─ new(max_distance) → Self
      ├─ with_operations(max_distance, operations) → Self  ← NEW
      └─ accepts(word, input) → bool

The operations field is currently stored but not yet used in successor generation.

Target State (Phase 2b)

GeneralizedAutomaton::accepts()
  └─> GeneralizedState::transition(&operations)
        └─> For each position:
              └─> For each op in operations.operations():
                    ├─ Check if op.can_apply(dict_chars, query_chars)
                    ├─ Compute successor based on op.consume_x/y/weight
                    └─ Add to next state

Next Steps

See docs/generalized/phase2_implementation_plan.md for detailed plan.

Immediate next task: Thread OperationSet through state transition methods

Phase 2b Tasks

1. Thread OperationSet (~30 min)

   • Add operations: &OperationSet parameter to GeneralizedState::transition()
   • Pass &self.operations from automaton methods

2. Refactor successor generation (~2-3 hours)

   • Replace hardcoded standard operations with iteration
   • Preserve SKIP-TO-MATCH optimization
   • Preserve out-of-window handling
   • Validate with existing tests

3. Multi-character operations (~2-3 hours)

   • Support consume_x > 1 or consume_y > 1
   • Handle transposition ⟨2, 2, 1.0⟩
   • Handle phonetic digraphs ⟨2, 1, w⟩

4. Testing (~2 hours)

   • Transposition tests
   • Phonetic operation tests
   • Cross-validation with UniversalAutomaton

5. Documentation (~1 hour)

   • Update module/struct docs
   • Add examples
   • Performance notes

Total estimated remaining time: 8-10 hours

Technical Decisions

1. Incremental Approach

Rather than a big-bang refactor, we're taking a methodical approach:

• Phase 2a: Add infrastructure, maintain compatibility ✅
• Phase 2b: Refactor single-char operations
• Phase 2c: Add multi-char operations
• Phase 2d: Testing and validation

2. Backward Compatibility

All existing code continues to work:

// This still works exactly as before
let automaton = GeneralizedAutomaton::new(2);
assert!(automaton.accepts("test", "tset"));  // Phase 1 tests pass

3. Preserve Optimizations

Critical Phase 1 optimizations must be preserved:

• SKIP-TO-MATCH: Scans ahead for next match in deletions
• Out-of-window handling: Handles input longer than word
• SmallVec: Inline position storage (≤8 positions)

4. Design Philosophy

Data-driven over hardcoded:

• Phase 1: Hardcoded standard operations
• Phase 2: Operations as data (OperationSet)
• Enables runtime composition and experimentation

Composability:

let ops = OperationSetBuilder::new()
    .with_standard_ops()
    .with_transposition()
    .with_operation(custom_phonetic_op)
    .build();

Performance Considerations

Expected Impact

Standard operations: No regression expected

• Will iterate over 4 operations instead of hardcoded branches
• Modern CPUs handle small loops efficiently
• May benefit from better instruction cache locality

Custom operations: Depends on operation count

• Transposition (5 ops): ~25% more operations, likely <10% slowdown
• Phonetic (10-20 ops): May show measurable impact
• Optimization: Sort operations by frequency/weight

Mitigation Strategies

1. Keep operation count low: Most metrics need ≤10 operations
2. Fast-path common operations: Match operation checked first
3. Inline operation checks: #[inline] on hot paths
4. Benchmark-driven: Profile before/after refactoring

Validation Strategy

At each phase:

1. Unit tests: All existing tests must pass
2. New tests: Add tests for new features
3. Cross-validation: Compare with UniversalAutomaton
4. Benchmarks: Ensure no major regressions

Files Modified

Phase 2a (Complete)

• src/transducer/generalized/automaton.rs
  • Lines 65-107: Added operations field and imports
  • Lines 128-166: Updated constructors

3. Parameter Threading ✅

Added: OperationSet parameter to GeneralizedState::transition()

Location: src/transducer/generalized/state.rs:149-154

pub fn transition(
    &self,
    _operations: &crate::transducer::OperationSet,  // NEW
    bit_vector: &CharacteristicVector,
    _input_length: usize,
) -> Option<Self>

Updated: All call sites to pass &self.operations or &automaton.operations

Locations:

• src/transducer/generalized/automaton.rs:313 - accepts() method
• src/transducer/generalized/automaton.rs:405 - test_debug_identical()
• src/transducer/generalized/automaton.rs:473 - test_debug_one_insertion()
• src/transducer/generalized/automaton.rs:577 - test_debug_deletion_middle()

Test Results: All 57 tests pass ✅

Phase 2c (Complete) ✅

Date: 2025-11-13

Goal: Replace hardcoded standard operations with dynamic OperationSet iteration

Modified files:

• src/transducer/generalized/state.rs
  • Lines 149-154: transition() - removed _ prefix from operations parameter
  • Lines 182-199: successors_standard() → successors() - added operations parameter
  • Lines 201-321: successors_i_type_standard() → successors_i_type() - refactored to iterate over operations
  • Lines 323-376: successors_m_type_standard() → successors_m_type() - refactored to iterate over operations

Key Changes:

1. Dynamic operation iteration: Replaced hardcoded if/else logic with for op in operations.operations()
2. Operation type classification: Uses op.is_match(), op.is_deletion(), op.is_insertion(), op.is_substitution()
3. Flexible weights: Uses op.weight() as u8 instead of hardcoded +1
4. Multi-char skipping: Added checks for op.consume_x() > 1 || op.consume_y() > 1 (Phase 2d)
5. Preserved optimizations: SKIP-TO-MATCH and out-of-window handling maintained

Test Results: All 57 tests pass ✅

Code Example (I-type within-window logic):

// Iterate over all operations
for op in operations.operations() {
    // Skip multi-char operations for now
    if op.consume_x() > 1 || op.consume_y() > 1 {
        continue;
    }

    if op.is_match() && has_match {
        // Generate match successor with offset unchanged
        if let Ok(succ) = GeneralizedPosition::new_i(offset, errors, self.max_distance) {
            successors.push(succ);
            return successors;  // Early return
        }
    } else if op.is_deletion() && errors < self.max_distance {
        let new_errors = errors + op.weight() as u8;
        if new_errors <= self.max_distance {
            // Delete: offset decreases
            if let Ok(succ) = GeneralizedPosition::new_i(offset - 1, new_errors, self.max_distance) {
                successors.push(succ);
            }
        }
    } else if (op.is_insertion() || op.is_substitution()) && errors < self.max_distance {
        let new_errors = errors + op.weight() as u8;
        if new_errors <= self.max_distance {
            // Insert/substitute: offset unchanged
            if let Ok(succ) = GeneralizedPosition::new_i(offset, new_errors, self.max_distance) {
                successors.push(succ);
            }
        }
    }
}

What Works Now:

• Standard operations (match, insert, delete, substitute) via OperationSet
• Custom operation weights
• Multiple operations of same type (e.g., two deletion operations with different weights)
• All Phase 1 functionality preserved

What's Next (Phase 2d):

• Remove consume_x/y > 1 check to enable transposition ⟨2,2,1⟩
• Handle multi-character matching in bit vector logic
• Add restricted operation support (can_apply() checks)

References

• OperationType: src/transducer/operation_type.rs
• OperationSet: src/transducer/operation_set.rs
• Universal automaton: src/transducer/universal/ (reference implementation)
• Mitankin's thesis: Efficient Computation of Substring Equivalence Classes (TCS 2011)

Success Criteria

Phase 2 is complete when:

• [x] OperationSet field added to GeneralizedAutomaton
• [x] Constructors support custom operation sets
• [x] All 57 original tests pass
• [x] Backward compatibility maintained
• [x] Implementation plan documented
• [x] OperationSet used in successor generation ✅ (Phase 2c complete)
• [x] Multi-character operations work (Phase 2d/3 evidence: generalized merge, split, transpose, and phonetic tests)
• [x] Transposition tests pass (Phase 2d/3 evidence: adjacent swap and distance-boundary tests)
• [x] Cross-validation succeeds for standard operations and focused phonetic cases
• [x] Documentation updated ✅

Historical Phase 2d Pause Rationale (Superseded)

At the time of this snapshot, the Universal automaton implementation and context-passing API were still stabilizing. Current code has since resolved those blockers:

1. Transposition support

   • GeneralizedPosition includes ITransposing and MTransposing states
   • GeneralizedAutomaton::with_operations(..., OperationSet::with_transposition()) accepts adjacent swaps
   • The generalized unit slice covers start, middle, end, repeated, and distance-boundary cases

2. Multi-character context support

   • Successor generation now receives word/input context for restricted operations
   • Split states retain entry_char so two-input-character phonetic operations can validate the complete pair
   • Merge, split, and transpose are covered by focused generalized tests

3. Phase 2 achievements remain valid

   • Runtime-configurable operation sets ✅
   • Dynamic operation iteration ✅
   • Custom operation weights ✅
   • Multiple operations of same type ✅
   • Full backward compatibility ✅

The historical analysis remains useful for design rationale, but it no longer describes the active implementation state.

Notes

This is foundational work for a flexible, composable edit distance system. The infrastructure is now connected to successor generation, and later reports should treat this file as a historical snapshot rather than the active implementation plan.