berust/
interpreter.rs

1use crate::playfield::*;
2use rand::distributions;
3use std::io;
4use std::io::prelude::*;
5
6/// The current mode of the program
7///
8/// A program is either executing normally, parsing a string or has terminated.
9#[derive(Clone, Copy, Debug, PartialEq)]
10pub enum Mode {
11    Execute,
12    Parse,
13    Terminate,
14}
15
16/// The stack of an execution.
17pub type Stack = Vec<i64>;
18
19/// A provider of input and output operations.
20pub struct InputOutput<R, W> {
21    reader: R,
22    writer: W,
23}
24
25impl<R, W> InputOutput<R, W>
26where
27    R: BufRead,
28    W: Write,
29{
30    /// Create a new input and output provider based on the given reader and writer.
31    pub fn new(reader: R, writer: W) -> Self {
32        Self { reader, writer }
33    }
34
35    /// Return the input provider.
36    pub fn reader(&self) -> &R {
37        &self.reader
38    }
39
40    /// Return the output provider.
41    pub fn writer(&self) -> &W {
42        &self.writer
43    }
44
45    fn write_int(&mut self, val: i64) {
46        write!(self.writer, "{} ", val).unwrap()
47    }
48
49    fn write_ascii(&mut self, val: i64) {
50        write!(self.writer, "{}", val as u8 as char).unwrap()
51    }
52
53    fn read_int(&mut self) -> i64 {
54        let mut input = String::new();
55
56        if self.reader.read_line(&mut input).is_err() {
57            return 0;
58        }
59
60        input.trim().parse().unwrap_or(0)
61    }
62
63    fn read_ascii(&mut self) -> i64 {
64        let mut buf = [0; 1];
65
66        if self.reader.read_exact(&mut buf).is_err() {
67            return -1;
68        }
69
70        i64::from(buf[0])
71    }
72}
73
74/// An [`InputOutput`] implementation based on `stdin` and `stdout`.
75///
76/// [`IntputOutput`]: struct.InputOutput.html
77pub type StdInputOutput = InputOutput<io::BufReader<io::Stdin>, io::Stdout>;
78
79impl Default for StdInputOutput {
80    fn default() -> Self {
81        Self::new(io::BufReader::new(io::stdin()), io::stdout())
82    }
83}
84
85/// A Befunge interpreter
86pub struct Interpreter<R, W> {
87    field: Playfield,
88    io: InputOutput<R, W>,
89    nav: PlayfieldNavigator,
90    stack: Stack,
91    mode: Mode,
92}
93
94impl<R, W> Interpreter<R, W>
95where
96    R: BufRead,
97    W: Write,
98{
99    /// Create a new interpreter for the given playfield.
100    pub fn new(field: Playfield, io: InputOutput<R, W>) -> Self {
101        let dimensions = field.dimensions();
102
103        Self {
104            field,
105            io,
106            nav: PlayfieldNavigator::new(dimensions),
107            stack: Vec::new(),
108            mode: Mode::Execute,
109        }
110    }
111
112    /// Get a reference to the playfield.
113    pub fn field(&self) -> &Playfield {
114        &self.field
115    }
116
117    /// Get a reference to the input and output provider.
118    pub fn io(&self) -> &InputOutput<R, W> {
119        &self.io
120    }
121
122    /// Get a reference to the navigator.
123    pub fn nav(&self) -> &PlayfieldNavigator {
124        &self.nav
125    }
126
127    /// Get a reference to the stack.
128    pub fn stack(&self) -> &Stack {
129        &self.stack
130    }
131
132    /// Get the current mode.
133    pub fn mode(&self) -> Mode {
134        self.mode
135    }
136
137    fn execute_step(&mut self, c: u8) -> Mode {
138        match c {
139            // Push this number on the stack
140            b'0'...b'9' => self.stack.push(i64::from(c - 0x30)),
141
142            // Addition: Pop a and b, then push a+b
143            b'+' => {
144                let a = self.stack.pop().unwrap_or(0);
145                let b = self.stack.pop().unwrap_or(0);
146
147                self.stack.push(a + b);
148            }
149
150            // Subtraction: Pop a and b, then push b-a
151            b'-' => {
152                let a = self.stack.pop().unwrap_or(0);
153                let b = self.stack.pop().unwrap_or(0);
154
155                self.stack.push(b - a);
156            }
157
158            // Multiplication: Pop a and b, then push a*b
159            b'*' => {
160                let a = self.stack.pop().unwrap_or(0);
161                let b = self.stack.pop().unwrap_or(0);
162
163                self.stack.push(a * b);
164            }
165
166            // Integer division: Pop a and b, then push b/a, rounded towards 0
167            b'/' => {
168                let a = self.stack.pop().unwrap_or(0);
169                let b = self.stack.pop().unwrap_or(0);
170
171                self.stack.push(b / a);
172            }
173
174            // Modulo: Pop a and b, then push the remainder of the integer division of b/a
175            b'%' => {
176                let a = self.stack.pop().unwrap_or(0);
177                let b = self.stack.pop().unwrap_or(0);
178
179                self.stack.push(b % a);
180            }
181
182            // Logical NOT: Pop a value. If the value is zero, push 1; otherwise, push zero.
183            b'!' => {
184                if self.stack.pop().unwrap_or(0) == 0 {
185                    self.stack.push(1)
186                } else {
187                    self.stack.push(0)
188                }
189            }
190
191            // Greater than: Pop a and b, then push 1 if b>a, otherwise zero.
192            b'`' => {
193                let a = self.stack.pop().unwrap_or(0);
194                let b = self.stack.pop().unwrap_or(0);
195
196                if b > a {
197                    self.stack.push(1)
198                } else {
199                    self.stack.push(0)
200                }
201            }
202
203            // Start moving right
204            b'>' => self.nav.turn(Direction::Right),
205
206            // Start moving left
207            b'<' => self.nav.turn(Direction::Left),
208
209            // Start moving up
210            b'^' => self.nav.turn(Direction::Up),
211
212            // Start moving down
213            b'v' => self.nav.turn(Direction::Down),
214
215            // Start moving in a random cardinal direction
216            b'?' => self.nav.turn(rand::random()),
217
218            // Pop a value; move right if value=0, left otherwise
219            b'_' => {
220                if self.stack.pop().unwrap_or(0) == 0 {
221                    self.nav.turn(Direction::Right)
222                } else {
223                    self.nav.turn(Direction::Left)
224                }
225            }
226
227            // Pop a value; move down if value=0, up otherwise
228            b'|' => {
229                if self.stack.pop().unwrap_or(0) == 0 {
230                    self.nav.turn(Direction::Down)
231                } else {
232                    self.nav.turn(Direction::Up)
233                }
234            }
235
236            // Start string mode: push each character's ASCII value all the way up to the next "
237            b'"' => return Mode::Parse,
238
239            // Duplicate value on top of the stack
240            b':' => {
241                let v = self.stack.pop().unwrap_or(0);
242
243                self.stack.push(v);
244                self.stack.push(v);
245            }
246
247            // Swap two values on top of the stack
248            b'\\' => {
249                let a = self.stack.pop().unwrap_or(0);
250                let b = self.stack.pop().unwrap_or(0);
251
252                self.stack.push(a);
253                self.stack.push(b);
254            }
255
256            // Pop value from the stack and discard it
257            b'$' => {
258                self.stack.pop();
259            }
260
261            // Pop value and output as an integer followed by a space
262            b'.' => self.io.write_int(self.stack.pop().unwrap_or(0)),
263
264            // Pop value and output as ASCII character
265            b',' => self.io.write_ascii(self.stack.pop().unwrap_or(0)),
266
267            // Bridge: Skip next cell
268            b'#' => self.nav.step(),
269
270            // A "put" call (a way to store a value for later use).
271            //
272            // Pop y, x, and v, then change the character at (x,y) in the program to the character
273            // with ASCII value v
274            b'p' => {
275                let y = self.stack.pop().unwrap_or(0);
276                let x = self.stack.pop().unwrap_or(0);
277                let v = self.stack.pop().unwrap_or(0);
278
279                self.field[(x as usize, y as usize)] = v as u8
280            }
281
282            // A "get" call (a way to retrieve data in storage).
283            //
284            // Pop y and x, then push ASCII value of the character at that position in the program
285            b'g' => {
286                let y = self.stack.pop().unwrap_or(0);
287                let x = self.stack.pop().unwrap_or(0);
288                let v = self.field[(x as usize, y as usize)];
289
290                self.stack.push(i64::from(v))
291            }
292
293            // Ask user for a number and push it
294            b'&' => self.stack.push(self.io.read_int()),
295
296            // Ask user for a character and push its ASCII value
297            b'~' => self.stack.push(self.io.read_ascii()),
298
299            // End program
300            b'@' => return Mode::Terminate,
301
302            // No-op. Does nothing
303            b' ' => (),
304
305            // Illegal characters
306            _ => panic!("Illegal character: {}", c as char),
307        }
308
309        Mode::Execute
310    }
311
312    fn parse_step(&mut self, c: u8) -> Mode {
313        if let b'"' = c {
314            return Mode::Execute;
315        }
316
317        self.stack.push(i64::from(c));
318
319        Mode::Parse
320    }
321}
322
323impl<R, W> Iterator for Interpreter<R, W>
324where
325    R: BufRead,
326    W: Write,
327{
328    type Item = ();
329
330    fn next(&mut self) -> Option<Self::Item> {
331        let val = self.field[self.nav.pos()];
332
333        self.mode = match self.mode {
334            Mode::Execute => self.execute_step(val),
335            Mode::Parse => self.parse_step(val),
336            Mode::Terminate => Mode::Terminate,
337        };
338
339        if let Mode::Terminate = self.mode {
340            return None;
341        }
342
343        self.nav.step();
344
345        Some(())
346    }
347}
348
349impl distributions::Distribution<Direction> for distributions::Standard {
350    fn sample<R: rand::Rng + ?Sized>(&self, rng: &mut R) -> Direction {
351        match rng.gen_range(0, 4) {
352            0 => Direction::Up,
353            1 => Direction::Down,
354            2 => Direction::Left,
355            _ => Direction::Right,
356        }
357    }
358}
359
360#[cfg(test)]
361mod tests {
362    use super::*;
363    use crate::playfield::Playfield;
364
365    fn test_program(field: &str, input: &str, output: &str, execution: Vec<(Mode, Stack)>) {
366        let reader = input.bytes().collect::<Vec<_>>();
367        let writer = Vec::new();
368
369        let playfield = Playfield::new(field);
370        let io = InputOutput::new(&reader[..], writer);
371        let mut interpreter = Interpreter::new(playfield, io);
372
373        for (mode, stack) in execution {
374            assert_eq!(mode, interpreter.mode);
375            assert_eq!(stack, interpreter.stack);
376
377            interpreter.next();
378        }
379
380        assert_eq!(output.bytes().collect::<Vec<_>>(), interpreter.io.writer);
381    }
382
383    #[test]
384    fn interpret_digits() {
385        test_program(
386            "0123456789",
387            "",
388            "",
389            vec![
390                (Mode::Execute, vec![]),
391                (Mode::Execute, vec![0]),
392                (Mode::Execute, vec![0, 1]),
393                (Mode::Execute, vec![0, 1, 2]),
394                (Mode::Execute, vec![0, 1, 2, 3]),
395                (Mode::Execute, vec![0, 1, 2, 3, 4]),
396                (Mode::Execute, vec![0, 1, 2, 3, 4, 5]),
397                (Mode::Execute, vec![0, 1, 2, 3, 4, 5, 6]),
398                (Mode::Execute, vec![0, 1, 2, 3, 4, 5, 6, 7]),
399                (Mode::Execute, vec![0, 1, 2, 3, 4, 5, 6, 7, 8]),
400                (Mode::Execute, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]),
401            ],
402        );
403    }
404
405    #[test]
406    fn interpret_arithmetic() {
407        test_program(
408            "73+",
409            "",
410            "",
411            vec![
412                (Mode::Execute, vec![]),
413                (Mode::Execute, vec![7]),
414                (Mode::Execute, vec![7, 3]),
415                (Mode::Execute, vec![10]),
416            ],
417        );
418
419        test_program(
420            "73-",
421            "",
422            "",
423            vec![
424                (Mode::Execute, vec![]),
425                (Mode::Execute, vec![7]),
426                (Mode::Execute, vec![7, 3]),
427                (Mode::Execute, vec![4]),
428            ],
429        );
430
431        test_program(
432            "73*",
433            "",
434            "",
435            vec![
436                (Mode::Execute, vec![]),
437                (Mode::Execute, vec![7]),
438                (Mode::Execute, vec![7, 3]),
439                (Mode::Execute, vec![21]),
440            ],
441        );
442
443        test_program(
444            "73/",
445            "",
446            "",
447            vec![
448                (Mode::Execute, vec![]),
449                (Mode::Execute, vec![7]),
450                (Mode::Execute, vec![7, 3]),
451                (Mode::Execute, vec![2]),
452            ],
453        );
454
455        test_program(
456            "73%",
457            "",
458            "",
459            vec![
460                (Mode::Execute, vec![]),
461                (Mode::Execute, vec![7]),
462                (Mode::Execute, vec![7, 3]),
463                (Mode::Execute, vec![1]),
464            ],
465        );
466    }
467
468    #[test]
469    fn interpret_logic() {
470        test_program(
471            "0!",
472            "",
473            "",
474            vec![
475                (Mode::Execute, vec![]),
476                (Mode::Execute, vec![0]),
477                (Mode::Execute, vec![1]),
478            ],
479        );
480
481        test_program(
482            "5!",
483            "",
484            "",
485            vec![
486                (Mode::Execute, vec![]),
487                (Mode::Execute, vec![5]),
488                (Mode::Execute, vec![0]),
489            ],
490        );
491
492        test_program(
493            "73`",
494            "",
495            "",
496            vec![
497                (Mode::Execute, vec![]),
498                (Mode::Execute, vec![7]),
499                (Mode::Execute, vec![7, 3]),
500                (Mode::Execute, vec![1]),
501            ],
502        );
503
504        test_program(
505            "45`",
506            "",
507            "",
508            vec![
509                (Mode::Execute, vec![]),
510                (Mode::Execute, vec![4]),
511                (Mode::Execute, vec![4, 5]),
512                (Mode::Execute, vec![0]),
513            ],
514        );
515    }
516
517    #[test]
518    fn interpret_direction() {
519        test_program(
520            "v\n3\n>4",
521            "",
522            "",
523            vec![
524                (Mode::Execute, vec![]),
525                (Mode::Execute, vec![]),
526                (Mode::Execute, vec![3]),
527                (Mode::Execute, vec![3]),
528                (Mode::Execute, vec![3, 4]),
529            ],
530        );
531
532        test_program(
533            "<@^\n  @\n  5",
534            "",
535            "",
536            vec![
537                (Mode::Execute, vec![]),
538                (Mode::Execute, vec![]),
539                (Mode::Execute, vec![]),
540                (Mode::Execute, vec![5]),
541            ],
542        );
543
544        test_program(
545            "?5@5\n5\n@\n5",
546            "",
547            "",
548            vec![
549                (Mode::Execute, vec![]),
550                (Mode::Execute, vec![]),
551                (Mode::Execute, vec![5]),
552            ],
553        );
554    }
555
556    #[test]
557    fn interpret_controlflow() {
558        test_program(
559            "0_5",
560            "",
561            "",
562            vec![
563                (Mode::Execute, vec![]),
564                (Mode::Execute, vec![0]),
565                (Mode::Execute, vec![]),
566                (Mode::Execute, vec![5]),
567            ],
568        );
569
570        test_program(
571            "3_5",
572            "",
573            "",
574            vec![
575                (Mode::Execute, vec![]),
576                (Mode::Execute, vec![3]),
577                (Mode::Execute, vec![]),
578                (Mode::Execute, vec![3]),
579            ],
580        );
581
582        test_program(
583            "0|\n 5",
584            "",
585            "",
586            vec![
587                (Mode::Execute, vec![]),
588                (Mode::Execute, vec![0]),
589                (Mode::Execute, vec![]),
590                (Mode::Execute, vec![5]),
591            ],
592        );
593
594        test_program(
595            "3|\n 5\n 4",
596            "",
597            "",
598            vec![
599                (Mode::Execute, vec![]),
600                (Mode::Execute, vec![3]),
601                (Mode::Execute, vec![]),
602                (Mode::Execute, vec![4]),
603            ],
604        );
605    }
606
607    #[test]
608    fn interpret_string() {
609        test_program(
610            "\"abc\"",
611            "",
612            "",
613            vec![
614                (Mode::Execute, vec![]),
615                (Mode::Parse, vec![]),
616                (Mode::Parse, vec![0x61]),
617                (Mode::Parse, vec![0x61, 0x62]),
618                (Mode::Parse, vec![0x61, 0x62, 0x63]),
619                (Mode::Execute, vec![0x61, 0x62, 0x63]),
620            ],
621        );
622
623        test_program(
624            "1\"23",
625            "",
626            "",
627            vec![
628                (Mode::Execute, vec![]),
629                (Mode::Execute, vec![1]),
630                (Mode::Parse, vec![1]),
631                (Mode::Parse, vec![1, 0x32]),
632                (Mode::Parse, vec![1, 0x32, 0x33]),
633                (Mode::Parse, vec![1, 0x32, 0x33, 0x31]),
634                (Mode::Execute, vec![1, 0x32, 0x33, 0x31]),
635            ],
636        );
637
638        test_program(
639            "v\n\"\na\nb\n\"",
640            "",
641            "",
642            vec![
643                (Mode::Execute, vec![]),
644                (Mode::Execute, vec![]),
645                (Mode::Parse, vec![]),
646                (Mode::Parse, vec![0x61]),
647                (Mode::Parse, vec![0x61, 0x62]),
648                (Mode::Execute, vec![0x61, 0x62]),
649            ],
650        );
651    }
652
653    #[test]
654    fn interpret_stack_manipulation() {
655        test_program(
656            "1:",
657            "",
658            "",
659            vec![
660                (Mode::Execute, vec![]),
661                (Mode::Execute, vec![1]),
662                (Mode::Execute, vec![1, 1]),
663            ],
664        );
665
666        test_program(
667            "12\\",
668            "",
669            "",
670            vec![
671                (Mode::Execute, vec![]),
672                (Mode::Execute, vec![1]),
673                (Mode::Execute, vec![1, 2]),
674                (Mode::Execute, vec![2, 1]),
675            ],
676        );
677
678        test_program(
679            "1$",
680            "",
681            "",
682            vec![
683                (Mode::Execute, vec![]),
684                (Mode::Execute, vec![1]),
685                (Mode::Execute, vec![]),
686            ],
687        );
688    }
689
690    #[test]
691    fn interpret_output() {
692        test_program(
693            "1.",
694            "",
695            "1 ",
696            vec![
697                (Mode::Execute, vec![]),
698                (Mode::Execute, vec![1]),
699                (Mode::Execute, vec![]),
700            ],
701        );
702
703        test_program(
704            "\"a\",25*,",
705            "",
706            "a\n",
707            vec![
708                (Mode::Execute, vec![]),
709                (Mode::Parse, vec![]),
710                (Mode::Parse, vec![0x61]),
711                (Mode::Execute, vec![0x61]),
712                (Mode::Execute, vec![]),
713                (Mode::Execute, vec![2]),
714                (Mode::Execute, vec![2, 5]),
715                (Mode::Execute, vec![10]),
716                (Mode::Execute, vec![]),
717            ],
718        );
719    }
720
721    #[test]
722    fn interpret_bridge() {
723        test_program(
724            "#01",
725            "",
726            "",
727            vec![
728                (Mode::Execute, vec![]),
729                (Mode::Execute, vec![]),
730                (Mode::Execute, vec![1]),
731            ],
732        );
733    }
734
735    #[test]
736    fn interpret_field_manipulation() {
737        test_program(
738            "30g5",
739            "",
740            "",
741            vec![
742                (Mode::Execute, vec![]),
743                (Mode::Execute, vec![3]),
744                (Mode::Execute, vec![3, 0]),
745                (Mode::Execute, vec![0x35]),
746                (Mode::Execute, vec![0x35, 5]),
747            ],
748        );
749
750        test_program(
751            "77*40p1",
752            "",
753            "",
754            vec![
755                (Mode::Execute, vec![]),
756                (Mode::Execute, vec![7]),
757                (Mode::Execute, vec![7, 7]),
758                (Mode::Execute, vec![49]),
759                (Mode::Execute, vec![49, 4]),
760                (Mode::Execute, vec![49, 4, 0]),
761                (Mode::Execute, vec![]),
762                (Mode::Execute, vec![1]),
763            ],
764        );
765    }
766
767    #[test]
768    fn interpret_user_input() {
769        test_program(
770            "&",
771            "4\n",
772            "",
773            vec![(Mode::Execute, vec![]), (Mode::Execute, vec![4])],
774        );
775
776        test_program(
777            "&",
778            "abc\n",
779            "",
780            vec![(Mode::Execute, vec![]), (Mode::Execute, vec![0])],
781        );
782
783        test_program(
784            "&",
785            "",
786            "",
787            vec![(Mode::Execute, vec![]), (Mode::Execute, vec![0])],
788        );
789
790        test_program(
791            "~~~",
792            "ab",
793            "",
794            vec![
795                (Mode::Execute, vec![]),
796                (Mode::Execute, vec![0x61]),
797                (Mode::Execute, vec![0x61, 0x62]),
798                (Mode::Execute, vec![0x61, 0x62, -1]),
799            ],
800        );
801    }
802
803    #[test]
804    fn interpret_termination() {
805        test_program(
806            "@",
807            "",
808            "",
809            vec![
810                (Mode::Execute, vec![]),
811                (Mode::Terminate, vec![]),
812                (Mode::Terminate, vec![]),
813            ],
814        );
815
816        test_program(
817            "5@",
818            "",
819            "",
820            vec![
821                (Mode::Execute, vec![]),
822                (Mode::Execute, vec![5]),
823                (Mode::Terminate, vec![5]),
824                (Mode::Terminate, vec![5]),
825            ],
826        );
827    }
828
829    #[test]
830    #[should_panic(expected = "Illegal character: x")]
831    fn interpret_illegal() {
832        test_program("x", "", "", vec![(Mode::Execute, vec![])]);
833    }
834}
berust/interpreter.rs

berust/
interpreter.rs
