amethyst/
turing.rs

1use crate::{
2    config::Config,
3    result::RunResult,
4    syntax::{AutomatonType, MacroType, Move, Program, StateType},
5    tape::Tape,
6};
7use std::collections::{HashMap, HashSet};
8
9#[derive(Debug)]
10pub enum Macro {
11    Move(String, Move, u32),
12    Override(String, Move, u32, char),
13    Place(String, String),
14    Shift(String, Move, u32),
15    Complement(String, TuringMachine),
16    Reunion(String, Vec<TuringMachine>),
17    Intersect(String, Vec<TuringMachine>),
18    Chain(String, Vec<TuringMachine>),
19    Repeat(String, u32, TuringMachine),
20}
21
22fn into_macro(
23    _type_name: String,
24    name: String,
25    macro_type: MacroType,
26    automata: &HashMap<String, AutomatonType>,
27    visited: &mut HashSet<String>,
28) -> Result<Macro, String> {
29    Ok(match macro_type {
30        MacroType::Move(move_symbol, number) => Macro::Move(name, move_symbol, number),
31        MacroType::Override(move_symbol, number, tape_symbol) => {
32            Macro::Override(name, move_symbol, number, tape_symbol)
33        }
34        MacroType::Place(str) => Macro::Place(name, str),
35        MacroType::Shift(move_symbol, number) => Macro::Shift(name, move_symbol, number),
36        MacroType::Complement(component) => {
37            let mut tm = TuringMachine::default();
38            tm.add_component(
39                name.to_string() + &component + ".",
40                &component,
41                automata,
42                visited,
43            )?;
44            tm.validate()?;
45            Macro::Complement(name, tm)
46        }
47        MacroType::Reunion(components) => Macro::Reunion(
48            name.to_owned(),
49            (*components)
50                .iter()
51                .map(|component| {
52                    let mut tm = TuringMachine::default();
53                    tm.add_component(
54                        name.to_string() + component + ".",
55                        &component,
56                        automata,
57                        visited,
58                    )?;
59                    tm.validate()?;
60                    Ok(tm)
61                })
62                .collect::<Result<Vec<TuringMachine>, String>>()?,
63        ),
64        MacroType::Intersect(components) => Macro::Intersect(
65            name.to_owned(),
66            (*components)
67                .iter()
68                .map(|component| {
69                    let mut tm = TuringMachine::default();
70                    tm.add_component(
71                        name.to_string() + component + ".",
72                        &component,
73                        automata,
74                        visited,
75                    )?;
76                    tm.validate()?;
77                    Ok(tm)
78                })
79                .collect::<Result<Vec<TuringMachine>, String>>()?,
80        ),
81        MacroType::Chain(components) => Macro::Chain(
82            name.to_owned(),
83            (*components)
84                .iter()
85                .map(|component| {
86                    let mut tm = TuringMachine::default();
87                    tm.add_component(
88                        name.to_string() + component + ".",
89                        &component,
90                        automata,
91                        visited,
92                    )?;
93                    tm.validate()?;
94                    Ok(tm)
95                })
96                .collect::<Result<Vec<TuringMachine>, String>>()?,
97        ),
98        MacroType::Repeat(num, component) => {
99            let mut tm = TuringMachine::default();
100            tm.add_component(
101                name.to_string() + &component + ".",
102                &component,
103                automata,
104                visited,
105            )?;
106            tm.validate()?;
107            Macro::Repeat(name, num, tm)
108        }
109    })
110}
111
112#[derive(Debug)]
113pub struct TuringMachine {
114    pub initial_state: String,
115    states: HashSet<String>,
116    accept_states: HashSet<String>,
117    reject_states: HashSet<String>,
118    transitions: HashMap<String, HashMap<char, (String, char, Move)>>, // (state, read_symbol) -> (new_state, write_symbol, move)
119    macros: HashMap<String, Box<Macro>>, // optimized macros: input state -> tape modifications -> output state
120}
121
122#[derive(Debug, Clone)]
123pub struct TuringState {
124    current_state: String,
125    tape: Tape,
126    iteration: u32,
127}
128
129impl Default for TuringMachine {
130    fn default() -> Self {
131        Self {
132            initial_state: "".to_owned(),
133            states: HashSet::new(),
134            accept_states: HashSet::new(),
135            reject_states: HashSet::new(),
136            transitions: HashMap::new(),
137            macros: HashMap::new(),
138        }
139    }
140}
141
142impl TuringState {
143    pub fn new(initial_state: String, tape_symbols: String) -> Self {
144        let mut tape = Tape::default();
145        tape.initialize(tape_symbols);
146        Self {
147            current_state: initial_state,
148            tape,
149            iteration: 0,
150        }
151    }
152}
153
154fn get_state_name(s: &StateType) -> &str {
155    match s {
156        StateType::Accept(name) => name,
157        StateType::Reject(name) => name,
158        StateType::State(name, _) => name,
159    }
160}
161
162fn get_automaton_name(a: &AutomatonType) -> &str {
163    match a {
164        AutomatonType::Machine(name, _) => name,
165        AutomatonType::Macro(name, _) => name,
166    }
167}
168//
169impl TuringMachine {
170    pub fn make(
171        &mut self,
172        syntax: &Program,
173        start: &String,
174        visited: &mut HashSet<String>,
175    ) -> Result<(), String> {
176        let automata: HashMap<String, AutomatonType> = (*syntax.automata)
177            .iter()
178            .map(|automaton| (get_automaton_name(automaton).to_string(), automaton.clone()))
179            .collect();
180        if !automata.contains_key(start) {
181            return Err(format!(
182                "Could not find start machine {}!",
183                start.to_string()
184            ));
185        }
186        self.add_component("".to_string(), start, &automata, visited)?;
187        self.validate()
188    }
189
190    pub fn add_component(
191        &mut self,
192        prefix: String,
193        component: &String,
194        automata: &HashMap<String, AutomatonType>,
195        visited: &mut HashSet<String>,
196    ) -> Result<(), String> {
197        if visited.contains(component) {
198            return Err(format!(
199                "Cycles are not allowed in components. Error for component {}!",
200                prefix
201                    .chars()
202                    .take(prefix.chars().count() - 1)
203                    .collect::<String>()
204            ));
205        }
206        visited.insert(component.to_string());
207        match automata.get(component) {
208            None => Err(format!(
209                "Could not find component {} of type {}!",
210                prefix
211                    .chars()
212                    .take(prefix.chars().count() - 1)
213                    .collect::<String>(),
214                component
215            )),
216            Some(automaton) => {
217                match automaton {
218                    AutomatonType::Machine(_, machine) => {
219                        (*machine.components)
220                            .iter()
221                            .try_for_each(|(automaton, c_name)| {
222                                self.add_component(
223                                    prefix.to_owned() + c_name + ".",
224                                    automaton,
225                                    &automata,
226                                    visited,
227                                )
228                            })?;
229                        (*machine.states).iter().for_each(|state| {
230                            self.add_state(state, prefix.to_owned());
231                        });
232                    }
233                    AutomatonType::Macro(type_name, macro_type) => {
234                        // Input state of the macro
235                        self.states.insert(prefix.to_string() + "input");
236                        self.initial_state = prefix.to_string() + "input";
237                        // Accept state of the macro
238                        self.states.insert(prefix.to_string() + "accept");
239                        self.accept_states.insert(prefix.to_string() + "accept");
240                        // Reject state of the macro
241                        self.states.insert(prefix.to_string() + "reject");
242                        self.reject_states.insert(prefix.to_string() + "reject");
243                        // Macro indexed by input_state
244                        self.macros.insert(
245                            prefix.to_string() + "input",
246                            Box::new(into_macro(
247                                type_name.to_owned(),
248                                prefix.to_owned(),
249                                macro_type.clone(),
250                                automata,
251                                visited,
252                            )?),
253                        );
254                    }
255                }
256                visited.remove(component);
257                Ok(())
258            }
259        }
260    }
261
262    pub fn add_state(&mut self, state_type: &StateType, prefix: String) {
263        let name = get_state_name(state_type);
264        let state_name = prefix.to_owned() + name;
265
266        match state_type {
267            StateType::Accept(_) => {
268                self.states.insert(state_name.to_owned());
269                self.accept_states.insert(state_name);
270            }
271            StateType::Reject(_) => {
272                self.states.insert(state_name.to_owned());
273                self.reject_states.insert(state_name);
274            }
275            StateType::State(_, state) => {
276                self.states.insert(state_name.to_owned());
277                self.accept_states.remove(&state_name);
278                self.reject_states.remove(&state_name);
279
280                if state.initial {
281                    self.initial_state = state_name.to_owned();
282                }
283                (*state.transitions).iter().for_each(|transition| {
284                    self.add_transition(
285                        state_name.to_owned(),
286                        transition.read_symbol,
287                        &transition.new_state,
288                        transition.write_symbol,
289                        transition.move_symbol,
290                        prefix.to_owned(),
291                    )
292                });
293            }
294        }
295    }
296
297    pub fn add_transition(
298        &mut self,
299        from: String,
300        read_symbol: char,
301        new_state: &String,
302        write_symbol: char,
303        move_symbol: Move,
304        prefix: String,
305    ) {
306        let new_state_name = prefix + new_state;
307        match self.transitions.get_mut(&from) {
308            None => {
309                let mut inner_map = HashMap::new();
310                inner_map.insert(read_symbol, (new_state_name, write_symbol, move_symbol));
311                self.transitions.insert(from, inner_map);
312            }
313            Some(inner_map) => {
314                inner_map.insert(read_symbol, (new_state_name, write_symbol, move_symbol));
315            }
316        }
317    }
318
319    pub fn validate(&mut self) -> Result<(), String> {
320        self.transitions.values().try_for_each(|inner| {
321            inner.values().try_for_each(|(state, _, _)| {
322                if !self.states.contains(state) {
323                    Err("Undefined state ".to_owned() + state)
324                } else {
325                    Ok(())
326                }
327            })
328        })
329    }
330
331    pub fn get_transition(&self, state: &String, read_symbol: char) -> (String, char, Move) {
332        match self.transitions.get(state).unwrap().get(&read_symbol) {
333            Some(tuple) => (*tuple).clone(),
334            None => match self.transitions.get(state).unwrap().get(&'_') {
335                None => ("reject".to_owned(), '@', Move::Neutral),
336                Some(&(ref new_state, write_symbol, move_symbol)) => {
337                    if write_symbol != '_' {
338                        (new_state.to_owned(), write_symbol, move_symbol)
339                    } else {
340                        (new_state.to_owned(), read_symbol, move_symbol)
341                    }
342                }
343            },
344        }
345    }
346
347    pub fn check_final(&self, tstate: &TuringState) -> Option<RunResult> {
348        if self.accept_states.contains(&tstate.current_state) {
349            return Some(RunResult::Accept);
350        }
351        if self.reject_states.contains(&tstate.current_state) {
352            return Some(RunResult::Reject);
353        }
354        None
355    }
356
357    pub fn start(&self, config: &Config) -> RunResult {
358        let mut turing_state =
359            TuringState::new(self.initial_state.to_owned(), config.input.to_owned());
360        if config.debug {
361            print!("State: {}", turing_state.current_state);
362        }
363        let result = self.run(&mut turing_state, config);
364        if config.debug {
365            println!("");
366        }
367        if config.show_tape {
368            println!("{}", turing_state.tape);
369        }
370        if config.show_output {
371            turing_state.tape.output();
372        }
373        result
374    }
375
376    pub fn run(&self, tstate: &mut TuringState, config: &Config) -> RunResult {
377        while tstate.iteration < config.iterations {
378            if let Some(result) = self.check_final(tstate) {
379                return result;
380            }
381
382            if let Some(macro_component) = self.macros.get(&tstate.current_state) {
383                let applied = self.apply_macro(tstate, &macro_component, &config);
384                match applied {
385                    Err(result) => return result,
386                    Ok(()) => {
387                        if config.debug {
388                            print!(" -> {}", &tstate.current_state)
389                        }
390                    }
391                }
392            }
393            if let Some(result) = self.check_final(tstate) {
394                return result;
395            }
396
397            let read_symbol = tstate.tape.read();
398            let (new_state, write_symbol, move_symbol) =
399                self.get_transition(&tstate.current_state, read_symbol);
400            if !self.states.contains(&new_state) {
401                panic!("Could not find state {}!", new_state);
402            }
403
404            tstate.current_state = new_state;
405            tstate.tape.write(write_symbol);
406            match move_symbol {
407                Move::Left => tstate.tape.move_left(),
408                Move::Right => tstate.tape.move_right(),
409                Move::Neutral => {}
410            }
411            if config.debug {
412                print!(" -> {}", tstate.current_state);
413            }
414            match config.bound {
415                Some(max_memory) => {
416                    if tstate.tape.memory() > max_memory {
417                        return RunResult::ExceededMemory;
418                    }
419                }
420                None => {}
421            }
422            tstate.iteration += 1;
423        }
424
425        return RunResult::ExceededTime;
426    }
427
428    fn apply_macro(
429        &self,
430        tstate: &mut TuringState,
431        macro_component: &Box<Macro>,
432        config: &Config,
433    ) -> Result<(), RunResult> {
434        match macro_component.as_ref() {
435            Macro::Move(name, move_symbol, num) => {
436                tstate.iteration += num;
437                if tstate.iteration > config.iterations {
438                    return Err(RunResult::ExceededTime);
439                }
440                match move_symbol {
441                    Move::Left => (0..*num).for_each(|_| tstate.tape.move_left()),
442                    Move::Right => (0..*num).for_each(|_| tstate.tape.move_right()),
443                    Move::Neutral => {}
444                }
445                tstate.current_state = name.to_string() + "accept";
446                Ok(())
447            }
448            Macro::Override(name, move_symbol, num, symbol) => {
449                tstate.iteration += num;
450                if tstate.iteration > config.iterations {
451                    return Err(RunResult::ExceededTime);
452                }
453                match move_symbol {
454                    Move::Left => (0..*num).for_each(|_| {
455                        tstate.tape.write(*symbol);
456                        tstate.tape.move_left();
457                    }),
458                    Move::Right => (0..*num).for_each(|_| {
459                        tstate.tape.write(*symbol);
460                        tstate.tape.move_right();
461                    }),
462                    Move::Neutral => tstate.tape.write(*symbol),
463                }
464                tstate.current_state = name.to_string() + "accept";
465                Ok(())
466            }
467            Macro::Place(name, tape_symbols) => {
468                tstate.iteration += tape_symbols.len() as u32;
469                if tstate.iteration > config.iterations {
470                    return Err(RunResult::ExceededTime);
471                }
472                tape_symbols.chars().for_each(|symbol| {
473                    tstate.tape.write(symbol);
474                    tstate.tape.move_right();
475                });
476                tstate.current_state = name.to_string() + "accept";
477                Ok(())
478            }
479            Macro::Shift(name, move_symbol, num) => {
480                tstate.iteration += num;
481                if tstate.iteration > config.iterations {
482                    return Err(RunResult::ExceededTime);
483                }
484                match move_symbol {
485                    Move::Left => (0..*num).for_each(|_| tstate.tape.shift_left()),
486                    Move::Right => (0..*num).for_each(|_| tstate.tape.shift_right()),
487                    Move::Neutral => {}
488                }
489                tstate.current_state = name.to_string() + "accept";
490                Ok(())
491            }
492            Macro::Complement(name, tm) => {
493                tstate.current_state = tm.initial_state.to_owned();
494                if config.debug {
495                    print!(" -> {}", &tstate.current_state)
496                }
497                match tm.run(tstate, config) {
498                    RunResult::Accept => tstate.current_state = name.to_string() + "reject",
499                    RunResult::Reject => tstate.current_state = name.to_string() + "accept",
500                    r => return Err(r),
501                }
502                Ok(())
503            }
504            Macro::Reunion(name, tms) => {
505                let old_tstate = tstate.clone();
506                for tm in tms {
507                    *tstate = old_tstate.clone();
508                    tstate.current_state = tm.initial_state.to_owned();
509                    if config.debug {
510                        print!(" -> {}", &tstate.current_state)
511                    }
512                    match tm.run(tstate, config) {
513                        RunResult::Accept => {
514                            tstate.current_state = name.to_string() + "accept";
515                            return Ok(());
516                        }
517                        RunResult::Reject => {}
518                        r => return Err(r),
519                    }
520                }
521                tstate.current_state = name.to_string() + "reject";
522                Ok(())
523            }
524            Macro::Intersect(name, tms) => {
525                let old_tstate = tstate.clone();
526                for tm in tms {
527                    *tstate = old_tstate.clone();
528                    tstate.current_state = tm.initial_state.to_owned();
529                    if config.debug {
530                        print!(" -> {}", &tstate.current_state)
531                    }
532                    match tm.run(tstate, config) {
533                        RunResult::Accept => {}
534                        RunResult::Reject => {
535                            tstate.current_state = name.to_string() + "reject";
536                            return Ok(());
537                        }
538                        r => return Err(r),
539                    }
540                }
541                tstate.current_state = name.to_string() + "accept";
542                Ok(())
543            }
544            Macro::Chain(name, tms) => {
545                for tm in tms {
546                    tstate.current_state = tm.initial_state.to_owned();
547                    if config.debug {
548                        print!(" -> {}", &tstate.current_state)
549                    }
550                    match tm.run(tstate, config) {
551                        RunResult::Accept => {}
552                        RunResult::Reject => {
553                            tstate.current_state = name.to_string() + "reject";
554                            return Ok(());
555                        }
556                        r => return Err(r),
557                    }
558                }
559                tstate.current_state = name.to_string() + "accept";
560                Ok(())
561            }
562            Macro::Repeat(name, num, tm) => {
563                for _ in 0..*num {
564                    tstate.current_state = tm.initial_state.to_owned();
565                    if config.debug {
566                        print!(" -> {}", &tstate.current_state)
567                    }
568                    match tm.run(tstate, config) {
569                        RunResult::Accept => {}
570                        RunResult::Reject => {
571                            tstate.current_state = name.to_string() + "reject";
572                            return Ok(());
573                        }
574                        r => return Err(r),
575                    }
576                }
577                tstate.current_state = name.to_string() + "accept";
578                Ok(())
579            }
580        }
581    }
582}
amethyst/turing.rs

amethyst/
turing.rs
