# Statifier - SCXML State Machines for Elixir
[](https://github.com/riddler/statifier/actions/workflows/ci.yml)
[](https://codecov.io/gh/riddler/statifier)
[](https://hex.pm/packages/statifier)
[](https://hexdocs.pm/statifier/)
> ⚠️ **Active Development Notice**
> This project is still under active development and things may change even though it is passed version 1. APIs, features, and behaviors may evolve as we continue improving SCXML compliance and functionality.
An Elixir implementation of SCXML (State Chart XML) state charts with a focus on W3C compliance.
## Features
- ✅ **Complete SCXML Parser** - Converts XML documents to structured data with precise location tracking
- ✅ **State Chart Interpreter** - Runtime engine for executing SCXML state charts
- ✅ **Modular Validation** - Document validation with focused sub-validators for maintainability
- ✅ **Compound States** - Support for hierarchical states with automatic initial child entry
- ✅ **Initial State Elements** - Full support for `<initial>` elements with transitions (W3C compliant)
- ✅ **Parallel States** - Support for concurrent state regions with simultaneous execution
- ✅ **Eventless Transitions** - Automatic transitions without event attributes (W3C compliant)
- ✅ **Conditional Transitions** - Full support for `cond` attributes with expression evaluation
- ✅ **Assign Elements** - Complete `<assign>` element support with location-based assignment and nested property access
- ✅ **Value Evaluation** - Non-boolean expression evaluation using Predicator v3.0 for actual data values
- ✅ **Data Model Integration** - StateChart data model with dynamic variable assignment and persistence
- ✅ **O(1) Performance** - Optimized state and transition lookups via Maps
- ✅ **Event Processing** - Internal and external event queues per SCXML specification
- ✅ **Parse → Validate → Optimize Architecture** - Clean separation of concerns
- ✅ **Feature Detection** - Automatic SCXML feature detection for test validation
- ✅ **Regression Testing** - Automated tracking of passing tests to prevent regressions
- ✅ **Git Hooks** - Pre-push validation workflow to catch issues early
- ✅ **Logging Infrastructure** - Protocol-based logging system with TestAdapter for clean test environments
- ✅ **Test Infrastructure** - Compatible with SCION and W3C test suites with integrated logging
- ✅ **Code Quality** - Full Credo compliance with proper module aliasing
- ✅ **History States** - Complete shallow and deep history state support per W3C SCXML specification
- ✅ **Multiple Transition Targets** - Support for space-separated multiple targets in transitions
## Current Status
### Working Features
- ✅ **Basic state transitions** and event-driven changes
- ✅ **Hierarchical states** with optimized O(1) state lookup and automatic initial child entry
- ✅ **Initial state elements** - Full `<initial>` element support with transitions and comprehensive validation
- ✅ **Parallel states** with concurrent execution of multiple regions and proper cross-boundary exit semantics
- ✅ **Eventless transitions** - Automatic transitions without event attributes (also called NULL transitions in SCXML spec), with cycle detection and microstep processing
- ✅ **Conditional transitions** - Full `cond` attribute support with Predicator v3.0 expression evaluation and SCXML `In()` function
- ✅ **Assign elements** - Complete `<assign>` element support with location-based assignment, nested property access, and mixed notation
- ✅ **If/Else/ElseIf conditional actions** - Complete `<if>`, `<elseif>`, `<else>` conditional execution blocks
- ✅ **Value evaluation system** - Statifier.ValueEvaluator module for non-boolean expression evaluation and data model operations
- ✅ **Enhanced expression evaluation** - Predicator v3.0 integration with deep property access and type-safe operations
- ✅ **History states** - Complete shallow and deep history state implementation with recording, restoration, and validation
- ✅ **Multiple transition targets** - Support for space-separated multiple targets (e.g., `target="state1 state2"`)
- ✅ **Enhanced parallel state exit logic** - Proper W3C SCXML exit set computation for complex parallel hierarchies
- ✅ **Transition conflict resolution** - Child state transitions take priority over ancestor transitions per W3C specification
- ✅ **SCXML-compliant processing** - Proper microstep/macrostep execution model with exit set computation and LCCA algorithms
- ✅ **Modular validation** - Refactored from 386-line monolith into focused sub-validators
- ✅ **Feature detection** - Automatic SCXML feature detection prevents false positive test results
- ✅ **SAX-based XML parsing** with accurate location tracking for error reporting
- ✅ **Performance optimizations** - O(1) state/transition lookups, optimized active configuration
- ✅ **Source field optimization** - Transitions include source state for faster event processing
- ✅ **Comprehensive logging** - Protocol-based logging system with structured metadata and test environment integration
### Planned Features
- Internal and targetless transitions
- More executable content (`<script>`, `<send>`, etc.)
- Enhanced datamodel support with more expression functions
- Enhanced validation for complex SCXML constructs
## Recent Completions
### **✅ Complete History State Support (v1.4.0)**
- **`Shallow History`** - Records and restores immediate children of parent states that contain active descendants
- **`Deep History`** - Records and restores all atomic descendant states within parent states
- **`History Tracking`** - Complete `Statifier.HistoryTracker` module with efficient MapSet operations
- **`History Validation`** - Comprehensive `Statifier.Validator.HistoryStateValidator` with W3C specification compliance
- **`History Resolution`** - Full W3C SCXML compliant history state transition resolution during interpreter execution
- **`StateChart Integration`** - History tracking integrated into StateChart lifecycle with recording before onexit actions
- **`SCION Test Coverage`** - Major improvement in SCION history test compliance (5/8 tests now passing)
### **✅ Multiple Transition Target Support (v1.4.0)**
- **`Space-Separated Parsing`** - Handles `target="state1 state2 state3"` syntax with proper whitespace splitting
- **`API Enhancement`** - `Statifier.Transition.targets` field (list) replaces `target` field (string) for better readability
- **`Validator Updates`** - All transition validators updated for list-based target validation with comprehensive testing
- **`Parallel State Fixes`** - Critical parallel state exit logic improvements with proper W3C SCXML exit set computation
- **`SCION Compatibility`** - history4b and history5 SCION tests now pass completely with multiple target support
### **✅ SCXML-Compliant Processing Engine**
- **`Microstep/Macrostep Execution`** - Implements SCXML event processing model with microstep (single transition set execution) and macrostep (series of microsteps until stable)
- **`Eventless Transitions`** - Transitions without event attributes (called NULL transitions in SCXML spec) that fire automatically upon state entry
- **`Exit Set Computation`** - Implements W3C SCXML exit set calculation algorithm for determining which states to exit during transitions
- **`LCCA Algorithm`** - Full Least Common Compound Ancestor computation for accurate transition conflict resolution and exit set calculation
- **`Cycle Detection`** - Prevents infinite loops with configurable iteration limits (100 iterations default)
- **`Parallel Region Preservation`** - Proper SCXML exit semantics for transitions within and across parallel regions
- **`Optimal Transition Set`** - SCXML-compliant transition conflict resolution where child state transitions take priority over ancestors
### **✅ Enhanced Parallel State Support**
- **`Cross-Parallel Boundaries`** - Proper exit semantics when transitions leave parallel regions
- **`Sibling State Management`** - Automatic exit of parallel siblings when transitions exit their shared parent
- **`Self-Transitions`** - Transitions within parallel regions preserve unaffected parallel regions
- **`Parallel Ancestor Detection`** - New functions for identifying parallel ancestors and region relationships
- **`Enhanced Exit Logic`** - All parallel regions properly exited when transitioning to external states
### **✅ Feature-Based Test Validation System**
- **`Statifier.FeatureDetector`** - Analyzes SCXML documents to detect used features
- **Feature validation** - Tests fail when they depend on unsupported features
- **False positive prevention** - No more "passing" tests that silently ignore unsupported features
- **Capability tracking** - Clear visibility into which SCXML features are supported
### **✅ Modular Validator Architecture**
- **`Statifier.Validator`** - Main orchestrator (from 386-line monolith)
- **`Statifier.Validator.StateValidator`** - State ID validation
- **`Statifier.Validator.TransitionValidator`** - Transition target validation
- **`Statifier.Validator.InitialStateValidator`** - All initial state constraints
- **`Statifier.Validator.ReachabilityAnalyzer`** - State reachability analysis
- **`Statifier.Validator.Utils`** - Shared utilities
### **✅ Initial State Elements**
- **Parser support** - `<initial>` elements with `<transition>` children
- **Interpreter logic** - Proper initial state entry via initial elements
- **Comprehensive validation** - Conflict detection, target validation, structure validation
- **Feature detection** - Automatic detection of initial element usage
## Future Extensions
The next major areas for development focus on expanding SCXML feature support:
### **High Priority Features**
- **Executable Content** - `<script>` elements (`<onentry>`, `<onexit>`, `<assign>` now supported!)
- **History States** - Shallow and deep history state support
### **Medium Priority Features**
- **Internal Transitions** - `type="internal"` transition support
- **Targetless Transitions** - Transitions without target for pure actions
- **Enhanced Error Handling** - Better error messages with source locations
- **Performance Benchmarking** - Establish performance baselines and optimize hot paths
## Installation
Add `statifier` to your list of dependencies in `mix.exs`:
```elixir
def deps do
[
{:statifier, "~> 1.8"}
]
end
```
## Usage
### Basic Example
```elixir
# Parse SCXML document
xml = """
<?xml version="1.0" encoding="UTF-8"?>
<scxml xmlns="http://www.w3.org/2005/07/scxml" version="1.0" initial="start">
<state id="start">
<transition event="go" target="end"/>
</state>
<state id="end"/>
</scxml>
"""
{:ok, document} = Statifier.parse(xml)
# Initialize state chart
{:ok, state_chart} = Statifier.Interpreter.initialize(document)
# Check active states
active_states = Statifier.Configuration.active_leaf_states(state_chart.configuration)
# Returns: MapSet.new(["start"])
# Send event
event = Statifier.Event.new("go")
{:ok, new_state_chart} = Statifier.Interpreter.send_event(state_chart, event)
# Check new active states
active_states = Statifier.Configuration.active_leaf_states(new_state_chart.configuration)
# Returns: MapSet.new(["end"])
```
### Eventless Transitions Example
```elixir
# Automatic transitions without events fire immediately
xml = """
<?xml version="1.0" encoding="UTF-8"?>
<scxml xmlns="http://www.w3.org/2005/07/scxml" version="1.0" initial="start">
<state id="start">
<transition target="processing"/> <!-- No event - fires automatically -->
</state>
<state id="processing">
<transition target="done" cond="ready == true"/> <!-- Conditional eventless -->
</state>
<state id="done"/>
</scxml>
"""
{:ok, document} = Statifier.parse(xml)
{:ok, state_chart} = Statifier.Interpreter.initialize(document)
# Eventless transitions processed automatically during initialization
active_states = Statifier.Configuration.active_leaf_states(state_chart.configuration)
# Returns: MapSet.new(["processing"]) - automatically moved from start
```
### Parallel States Example
```elixir
xml = """
<?xml version="1.0" encoding="UTF-8"?>
<scxml xmlns="http://www.w3.org/2005/07/scxml" version="1.0">
<parallel id="app">
<state id="ui" initial="idle">
<state id="idle">
<transition event="click" target="busy"/>
</state>
<state id="busy">
<transition event="done" target="idle"/>
</state>
</state>
<state id="network" initial="offline">
<state id="offline">
<transition event="connect" target="online"/>
</state>
<state id="online"/>
</state>
</parallel>
</scxml>
"""
{:ok, document} = Statifier.parse(xml)
{:ok, state_chart} = Statifier.Interpreter.initialize(document)
# Both parallel regions active simultaneously
active_states = Statifier.Configuration.active_leaf_states(state_chart.configuration)
# Returns: MapSet.new(["idle", "offline"])
```
### History States Example
```elixir
# SCXML with shallow and deep history states
xml = """
<?xml version="1.0" encoding="UTF-8"?>
<scxml xmlns="http://www.w3.org/2005/07/scxml" version="1.0" initial="main">
<state id="main" initial="sub1">
<!-- Shallow history - restores immediate children -->
<history id="main_hist" type="shallow">
<transition target="sub1"/> <!-- Default when no history -->
</history>
<state id="sub1">
<transition event="go" target="sub2"/>
</state>
<state id="sub2">
<transition event="go" target="sub3"/>
</state>
<state id="sub3">
<transition event="exit" target="other"/>
<transition event="back" target="main_hist"/> <!-- Restore history -->
</state>
</state>
<state id="other">
<transition event="return" target="main_hist"/> <!-- Restore to last sub-state -->
</state>
</scxml>
"""
{:ok, document} = Statifier.parse(xml)
{:ok, state_chart} = Statifier.Interpreter.initialize(document)
# Progress through states
{:ok, state_chart} = Statifier.Interpreter.send_event(state_chart, Statifier.Event.new("go"))
{:ok, state_chart} = Statifier.Interpreter.send_event(state_chart, Statifier.Event.new("go"))
# Active states: ["sub3"]
{:ok, state_chart} = Statifier.Interpreter.send_event(state_chart, Statifier.Event.new("exit"))
# Active states: ["other"] - history recorded
{:ok, state_chart} = Statifier.Interpreter.send_event(state_chart, Statifier.Event.new("return"))
# Active states: ["sub3"] - history restored!
```
### Multiple Transition Targets Example
```elixir
# SCXML with multiple target transitions
xml = """
<?xml version="1.0" encoding="UTF-8"?>
<scxml xmlns="http://www.w3.org/2005/07/scxml" version="1.0" initial="start">
<state id="start">
<!-- Multiple targets - enter multiple states simultaneously -->
<transition event="activate" target="system target1 target2"/>
</state>
<parallel id="system">
<state id="target1">
<transition event="done" target="end"/>
</state>
<state id="target2">
<transition event="done" target="end"/>
</state>
</parallel>
<state id="end"/>
</scxml>
"""
{:ok, document} = Statifier.parse(xml)
{:ok, state_chart} = Statifier.Interpreter.initialize(document)
# Send activate event - enters multiple targets
{:ok, state_chart} = Statifier.Interpreter.send_event(state_chart, Statifier.Event.new("activate"))
# Check active states - multiple states active simultaneously
active_states = Statifier.Configuration.active_leaf_states(state_chart.configuration)
# Returns: MapSet.new(["target1", "target2"]) - both targets entered
```
### Document Validation
```elixir
{:ok, document} = Statifier.parse(xml)
case Statifier.Validator.validate(document) do
{:ok, optimized_document, warnings} ->
# Document is valid and optimized, warnings are non-fatal
IO.puts("Valid document with #{length(warnings)} warnings")
# optimized_document now has O(1) lookup maps built
{:error, errors, warnings} ->
# Document has validation errors
IO.puts("Validation failed with #{length(errors)} errors")
end
```
### Assign Elements Example
```elixir
# SCXML with assign elements for dynamic data manipulation
xml = """
<?xml version="1.0" encoding="UTF-8"?>
<scxml xmlns="http://www.w3.org/2005/07/scxml" version="1.0" initial="start">
<state id="start">
<onentry>
<assign location="userName" expr="'John Doe'"/>
<assign location="counter" expr="42"/>
<assign location="user.profile.name" expr="'Jane Smith'"/>
<assign location="users['admin'].active" expr="true"/>
</onentry>
<transition target="working"/>
</state>
<state id="working">
<onentry>
<assign location="counter" expr="counter + 1"/>
<assign location="status" expr="'processing'"/>
</onentry>
<onexit>
<assign location="status" expr="'completed'"/>
</onexit>
<transition event="finish" target="done"/>
</state>
<final id="done"/>
</scxml>
"""
{:ok, document} = Statifier.parse(xml)
{:ok, state_chart} = Statifier.Interpreter.initialize(document)
# Check the data model after onentry execution
datamodel = state_chart.datamodel
# Returns: %{
# "userName" => "John Doe",
# "counter" => 43, # incremented to 43 in working state
# "user" => %{"profile" => %{"name" => "Jane Smith"}},
# "users" => %{"admin" => %{"active" => true}},
# "status" => "processing"
# }
```
### Logging and Test Environment
Statifier includes a comprehensive logging system designed for both production use and clean test environments:
```elixir
# Production logging with Elixir Logger integration
{:ok, document} = Statifier.parse(xml)
{:ok, state_chart} = Statifier.Interpreter.initialize(document, [
log_adapter: {Statifier.Logging.ElixirLoggerAdapter, []},
log_level: :info
])
# Test environment automatically uses TestAdapter (configured in test/test_helper.exs)
# for clean output and log inspection
# Using log helpers in tests
defmodule MyStateMachineTest do
use Statifier.Case # Provides logging test helpers
test "action execution with logging" do
xml = """
<scxml xmlns="http://www.w3.org/2005/07/scxml" version="1.0" initial="start">
<state id="start">
<onentry>
<log expr="'Starting process'"/>
<assign location="status" expr="'active'"/>
</onentry>
<transition event="go" target="done"/>
</state>
<state id="done"/>
</scxml>
"""
{:ok, state_chart} = test_scxml(xml, "logging test", ["start"], [
{%{"name" => "go"}, ["done"]}
])
# Assert specific log entries were created
assert_log_entry(state_chart, message_contains: "Starting process")
assert_log_entry(state_chart, level: :debug, action_type: "assign_action")
# Verify logs appear in chronological order
assert_log_order(state_chart, [
[message_contains: "Starting process"],
[action_type: "assign_action"]
])
end
end
```
**Key logging features:**
- **Clean test output**: No log pollution in test console
- **Structured metadata**: All logs include contextual information (state_id, action_type, phase)
- **Chronological storage**: Logs stored oldest-first for intuitive debugging
- **Test helpers**: `assert_log_entry()` and `assert_log_order()` for easy log verification
- **Production integration**: ElixirLoggerAdapter integrates seamlessly with existing Logger setup
## Development
### Requirements
- Elixir 1.17+
- Erlang/OTP 26+
### Setup
```bash
mix deps.get
mix compile
```
### Code Quality Workflow
The project maintains high code quality through automated checks:
```bash
# Local validation workflow (also runs via pre-push hook)
mix format # Auto-fix formatting
mix test.regression # Run critical regression tests (22 tests)
mix credo --strict # Static code analysis
mix dialyzer # Type checking
```
### Regression Testing
The project uses automated regression testing to prevent breaking existing functionality:
```bash
# Run only tests that should always pass (118 tests)
mix test.regression
# Check which tests are currently passing to update regression suite
mix test.baseline
# Install git hooks for automated validation
./scripts/setup-git-hooks.sh
```
The regression suite tracks:
- **Internal tests**: All `test/statifier/**/*_test.exs` files (707 total tests) - comprehensive edge case coverage
- **SCION tests**: Multiple passing tests including history, parallel, and conditional features
- **W3C tests**: Several passing tests with continued improvement
### Running Tests
```bash
# All internal tests (excludes SCION/W3C by default) - 707 tests
mix test
# All tests including SCION and W3C test suites
mix test --include scion --include scxml_w3
# Only regression tests (118 critical tests)
mix test.regression
# With coverage reporting
mix coveralls
# Specific test categories
mix test --include scion test/scion_tests/history/
mix test test/statifier/parser/scxml_test.exs
mix test test/statifier/history/
```
## Architecture
### Core Components
- **`Statifier.Parser.SCXML`** - SAX-based XML parser with location tracking (parse phase)
- **`Statifier.Validator`** - Modular validation orchestrator with focused sub-validators (validate + optimize phases)
- **`Statifier.Validator.HistoryStateValidator`** - Dedicated validator for history state constraints and W3C compliance
- **`Statifier.FeatureDetector`** - SCXML feature detection for test validation and capability tracking
- **`Statifier.Interpreter`** - Synchronous state chart interpreter with compound state and history support
- **`Statifier.StateChart`** - Runtime container with event queues and history tracking
- **`Statifier.HistoryTracker`** - Core history state tracking with efficient MapSet operations
- **`Statifier.Configuration`** - Active state management (leaf states only)
- **`Statifier.Event`** - Event representation with origin tracking
### Data Structures
- **`Statifier.Document`** - Root SCXML document with states, metadata, O(1) lookup maps, and history helper functions
- **`Statifier.State`** - Individual states with transitions, hierarchical nesting, and history type support
- **`Statifier.Transition`** - State transitions with events and multiple targets (list-based)
- **`Statifier.Data`** - Datamodel elements with expressions
### Architecture Flow
```elixir
# 1. Parse: XML → Document structure
{:ok, document} = Statifier.parse(xml)
# 2. Validate: Check semantics + optimize with lookup maps
{:ok, optimized_document, warnings} = Statifier.Validator.validate(document)
# 3. Interpret: Run state chart with optimized lookups
{:ok, state_chart} = Statifier.Interpreter.initialize(optimized_document)
```
## Performance Optimizations
The implementation includes several key optimizations for production use:
### **O(1) State and Transition Lookups**
- **State Lookup Map**: `%{state_id => state}` for instant state access
- **Transition Lookup Map**: `%{state_id => [transitions]}` for fast transition queries
- **Built During Validation**: Lookup maps only created for valid documents
- **Memory Efficient**: Uses existing document structure, no duplication
### **Compound and Parallel State Entry**
```elixir
# Automatic hierarchical entry
{:ok, state_chart} = Statifier.Interpreter.initialize(document)
active_states = Statifier.Configuration.active_leaf_states(state_chart.configuration)
# Returns only leaf states (compound/parallel states entered automatically)
# Fast ancestor computation when needed
ancestors = Statifier.Configuration.all_active_states(state_chart.configuration, state_chart.document)
# O(1) state lookups + O(d) ancestor traversal
# Parallel states enter ALL child regions simultaneously
# Compound states enter initial child recursively
```
### **Parse → Validate → Optimize Flow**
- **Separation of Concerns**: Parser focuses on structure, validator on semantics
- **Conditional Optimization**: Only builds lookup maps for valid documents
- **Future-Proof**: Supports additional parsers (JSON, YAML) with same validation
**Performance Impact:**
- O(1) vs O(n) state lookups during interpretation
- O(1) vs O(n) transition queries for event processing
- Source field optimization eliminates expensive lookups during event processing
- Critical for responsive event processing in complex state charts
## Regression Testing System
The project includes a sophisticated regression testing system to ensure stability:
### **Test Registry** (`test/passing_tests.json`)
```json
{
"internal_tests": ["test/statifier_test.exs", "test/statifier/**/*_test.exs"],
"scion_tests": ["test/scion_tests/basic/basic0_test.exs", ...],
"w3c_tests": []
}
```
### **Wildcard Support**
- Supports glob patterns like `test/statifier/**/*_test.exs`
- Automatically expands to all matching test files
- Maintains clean, maintainable test registry
### **CI Integration**
- Regression tests run before full test suite in CI
- Prevents merging code that breaks core functionality
- Fast feedback loop (63 tests vs 444 total tests)
### **Local Development**
```bash
# Check current regression status
mix test.regression
# Update regression baseline after adding features
mix test.baseline
# Manually add newly passing tests to test/passing_tests.json
# Pre-push hook automatically runs regression tests
git push origin feature-branch
```
## Contributing
1. Fork the repository
2. Create a feature branch (`git checkout -b feature/amazing-feature`)
3. Install git hooks: `./scripts/setup-git-hooks.sh`
4. Make your changes following the code quality workflow:
- `mix format` (auto-fix formatting)
- Add tests for new functionality
- `mix test.regression` (ensure no regressions)
- `mix credo --strict` (static analysis)
- `mix dialyzer` (type checking)
5. Update regression tests if you fix failing SCION/W3C tests:
- Run `mix test.baseline` to see current status
- Add newly passing tests to `test/passing_tests.json`
6. Ensure all CI checks pass
7. Commit your changes (`git commit -m 'Add amazing feature'`)
8. Push to the branch (pre-push hook will run automatically)
9. Open a Pull Request
### Code Style
- All code is formatted with `mix format`
- Static analysis with Credo (strict mode)
- Type checking with Dialyzer
- Comprehensive test coverage (90%+ maintained)
- Detailed documentation with `@moduledoc` and `@doc`
- Pattern matching preferred over multiple assertions in tests
- Git pre-push hook enforces validation workflow automatically
- Regression tests ensure core functionality never breaks
## License
This project is licensed under the MIT License - see the [LICENSE](LICENSE) file for details.
## Acknowledgments
- [W3C SCXML Specification](https://www.w3.org/TR/scxml/) - Official specification
- [SCION Test Suite](https://github.com/jbeard4/SCION) - Comprehensive test cases
