115 line brainfuck interpreter written in C++

Question

This is a simple brainfuck interpreter I've written in C++. It takes a path to a brainfuck source file as a command line argument. The program uses a tape size of 30000 and cell size of one byte. Decrementing a cell's value under 0 will wrap it to 255 and vice versa.

I would really appreciate any kind of feedback, especially on how the existing code could be improved.

I'm using Apple Clang/LLVM and I've been compiling with the command:

clang++ -pedantic -O3 -std=c++17 brainfuck.cpp -o brainfuck

brainfuck.cpp:

#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>


/* Read the source file into a char vector, and return the vector. */
std::vector<char> read_source(std::string&& file_path)
{
    std::ifstream file(file_path);

    std::vector<char> source;

    char c;
    while (file.get(c)) {
        source.push_back(c);
    }

    return source;
}


/* Remove all but chars, which don't have meaning in brainfuck, from the source file.
 * This removes whitespace, newlines and comment chars. */
void filter_chars(std::vector<char>& source)
{
    auto new_end = std::remove_if(source.begin(), source.end(),
                                  [](char c) { return !std::strchr("<>+-[],.", c); });

    source.erase(new_end, source.end());
}


/* The actual interpreter. Goes through the source char by char and
 * acts according to brainfuck's rules. */
void interpret(std::vector<char>& source)
{
    std::vector<unsigned char> tape(30000, 0);
    int h = 0;  // the tape head

    int brace_count = 0;  // keeps track of nested braces

    int i = 0;  // the index to read the source
    while (i < source.size()) {
        switch (source[i]) {
            case '<':
                --h;
                break;
            case '>':
                ++h;
                break;
            case '+':
                ++tape[h];
                break;
            case '-':
                --tape[h];
                break;
            case '.':
                std::cout << tape[h] << std::flush;
                break;
            case ',':
                std::cin >> tape[h];
                break;

            case '[':
                if (tape[h] == 0) {
                    ++brace_count;
                    while (source[i] != ']' || brace_count != 0) {
                        ++i;
                        if (source[i] == '[') {
                            ++brace_count;
                        }
                        else if (source[i] == ']') {
                            --brace_count;
                        }
                    }
                }
                break;

            case ']':
                if (tape[h] != 0) {
                    ++brace_count;
                    while (source[i] != '[' || brace_count != 0) {
                        --i;
                        if (source[i] == ']') {
                            ++brace_count;
                        }
                        else if (source[i] == '[') {
                            --brace_count;
                        }
                    }
                }
                break;

        }
        ++i;
    }
}


int main(int argc, char* argv[])
{
    if (argc > 1) {
        std::vector<char> source = read_source(argv[1]);
        filter_chars(source);
        interpret(source);
        return 0;
    }
    else {
        std::cout << "Expected a brainfuck source file as a command line argument.\n";
        std::cout << "Terminating the program." << std::endl;
        return 1;
    }
}

Answer 1

Design

You do not validate that the program is valid before starting. You should check that '[' and ']' are all matched correctly. This can be done while loading the program.

Your memory (tape) runs from 0 -> 3000. But the ptr into this memory is not bound by this constraint. I would make sure that h is bound to this range.

Your jump backwards at the end of a block is very inefficient. Considering that when you have reached a ] you must have already passed the [ you could record this fact and simply jump back to that location.

Implementation

I would simplify loading the program (as suggested by @Edward). If you need to log it that can also be done here:

// You can make `log` /dev/null or you could have a null stream
// that does nothing with the input (its not that hard to write).
std::vector<char> loadFile(std::istream& str, std::ostream& log)
{
    int openBrace = 0;
    std::vector<char> source; 
    std::copy_if(std::istream_iterator<char>(str),
                 std::istream_iterator<char>(),
                 std::back_inserter(source), 
                 [&log, & openBrace](char c) {
                     if (c == ']') { --openBrace;}
                     if (c == '[') { ++openBrace;}
                     if (openBrace < 0) {
                         throw std::runtime_error("Poop");
                     }
                     log << c;
                     return std::strchr("<>+-[],.", c);
                 });
    if (openBrace != 0) {
        throw std::runtime_error("Poop");
    }

    return source;
}

Code Review

If you can't modify the program (I don't think brainfuck supports self modifying code) then you should pass the source by const reference to prevent accidents.

void interpret(std::vector<char>& source)

---

Is there a reason for a 30000 limit?

    std::vector<unsigned char> tape(30000, 0);

Maybe this limit can be passed as an argument from main. The default is 30000 byt a user could override the default to allow smaller/larger values.

---

This allows negative values:

    int h = 0;  // the tape head

Also you can potentially fall off the high end. So you need to watch that.

---

Are you sure that int is large enough to index all programs?

    int i = 0;  // the index to read the source

I would definitely make this std::size_t.

---

            case '<':
                --h;    // You want to allow it to fall off the left hand end?

---

            case '>':
                ++h;    // You want to allow it to fall off the right hand end?

---

            case ',':
                std::cin >> tape[h];  // Careful. The operator >> skips white space on read.
                                      // I would add std::noskipws here.

---

Here you need to validate that your inner loop does not extend beyond the end of your source.

Also this code is broken if you are already inside a brace and then hit another brace and the count is zero. As this will cause it not only jump over the current loop but also all outer loop that you are currently inside.

Also you can save the current position for quick jump back.

I would write the loop code like this:

   std::vector<std::size_t>    loopPos;
   ...

            case '[':
                if (tape[h] != 0) {
                    loopPos.push_back(i);
                }
                else {
                    ++i;  // Want to skip over the current '[' so we can start `ignoreBrace` at 1
                    for(int ignoreBrace = 1; i < source.size() && ignoreBrace != 0; ++i) {
                        if (source[i] == ']' {
                            --ignoreBrace;
                        }
                        if (source[i] == '[' {
                            ++ignoreBrace;
                        }
                    }
                    --i; // because of the ++i in the loop we are now
                         // one passed the ']' we want to move back and
                         // point at the ']' so the outer-loops ++i will
                         // increment passed it.
                }
                break;

            case ']':
                if (tape[h] != 0) {
                    i = loopPos.back();
                }
                else {
                    loopPos.pop_back();
                }
                break;

---

Personally I would put all error checking up front. That way normal code execution is at the normal indent level notinside a scope block.

Also I would allow for the possibility of the source being specified via std::cin?

int main(int argc, char* argv[])
{
    // Validate the input.
    if (argc != 1) {
        std::cout << "Expected a brainfuck source file as a command line argument.\n";
        std::cout << "Terminating the program." << std::endl;
        return 1;
    }

    // Normal operations.
    std::vector<char> source = read_source(argv[1]);
    filter_chars(source);
    interpret(source);
    return 0;
}

Answer 2

I see some things that may help you improve your program.

Use all of the required #includes

The function std::strchr is used but its declaration is in #include <cstring> which is not actually in the list of includes.

Be careful with signed and unsigned

In the interpret routine, the code compares an int i to a size_t (because that's what is returned from source.size()) but size_t is unsigned and int is signed. Instead, declare i as size_t.

Copy and filter in one step

It's not wrong, by any means, but I'd be inclined to copy and filter all at once rather than as two separate steps. Here's one way to do that:

std::vector<char> source; 
std::copy_if(std::istream_iterator<char>(std::cin), std::istream_iterator<char>(), 
             std::back_inserter(source), 
             [](char c) { return std::strchr("<>+-[],.", c); }
            );

It's not critical, of course, but this way it minimizes the number of times the vector is resized. Also note that I've altered the program to read from std::cin instead of a file. This way, it's possible to take input from a unnamed pipe, for example, adding to the flexibility of the program.

Fix the bugs

The current implementation doesn't check to see if it runs off the end of the vector while processing a brace and it doesn't check to see that h doesn't go out of bounds.