constexpr brainfuck interpreter

cbf.cpp

#include <array>
#include <cstdint>
#include <cstdio>
#include <string_view>
#include <type_traits>
#include <optional>
#include <variant>

template <class... Ts> struct overloaded : Ts... { using Ts::operator()...; };
template <class... Ts> overloaded(Ts...) -> overloaded<Ts...>;

template <class T, std::size_t Size>
class cvector {
    static_assert(std::is_default_constructible_v<T>);
    static_assert(std::is_trivially_destructible_v<T>);

    std::array<T, Size> storage{};
    std::size_t end = 0;

public:
    constexpr T& push_back(const T& elem) {
        return storage[end++] = elem;
    }
    constexpr void pop_back() {
        --end;
    }

    constexpr T& operator[](std::size_t idx) { return storage[idx]; }
    constexpr const T& operator[](std::size_t idx) const { return storage[idx]; }
    constexpr T& back() { return (*this)[end-1]; }
    constexpr const T& back() const { return (*this)[end-1]; }

    constexpr std::size_t size() const { return end; }

    constexpr T* data() { return storage.data(); }
    constexpr const T* data() const { return storage.data(); }
};

using i8 = std::int8_t;
using idx = std::size_t;

struct MoveRight {};
struct MoveLeft {};
struct Increment {};
struct Decrement {};
struct Output {};
struct Input {};
struct JumpForward {
    idx to;
};
struct JumpBack {
    idx to;
};

using Code = std::variant<
    MoveRight, 
    MoveLeft, 
    Increment, 
    Decrement, 
    Output, 
    Input,
    JumpForward,
    JumpBack
>;

template <class T>
constexpr T& as(Code& code) { return std::get<T>(code); }
template <class T>
constexpr const T& as(const Code& code) { return std::get<T>(code); }

struct Frame {
    idx start;
};

template <std::size_t Size = 1024>
using Chunk = cvector<Code, Size>;

template <std::size_t Size = 1024>
constexpr Chunk<Size> compile(std::string_view source) {
    Chunk<Size> chunk;
    cvector<Frame, 1024> frames;
    while (!source.empty()) {
        switch (source.front()) {
            case '>': 
                chunk.push_back(MoveRight{}); break;
            case '<': 
                chunk.push_back(MoveLeft{}); break;
            case '+':
                chunk.push_back(Increment{}); break;
            case '-':
                chunk.push_back(Decrement{}); break;
            case '.':
                chunk.push_back(Output{}); break;
            case ',':
                chunk.push_back(Input{}); break;

            case '[':
                chunk.push_back(JumpForward{0});
                frames.push_back(Frame{chunk.size() - 1});
                break;
            case ']':
                chunk.push_back(JumpBack{frames.back().start});
                as<JumpForward>(chunk[frames.back().start]).to = chunk.size() - 1;
                frames.pop_back();
                break;
            
            default: break;
        }
        source.remove_prefix(1);
    }
    return chunk;
}

struct Machine {
    std::array<i8, 30'000> memory{};
    std::size_t pidx = 0;
};

using Out = cvector<char, 1024>;

template <std::size_t Size>
constexpr Out execute(const Chunk<Size>& code, std::string_view input = "") {
    Machine m;
    Out output;

    for (idx ip = 0; ip != code.size(); ++ip) {
        const auto& opcode = code[ip];
        std::visit(overloaded{
            [&](MoveRight) { ++m.pidx; },
            [&](MoveLeft) { --m.pidx; },
            [&](Increment) { ++m.memory[m.pidx]; },
            [&](Decrement) { --m.memory[m.pidx]; },
            [&](Output) { output.push_back(m.memory[m.pidx]); },
            [&](Input) { m.memory[m.pidx] = input.front(); input.remove_prefix(1); },
            [&](JumpForward jmp) { if (m.memory[m.pidx] == 0) ip = jmp.to; },
            [&](JumpBack jmp) { if (m.memory[m.pidx] != 0) ip = jmp.to; },
        }, opcode);
    }

    return output;
}

constexpr auto x = execute(compile(R"(
++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.
)"));

int main() {
    std::puts(x.data());
}