2
\$\begingroup\$

I built a Brainfuck interpreter. It seems to be working. I ran the game of life and this tic-tac-toe and other programs on it. They worked fine. I'd appreciate any comments on correctness, readability and performance improvements:

#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <deque>
#include <fstream>
#include <iostream>
#include <iterator>
#include <stack>
#include <utility>
#include <vector>

#ifdef _MSC_VER
#include <ciso646>  // and/or/not
#endif              // !_MSC_VER

#ifdef __GNUC__
# define pure_attribute [[gnu::pure]]
# define const_attribute [[gnu::const]]
#else
# define pure_attribut
# define const_attribute
#endif // __GNUC__

/* "Infinite" unsigned char buffer pointer */
class Pointer {
public:
    using storage_type = std::deque<char>;
    using size_type = storage_type::size_type;

    explicit Pointer(size_type const preAllocatedMemory = 1)
            : mem_(preAllocatedMemory), index_{ 0 } {
        /* preAllocatedMemory must be at least 1 */
        assert(preAllocatedMemory != 0);
    }

    auto& operator+=(size_type const c) {
        index_ += c;
        /* Allocate memory if needed. */
        if (mem_.size() <= index_) mem_.resize(index_ + 1);
        return *this;
    }

    auto operator++() -> Pointer& { return (*this += 1); }

    auto& operator-=(size_type const c) noexcept {
        assert(index_ - c < index_);
        index_ -= c;
        return *this;
    }

    auto operator--() noexcept -> Pointer& { return (*this -= 1); }

    auto operator++(int) const->Pointer = delete; /* Expensive and pointless. Use preincrement instead */
    auto operator--(int) const->Pointer = delete; /* Expensive and pointless. Use predecrement instead */

    [[nodiscard]] auto operator*() const& -> const storage_type::value_type& {
        assert(mem_.size() > index_);
        return mem_[index_];
    }

    [[nodiscard]] auto operator*() & -> storage_type::value_type& {
        return const_cast<storage_type::value_type&>(*std::as_const(*this));
    }

private:
    [[no_unique_address]] storage_type mem_;
    [[no_unique_address]] size_type index_;
};

/* A class that contains one of "><+-.,[]" and how many times it is supposed to be executed consecutively */
class Command {
public:
    Command(char const ch, std::size_t const sz) : command_{ ch }, count_{ sz } {}
    [[nodiscard]] auto command() const noexcept { return command_; }
    [[nodiscard]] auto count() const noexcept { return count_; }

    enum ActionableCommands : char {
        PointerIncr = '>',
        PointerDecr = '<',
        CellValIncr = '+',
        CellValDecr = '-',
        Cout = '.',
        Cin = ',',
        LoopBegin = '[',
        LoopEnd = ']',
    };
private:
    char command_;
    std::size_t count_;
};

const_attribute [[nodiscard]] bool operator==(Command const com, char const ch) noexcept {
    return com.command() == ch;
}

const_attribute [[nodiscard]] bool operator!=(Command const com, char const ch) noexcept {
    return not (com == ch);
}

template <char op, typename T1, typename T2> // Workaround for "-Wconversion" being buggy
inline static void operation(T1& t, T2 const t2) noexcept {
#ifdef __GNUC__
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wconversion"
#endif // __GNUC__

    if constexpr (op == '+') t += static_cast<T1>(t2);
    else if constexpr (op == '-') t -= static_cast<T1>(t2);

#ifdef __GNUC__
#pragma GCC diagnostic pop
#endif // __GNUC__
}

/* Return false if `ch` is a comment, true if it is a command() */
bool interpret(Command const com, Pointer& p) {
    auto const ch = com.command();
    auto const count = com.count();
    switch (ch) {
        case Command::PointerIncr: {
            p += count;
            break;
        }
        case Command::PointerDecr: {
            p -= count;
            break;
        }
        case Command::CellValIncr: {
            operation<'+'>(*p, count);
            break;
        }
        case Command::CellValDecr: {
            operation<'-'>(*p, count);
            break;
        }
        case Command::Cout: {
            std::fill_n(std::ostream_iterator<unsigned char>(std::cout), count, *p);
            break;
        }
        case Command::Cin: {
            for (std::size_t i = 0; i != count; ++i) {
                std::cin >> *p;
            }
            break;
        }
        default: /* Everything else is a comment */
            return false;
    }
    return true;
}

/* Skips from `[` to the corresponding `]` taking account nested loops. */
template <typename BidirIter>
[[nodiscard]] auto skipLoop(BidirIter p) noexcept {
    assert(*p == Command::LoopBegin);
    std::size_t bracketCount = 0;
    do {
        if (*p == Command::LoopBegin)
            ++bracketCount;
        else if (*p == Command::LoopEnd)
            --bracketCount;
        ++p;
    } while (bracketCount != 0);
    return p - 1;
}

/* Is `[` or `]` */
const_attribute [[nodiscard]] auto isLoopCommand(char const ch) noexcept -> bool {
    switch (ch) {
        case Command::LoopBegin:
        case Command::LoopEnd:
            return true;
        default:
            return false;
    }
}

/* Is one of the actionable 8 characters */
const_attribute [[nodiscard]] auto isCommand(char const ch) noexcept -> bool {
    switch (ch) {
        case Command::LoopBegin:
        case Command::LoopEnd:
        case Command::PointerIncr:
        case Command::PointerDecr:
        case Command::CellValIncr:
        case Command::CellValDecr:
        case Command::Cout:
        case Command::Cin:
            return true;
        default:
            return false;
    }
}


/* Skip all characters until for one `isCommand` returns true. */
template <typename InputIter>
[[ nodiscard ]] auto skipComment(InputIter beg, InputIter const end) {
    while (beg != end and not isCommand(*beg)) ++beg;
    return beg;
}

template <typename InputIter>
[[nodiscard]] auto generateSourceCode(InputIter beg, InputIter const end) {
    std::vector<Command> source_code;
    while (beg != end) {
        auto const ch = *beg;
        std::size_t count = 0;
        if (isLoopCommand(ch)) { // Executing more than 1 loop command doesn't work.
            ++count;
            ++beg;
        }
        else if (isCommand(ch)) { // Accumulate commands
            while ((beg = skipComment(beg, end)) != end and *beg == ch) {
                ++count;
                ++beg;
            }
        }
        else {
            /* Everything else is a comment and is ignored. */
            ++beg;
        }
        source_code.emplace_back(ch, count);
    }
    return source_code;
}

int main(int const argc, char* const argv[]) {
    Pointer p;
    if (argc < 2) {
        std::cerr << "Source-code file name needed\n";
        return EXIT_FAILURE;
    }
    std::ifstream f{ argv[1] };
    if (not f.is_open()) {
        std::cerr << "Can't open the source-code file \n";
        return EXIT_FAILURE;
    }
    using StremIter = std::istream_iterator<char>;
    const auto sourceCode = generateSourceCode(StremIter{ f }, StremIter{});

    auto it = sourceCode.cbegin();
    auto const end = sourceCode.cend();

    std::stack<decltype(it)> loopPos; /* Here we log loops */
    while (it != end) {
        /* Firstly we consider loops  */
        if (*it == Command::LoopBegin) {
            /* If the current cell is zero, skip the loop. */
            if (*p == 0) {
                it = skipLoop(it);
            }
            else /* Else, log the loop starting */
            {
                loopPos.push(it);
            }
            ++it;
        }
        else if (*it == Command::LoopEnd) /* Jump to the last `]` */
        {
            assert(not loopPos.empty());
            it = loopPos.top();
            loopPos.pop();
            /* don't increment `it` */
        }
        else {
            interpret(*it, p);
            ++it;
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ [[no_unique_address]] is C++20 \$\endgroup\$ – Aganju Jan 2 at 16:31
  • \$\begingroup\$ @Aganju yes, you're right. Thank you for the feedback. Since a confirming C++17 compiler should ignore unrecognized attributes, it should be alright. \$\endgroup\$ – Ayxan Haqverdili Jan 2 at 17:09
  • \$\begingroup\$ If it is alright for no_unique_address then why do this # define pure_attribute [[gnu::pure]] You should be consistent in how you apply attributes. \$\endgroup\$ – Martin York Jan 2 at 19:29
  • \$\begingroup\$ @MartinYork Which approach would you recommend? Ignored attributes cause warnings, do #define seems a little cleaner? I am open for all suggestions. \$\endgroup\$ – Ayxan Haqverdili Jan 2 at 20:13
  • \$\begingroup\$ @Ayxan I don't mind either approach. But one of the core principles in programming is consistency. I don't want to have to figure out two different approaches in the same code base. \$\endgroup\$ – Martin York Jan 2 at 22:05
3
\$\begingroup\$

Be a bit more consistent formatting the code

You are not very consistent with spaces around operators in function declarations, for example:

auto operator--() noexcept -> Pointer& { return (*this -= 1); }
auto operator++(int) const->Pointer = delete;

Also, I recommend that even for one-liner functions, you put the body of the function on a separate line. If the classes were split out into their own source and header files, then it would help when looking at the declaration of the class in the header file, because you can then more easily see which member functions are merely declared, or whether their definition is available in-line.

Use more whitespace to clarify the structure of your code

Use empty lines to separate sections inside functions from each other visually, so it is easier to see the structure of your code. For example, to make it easier to distinguish initialization, the main loop and the return statement in skipLoop():

template <typename BidirIter>
[[nodiscard]] auto skipLoop(BidirIter p) noexcept {
    assert(*p == Command::LoopBegin);
    std::size_t bracketCount = 0;

    do {
        if (*p == Command::LoopBegin)
            ++bracketCount;
        else if (*p == Command::LoopEnd)
            --bracketCount;

        ++p;
    } while (bracketCount != 0);

    return p - 1;
}

Avoid const-casting

You don't need a const version of operator*(). The following should be enough:

[[nodiscard]] auto operator*() & -> storage_type::value_type& {
    assert(mem_.size() > index_);
    return mem_[index_];
}

This avoids the complicated const-casting that is going on. If you really need const Pointers in the future, I would just write two copies of this function without any casts.

Safe checking of integer overflow

You have the following check in operator-=():

assert(index_ - c < index_);

Where both index_ and c are of type size_type. This works for storage_type = std::deque<char>, since its std::dequeue::size_type is guaranteed to be an unsigned integer type. However, assuming that you want this code to be generic enough so you can safely use any other container, you should not make this assumption.

If size_type were a signed integer type, then since signed integer wraparound is undefined behaviour in C++, the compiler is free to assume that wraparound never happens, and so it will likely optimize away this test. The proper way to test this is:

assert(c > 0 && c <= index_);

Also note that you have no matching assertion in operator+=().

Consider using enum class

Make ActionableCommands an enum class. Yes, this will require a lot more static_casting, but it results in safer code. The compiler can warn if you miss a case in switch-statements, and you can't accidentily have something that is not a command implicitly converted to one.

Split operation<>() in separate functions

I don't see any good reason for a function operation() that is templated on a constant, and then does something completely different depending on that constant. Just make two functions, operation_plus() and operation_minus(). But:

Don't hide potentially unsafe static_casts

The sole reason for operation<>() seems to be to do a static_cast and to tell the compiler to ignore potential unsafe behavior. It would be better if you could just write the following in interpret():

case Command::CellVarIncr:
    *p += count;
    break;
case Command::CellVarDecr:
    *p -= count;
    break;

And if the compiler ever warns, find a way to fix the code instead of disabling the warnings.

Check for read errors when reading from a file

Even if you succesfully opened a std::ifstream, there can be an error later on while reading from the file. So be sure to check its state after reading in the source code, using if (f.fail()) { /* handle error */ }.

Don't overengineer

This might be a subjective thing, but I feel that you are overengineering your code. If you were implementing a library, a lot of the templating and attributes would certainly be justified, but if you are just writing an executable that parses and executes Brainfuck code, it's a bit of a wasted effort. KISS and YAGNI.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you for the review. Here are a few questions/points: \$\endgroup\$ – Ayxan Haqverdili Jan 4 at 17:22
  • \$\begingroup\$ (Avoid const-casting) I understand the suggestion to keep the code simple, but are you suggesting to duplicate the code instead? I think this is one of the very few situations const_cast was even created for. So I am thinking it's a bit of well known already? I may be wrong. \$\endgroup\$ – Ayxan Haqverdili Jan 4 at 17:24
  • \$\begingroup\$ (Don't hide potentially unsafe static_casts) Originally I had an explicit cast inplace instead of the function, but in my version of GCC -Wconversion was buggy. It was complaining about the explicit cast I had there, which shouldn't happen (it wasn't happening on MSVC) so I googled it, and turns out it was a bug. Hence the function to work around the compiler bug. \$\endgroup\$ – Ayxan Haqverdili Jan 4 at 17:26
  • \$\begingroup\$ (Split operation<>() in separate functions) "I don't see any good reason for a function operation() that is templated on a constant, and then does something completely different depending on that constant. Just make two functions, operation_plus() and operation_minus()". Again, this function wasn't a planned thing, and I was planning to remove it once we upgraded to a newer and hopefully bug-free version of GCC. Here I was merely trying to avoid the duplication of the warning disabling bit of code so I can more easily identify and remove it all later on. \$\endgroup\$ – Ayxan Haqverdili Jan 4 at 17:30
  • \$\begingroup\$ I agree with everything else you commented (+1). \$\endgroup\$ – Ayxan Haqverdili Jan 4 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.