# nifty
A crate for generating Deterministic Finite State Automata in Rust.  

## Description

The goal of this crate is not to be an efficient parsing library. Use a regex for that.  
Rather, this crate aims to preserve the integrity of stepping through a DFA state diagram.   

It allows you to build a DFA with states of a generic type `S` that recognizes a language
whose symbols are of a generic type `T`. You can traverse each transition symbol one by one, or you can 
consume an iterator of symbols, which the DFA will either `Accept` or `Reject`.

DFAs are created using a `DFABuilder`, or by using the `make_dfa!` macro.
Both methods ensure that the DFA has valid transitions for every symbol in its alphabet.

## Examples

### Building a DFA

![example](images/example.png)

**Code**
```rust
use nifty::make_dfa;

fn main() {
    let q0 = "q0";
    let q1 = "q1";
    let q2 = "q2";
    let q3 = "q3";

    let mut dfa = make_dfa! {
        states { q0, q1, q2, q3 }
        accept { q0, q1 }
        start  { q0 }
        dead   { q3 }
        transitions {
            d(q0, 'a') = q1
            d(q0, 'b') = q3

            d(q1, 'a') = q1
            d(q1, 'b') = q2

            d(q2, 'a') = q1
            d(q2, 'b') = q2
        }
        recognizes { 
            "empty, or starts and ends with { a }"
        }
    };

    dbg!(&dfa);

    dbg!(dfa.evaluate("".chars()));
    dbg!(dfa.evaluate("a".chars()));
    dbg!(dfa.evaluate("b".chars()));
    dbg!(dfa.evaluate("aa".chars()));
    dbg!(dfa.evaluate("ab".chars()));
    dbg!(dfa.evaluate("abb".chars()));
    dbg!(dfa.evaluate("aba".chars()));
    dbg!(dfa.evaluate("abba".chars()));
    dbg!(dfa.evaluate("babba".chars()));
}
```

**Output**
```
[src/lib.rs:82] &dfa = DFA {
    recognizes: "empty, or starts and ends with { a }",
    states: {
        "q0",
        "q1",
        "q2",
        "q3",
    },
    accept_states: {
        "q0",
        "q1",
    },
    dead_states: {
        "q3",
    },
    goal_states: {},
    transitions: {
        'a': {
            "q0": "q1",
            "q1": "q1",
            "q2": "q1",
        },
        'b': {
            "q0": "q3",
            "q1": "q2",
            "q2": "q2",
        },
    },
    start: Some(
        "q0",
    ),
    current: "q0",
}


[src/main.rs:28] dfa.evaluate("".chars()) = Accept
[src/main.rs:29] dfa.evaluate("a".chars()) = Accept
[src/main.rs:30] dfa.evaluate("b".chars()) = Reject
[src/main.rs:31] dfa.evaluate("aa".chars()) = Accept
[src/main.rs:32] dfa.evaluate("ab".chars()) = Reject
[src/main.rs:33] dfa.evaluate("abb".chars()) = Reject
[src/main.rs:34] dfa.evaluate("aba".chars()) = Accept
[src/main.rs:35] dfa.evaluate("abba".chars()) = Accept
[src/main.rs:36] dfa.evaluate("babba".chars()) = Reject
```

### Tracing a Path

![example](images/example2.png)

**Code**
```rust
use nifty::make_dfa;

fn main() {
    let q0 = "Seen { }";
    let q1 = "Seen { b }";
    let q2 = "Seen { ba }";
    let q3 = "Seen { bab }";

    let mut dfa = make_dfa! {
        states { q0, q1, q2, q3 }
        start  { q0 }
        goal   { q3 }
        transitions {
            d(q0, 'a') = q0
            d(q1, 'a') = q2
            d(q2, 'a') = q0

            d(q0, 'b') = q1
            d(q1, 'b') = q1
            d(q2, 'b') = q3
        }
        recognizes {
            "contains { bab }"
        }
    };  

    let path = "abaababa".chars()
        .map(|c| (c, dfa.get_next(&c)))
        .collect::<Vec<_>>();

    for tuple in &path {
        println!("{:?}", tuple);
    }   
}
```

**Output**
```text
('a', "Seen { }")
('b', "Seen { b }")
('a', "Seen { ba }")
('a', "Seen { }")
('b', "Seen { b }")
('a', "Seen { ba }")
('b', "Seen { bab }")
('a', "Seen { bab }")
```