amethyst/
turing.rs

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

amethyst/
turing.rs
