I decided to try and write a Brainfuck interpreter in C as an exercise. This could have been written in one file, but I decided to split it up into a State "class" and an some interpreter methods.

An example test-run with a ROT13 implementation in Brainfuck:

const char* source_buffer = // Code in above link. Read from file in my test.
interpret_with_std_io(source_buffer);

// In the console

Hello World!
Uryyb Jbeyq!

I'd like suggestions on anything, but specifically:

• I'm fairly new to C. I'd like to know if I'm still making any newbie mistakes.

• A few parts of my interpreter/state separation feel clumsy. 99% of the state code requires no knowledge of the source code. [ unfortunately has the potential to jump forwards, so unless I pre-compute all the possible jumps, I need access to the source so I can search for its matching ]. I originally had the two hande_loop_ functions in the state code, then moved it to the interpreter, then back to the state. As a consequences though, my interpreter function dispatch_command now requires access to the source, solely for [.

• I needed a variable-sized stack to store the jump points, and decided on a linked list. It seems perfect here. Am I handling it OK?

• The mismatched-brace handling logic is frustrating. The handle_loop_ functions return false when they detect a mismatched brace. I need to manually feed this result all the way back to the main interpret_with_state function, just so I know whether an error happened. Exceptions would be perfect here, but obviously they aren't an option. Is there a better way of handling this?

It's broken up into 3 files: helpers.c (for safe allocation helpers), state.c and interpreter.c.

Helpers

#ifndef HELPERS_H
#define HELPERS_H

#include <stdlib.h>

// Prints an error message to stderr if ptr is NULL
// Message is in the form "Could not allocate space for %s.".
void ensure_allocation(const void* ptr, const char* allocation_reason);

// Attempts to allocate the requested amount of memory and asserts the validity of the
//  returned pointer using ensure_allocation before returning
void* terminating_malloc(size_t bytes, const char* allocation_reason);

#endif

#include <stdio.h>

#include "helpers.h"

void ensure_allocation(const void* ptr, const char* allocation_reason) {
    if (!ptr) {
        fprintf(stderr, "Could not allocate space for %s.", allocation_reason);
        exit(EXIT_FAILURE);
    }
}

void* terminating_malloc(size_t bytes, const char* allocation_reason) {
    void* const ptr = malloc(bytes);

    ensure_allocation(ptr, allocation_reason);

    return ptr;
}

State

#ifndef STATE_H
#define STATE_H

#include <stdlib.h>
#include <stdbool.h>

#define STANDARD_CELL_BUFFER_LENGTH 30000

typedef unsigned char Cell_Type;

typedef struct Jump_Node {
    size_t jump_position;
    struct Jump_Node* next;

} Jump_Node;

typedef struct {
    size_t instruction_pointer;
    size_t cell_pointer;

    Cell_Type* cell_buffer;
    size_t buffer_length;

    Jump_Node* jump_nodes_head;

} State;

void init_state(State*, size_t buffer_length);

// Initializes it with a buffer with the length of STANDARD_CELL_BUFFER_LENGTH
void init_standard_state(State*);


void advance_instruction_pointer(State*);


void increment_current_cell(State*); // +
void decrement_current_cell(State*); // -


// bool returns indicate whether or not the new cell pointer is "inbounds"
bool move_cell_pointer_left(State*); // <
bool move_cell_pointer_right(State*); // >

Cell_Type get_current_cell(State*); // .
void set_current_cell(State*, Cell_Type new_cell_contents); // ,


// Return false and have no effect if a matching brace isn't found, and it was required for operation
// Return true otherwise
bool handle_loop_start(State*, const char* source); // [
bool handle_loop_end(State*); // ]



// Frees the cell_buffer and the jump nodes; not the State pointer
void free_state(const State*);

#endif

#include <stdlib.h>
#include <stdbool.h>
#include <stdio.h>
#include <string.h>

#include "helpers.h"
#include "state.h"

// ----- Jump Nodes -----

static void init_jump_node(Jump_Node* node, size_t position, Jump_Node* next_node) {
    node->jump_position = position;
    node->next = next_node;
}

static void free_jump_nodes(const Jump_Node* head) {
    const Jump_Node* current = head;

    while (current) {
        Jump_Node* next = current->next;
        free((Jump_Node*)current);

        current = next;
    }
}

// ----- State -----

void init_state(State* state, size_t buffer_length) {
    size_t const buffer_size = sizeof(Cell_Type) * buffer_length;
    Cell_Type* const cell_buffer = terminating_malloc(buffer_size, "cell buffer");
    memset(cell_buffer, 0, buffer_size);

    state->instruction_pointer = 0;
    state->cell_pointer = 0;
    
    state->cell_buffer = cell_buffer;
    state->buffer_length = buffer_length;

    state->jump_nodes_head = NULL;
}

void init_standard_state(State* state) {
    init_state(state, STANDARD_CELL_BUFFER_LENGTH);
}

void advance_instruction_pointer(State* state) {
    state->instruction_pointer++;
}

static void add_to_current_cell(State* state, Cell_Type n_to_add) {
    size_t const cell_ptr = state->cell_pointer;

    state->cell_buffer[cell_ptr] += n_to_add;
}

void increment_current_cell(State* state) {
    add_to_current_cell(state, 1);
}

void decrement_current_cell(State* state) {
    add_to_current_cell(state, -1);
}

static bool move_cell_pointer_by(State* state, int move_by) {
    state->cell_pointer += move_by;

    size_t const c_ptr = state->cell_pointer;
    return c_ptr > 0 && c_ptr < state->buffer_length;
}

bool move_cell_pointer_left(State* state) {
    return move_cell_pointer_by(state, -1);
}

bool move_cell_pointer_right(State* state) {
    return move_cell_pointer_by(state, 1);
}

Cell_Type get_current_cell(State* state) {
    const size_t cell_ptr = state->cell_pointer;

    return state->cell_buffer[cell_ptr];
}

static bool current_cell_is_zero(State* state) {
    return get_current_cell(state) == 0;
}

void set_current_cell(State* state, Cell_Type new_cell_contents) {
    const size_t cell_ptr = state->cell_pointer;

    state->cell_buffer[cell_ptr] = new_cell_contents;
}

// Returns the index in the source of the brace matching the opening brace at the given position.
// Returns -1 if a matching brace isn't found.
static int matching_brace_position(size_t opening_brace_position, const char* source) {
    int depth = 1;

    for (int i = opening_brace_position + 1; ; i++) {
        const char command = source[i];

        if (command == '\0') {
            return -1;

        } else if (command == '[') {
            depth += 1;

        } else if (command == ']') {
            depth -= 1;

            if (depth == 0) {
                return i;
            }
        }
    }
}

bool handle_loop_start(State* state, const char* source) {
    if (current_cell_is_zero(state)) { // Skip the loop
        const int pos = matching_brace_position(state->instruction_pointer, source);

        if (pos == -1) {
            return false;

        } else {
            state->instruction_pointer = pos;
        }

    } else { // Set a jump back point
        Jump_Node* const node = terminating_malloc(sizeof(Jump_Node), "jump node");
        init_jump_node(node, state->instruction_pointer, state->jump_nodes_head);

        state->jump_nodes_head = node;
    }

    return true;
}

bool handle_loop_end(State* state) {
    const Jump_Node* const popped_jump = state->jump_nodes_head;

    if (popped_jump) {
        if (current_cell_is_zero(state)) {
            state->jump_nodes_head = popped_jump->next;
            free((Jump_Node*)popped_jump);

        } else {
            size_t const recorded_position = popped_jump->jump_position;
            state->instruction_pointer = recorded_position;
        }

        return true;

    } else {
        return false;
    }
}

void free_state(const State* state) {
    free(state->cell_buffer);
    free_jump_nodes(state->jump_nodes_head);
}

static void dbg_set_cell(State* state, size_t cell_ptr, Cell_Type contents) {
    state->cell_buffer[cell_ptr] = contents;
}

Interpreter

#ifndef INTERPRETER_H
#define INTERPRETER_H

#include <stdio.h>

// Interpret the supplied code either using the standard io streams, or the supplied ones.
void interpret(const char* code, FILE* in_stream, FILE* out_stream);
void interpret_with_std_io(const char* code);

#endif

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#include "state.h"
#include "interpreter.h"
#include "helpers.h"

// Returns a wrapped cell_pointer in the range 0 <= cell_pointer < buffer_size
// Requires that cell_pointer isn't more than buffer_size out of bounds.
static size_t wrap_cell_pointer(int signed_cell_pointer, size_t buffer_size) {
    int const scp = signed_cell_pointer;

    if (scp < 0) {
        return buffer_size + scp;
    
    } else if (scp >= (int)buffer_size) {
        return scp - buffer_size;
    
    } else {
        return scp;
    }
}

static void wrap_state_cell_pointer(State* state) {
    state->cell_pointer = wrap_cell_pointer(state->cell_pointer, state->buffer_length);
}

// Gets input from the supplied stream
// Returns a falsey null character if the input was out of range
// RELIES ON UCHAR_MAX!!! If Cell_Type is altered from an unsigned char,
//  this must be changed accordingly!
static Cell_Type read_input_from_stream(FILE* in_stream) {
    int const input = getc(in_stream);

    return (input > UCHAR_MAX || input < 0) ? '\0' : input;
}

// This must also be changed if Cell_Type is changed!
static void print_to_stream(FILE* out_stream, Cell_Type output) {
    fprintf(out_stream, "%c", output);
    fflush(out_stream);
}

static bool dispatch_command(State* state, char command, const char* source, FILE* in_stream, FILE* out_stream) {
    switch (command) {
        case '+':
            increment_current_cell(state);
            break;

        case '-':
            decrement_current_cell(state);
            break;

        case '<':
            move_cell_pointer_left(state);
            wrap_state_cell_pointer(state);
            break;

        case '>':
            move_cell_pointer_right(state);
            wrap_state_cell_pointer(state);
            break;

        case '[': {
            const bool matching = handle_loop_start(state, source);

            if (!matching) {
                puts("Unmatched [ found.\n");
                return false;
            }

            break;
        }

        case ']': {
            bool const matching = handle_loop_end(state);

            if (!matching) {
                puts("Unmatched ] found.\n");
                return false;
            }

            break;
        } 

        case ',': {
            Cell_Type const input = read_input_from_stream(in_stream);
            if (input) {
                set_current_cell(state, input);
            }

            break;
        }

        case '.': {
            Cell_Type const output = get_current_cell(state);
            print_to_stream(out_stream, output);

            break;
        }
    }

    return true;
}

static void interpret_with_state(State* state, const char* source, FILE* in_stream, FILE* out_stream) {
    while (true) {
        char const command = source[state->instruction_pointer];

        if (command == '\0') {
            break;

        } else {
            bool const evald_ok = dispatch_command(state, command, source, in_stream, out_stream);

            if (!evald_ok) {
                return;
            }

            advance_instruction_pointer(state);
        }
    }
}

void interpret(const char* code, FILE* in_stream, FILE* out_stream) {
    State state;
    init_standard_state(&state);

    interpret_with_state(&state, code, in_stream, out_stream);

    free_state(&state);
}

void interpret_with_std_io(const char* code) {
    interpret(code, stdin, stdout);
}