dandy 0.1.10

Implementation of DFAs, NFAs and regular expressions together with a file format
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144

use crate::nfa::{Nfa, NfaState};
use crate::parser::{NfaAlphabetEntry, ParsedNfa, ParsedNfaState};
use std::collections::{HashMap, HashSet};
use std::ops::Not;
use std::rc::Rc;
use thiserror::Error;

#[derive(Debug, Error, PartialEq)]
pub enum NfaParseError<'a> {
    #[error("Wrong number of transitions for state '{0}': has {1} expected {2}")]
    WrongNumberOfTransitions(&'a str, usize, usize),
    #[error("State '{1}' does not exist (in transition from state '{0}')")]
    TransitionDoesNotExist(&'a str, &'a str),
    #[error("There is no initial state")]
    MissingInitialState,
    #[error("There are two (or more) initial states")]
    MultipleInitialStates,
    #[error("'{0}' appears twice in the alphabet")]
    DuplicateAlphabetSymbol(&'a str),
    #[error("State '{0}' defined multiple times")]
    DuplicateStateDefinition(&'a str),
}

impl<'a> TryFrom<ParsedNfa<'a>> for Nfa {
    type Error = NfaParseError<'a>;

    fn try_from(value: ParsedNfa<'a>) -> Result<Self, Self::Error> {
        use NfaParseError::*;
        let ParsedNfa { head, states } = value;

        let mut eps_idx = None;
        {
            let mut alphabet = HashSet::new();
            head.iter()
                .enumerate()
                .try_for_each(|(idx, e)| match e {
                    NfaAlphabetEntry::Element(c) => alphabet.insert(c).then_some(()).ok_or(c),
                    NfaAlphabetEntry::Eps => {
                        if eps_idx.is_some() {
                            Err(&"ε")
                        } else {
                            eps_idx = Some(idx);
                            Ok(())
                        }
                    }
                })
                .map_err(|e| DuplicateAlphabetSymbol(e))?
        }

        let state_name_map: HashMap<_, _> = states
            .iter()
            .enumerate()
            .map(|(i, s)| (s.name, i))
            .collect();

        if state_name_map.len() != states.len() {
            // We have a duplicate name, let's find it!
            let mut seen = HashSet::new();
            let duplicate = states
                .iter()
                .find_map(|s| seen.insert(s.name).not().then_some(s.name))
                .unwrap_or("<unknown>");
            return Err(DuplicateStateDefinition(duplicate));
        }

        let mut initial_state = None;

        let mut new_states = Vec::with_capacity(states.len());
        for (idx, state) in states.into_iter().enumerate() {
            let ParsedNfaState {
                name,
                initial,
                accepting,
                transitions,
            } = state;

            if transitions.len() != head.len() {
                return Err(WrongNumberOfTransitions(
                    name,
                    transitions.len(),
                    head.len(),
                )); // Alphabet and state transitions does not have same len
            }

            let mut epsilon_transitions = None;
            let mut new_transitions = Vec::with_capacity(head.len());
            for (idx, transition) in transitions.iter().enumerate() {
                let mut tr_idx = Vec::with_capacity(transition.len());
                if Some(idx) == eps_idx {
                    for target in transition {
                        if let Some(idx) = state_name_map.get(target) {
                            tr_idx.push(*idx);
                        } else {
                            return Err(TransitionDoesNotExist(name, target)); // Target of transition does not exist
                        }
                    }
                    epsilon_transitions = Some(tr_idx);
                } else {
                    for target in transition {
                        if let Some(idx) = state_name_map.get(target) {
                            tr_idx.push(*idx);
                        } else {
                            return Err(TransitionDoesNotExist(name, target)); // Target of transition does not exist
                        }
                    }
                    new_transitions.push(tr_idx);
                }
            }

            if initial {
                if initial_state.is_none() {
                    initial_state = Some(idx);
                } else {
                    return Err(MultipleInitialStates);
                }
            }

            new_states.push(NfaState {
                name: Rc::from(name),
                initial,
                accepting,
                epsilon_transitions: epsilon_transitions.unwrap_or_default(),
                transitions: new_transitions,
            });
        }

        if let Some(initial_state) = initial_state {
            let dfa = Nfa {
                alphabet: head
                    .into_iter()
                    .filter_map(|s| match s {
                        NfaAlphabetEntry::Eps => None,
                        NfaAlphabetEntry::Element(s) => Some(Rc::from(s)),
                    })
                    .collect::<Rc<[_]>>(),
                states: new_states,
                initial_state,
            };
            Ok(dfa)
        } else {
            Err(MissingInitialState)
        }
    }
}