C brainfuck interpreter

brainfuck.c

// brainfuck interpreter
//
// based on the example distributed with the crystal source code
#include <mine.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#ifndef INITIAL_SIZE
#define INITIAL_SIZE 5
#endif
#ifndef INITIAL_LEFTSTACK_SIZE
#define INITIAL_LEFTSTACK_SIZE INITIAL_SIZE
#endif
#ifndef INITIAL_JUMP_TABLE_SIZE
#define INITIAL_JUMP_TABLE_SIZE INITIAL_SIZE
#endif

#ifndef RAISE
#define RAISE(...)                                                             \
  {                                                                            \
    fprintf(stderr, __VA_ARGS__);                                              \
    exit(1);                                                                   \
  }
#endif

typedef struct {
  int *tape;
  int pos;
  int size;
} Tape;

Tape *newTape() {
  int *tape = malloc(1 * sizeof(int));
  tape[0] = 0;
  Tape *nt = malloc(1 * sizeof(Tape));
  *nt = (Tape){.tape = tape, .pos = 0, .size = 0};
  return nt;
}

void tapeFree(Tape *self) {
  free(self->tape);
  free(self);
}

int get(Tape *self) { return self->tape[self->pos]; }
int inc(Tape *self) { return ++self->tape[self->pos]; }
int dec(Tape *self) { return --self->tape[self->pos]; }
int advance(Tape *self) {
  self->pos++;
  if (self->pos >= self->size) {
    self->size = self->pos + 1;
    self->tape = realloc(self->tape, self->size * sizeof(int));
    self->tape[self->pos] = 0;
  }
  return self->tape[self->pos];
}
int devance(Tape *self) {
  if (self->pos <= 0)
    RAISE("invalid index %d, must be greater than 0.\n", self->pos);
  return self->tape[--self->pos];
}

typedef struct {
  int location;
  int destination;
} BracketPair;

typedef struct {
  BracketPair *data;
  size_t size;
  size_t capacity;
} BracketTable;

BracketTable *newBracketTable() {
  BracketTable *bt = malloc(1 * sizeof(BracketTable));
  *bt = (BracketTable){.capacity = INITIAL_JUMP_TABLE_SIZE, .size = 0};
  bt->data = malloc(1 * sizeof(BracketTable));
  return bt;
}

void freeBracketTable(BracketTable *self) {
  free(self->data);
  free(self);
}

BracketTable *bracketTableResize(BracketTable *self) {
  self->data =
      realloc(self->data, sizeof(BracketPair *) * (self->capacity *= 2));
  return self;
}

void addBracketPair(BracketTable *self, BracketPair pair) {
  if (self->size > self->capacity)
    RAISE(
        "Implementation error. table size (%lu) was greater than its capacity "
        "(%lu)\n",
        self->size, self->capacity);
  if (self->capacity == self->size)
    bracketTableResize(self);
  self->size++;
  self->data[self->size - 1] = pair;
}

void addBrackets(BracketTable *self, int location, int destination) {
  addBracketPair(
      self, (BracketPair){.location = location, .destination = destination});
}

int jump(BracketTable *self, int location) {
  BracketPair *pair;
  for (size_t i = 0; i < self->size; i++) {
    pair = self->data + i;
    if (pair->location == location)
      return pair->destination;
  }
  RAISE("matching bracket not found for bracket at character %d\n", location);
}

typedef struct {
  int *data;
  size_t size;
  size_t pos;
  bool empty;
} StackData;

StackData *newStack() {
  StackData *sd = malloc(sizeof(StackData));
  *sd = (StackData){.size = INITIAL_LEFTSTACK_SIZE, .pos = 0, .empty = true};
  sd->data = malloc(INITIAL_LEFTSTACK_SIZE * sizeof(int));
  return sd;
}

void freeStack(StackData *self) {
  free(self->data);
  free(self);
}

void stackResize(StackData *self) {
  self->data = realloc(self->data, self->size *= 2);
}

int stackPush(StackData *self, int value) {
  if (self->size < self->pos)
    RAISE("Implementation error. Stack size (%lu) was less than the current "
          "position (%lu)\n",
          self->size, self->pos);
  if (self->size == self->pos)
    stackResize(self);
  self->pos++;
  self->data[self->pos] = value;
  printf("size: (%lu)\tpos: (%lu)\tdata: (%d)\n", self->size, self->pos,
         self->data[self->pos]);
  self->empty = false;
  return value;
}

int stackPeek(StackData *self) {
  if (self->empty)
    RAISE("tried to peek from empty stack");
  return self->data[self->pos];
}
int stackPop(StackData *self) {
  if (self->empty)
    RAISE("tried to pop from empty stack");
  self->pos--;
  if (self->pos == 0) {
    self->empty = true;
  }
  return self->data[self->pos];
}

typedef struct {
  char *text;
  size_t textSize;
  StackData *leftStack;
  size_t pos;
  BracketTable *jumpTable;
} Program;

Program *newProgram() {
  Program *p = malloc(1 * sizeof(Program));
  *p = (Program){
      .jumpTable = newBracketTable(), .leftStack = newStack(), .pos = 0};
  return p;
}

void freeProgram(Program *self) {
  free(self->text);
  free(self);
}

void pushChar(Program *self, char c) {
  if (self->textSize < self->pos)
    RAISE(
        "Implementation error: string size (%lu) was smaller than the current "
        "position (%lu).\n",
        self->textSize, self->pos);
  if (self->textSize == self->pos)
    self->text = realloc(self->text, self->textSize *= 2);
  printf("pos: %lu\ttextSize: %lu\n", self->pos, self->textSize);
  self->text[self->pos++] = c;
}

bool isBrainfuck(char character) {
  char *testChar = "[]<>+-,.";
  do {
    if (character == *testChar)
      return true;
  } while (*(testChar++));
  return false;
}

void parseChar(Program *self, char c) {
  if (isBrainfuck(c)) {
    pushChar(self, c);
    if (c == '[')
      stackPush(self->leftStack, self->pos);
    else if (c == ']') {
      int left = stackPop(self->leftStack);
      addBrackets(self->jumpTable, left, self->pos);
      addBrackets(self->jumpTable, self->pos, left);
    }
    self->pos++;
  }
}

void parseText(Program *self, char *text) {
  char thisChar;
  while ((thisChar = text[self->pos + 1]))
    parseChar(self, thisChar);
}

brainfuckSpec.c

#include <bsd/string.h>

#include "bdd-for-c.h"
#include "brainfuck.c"

bool compareStrings(char *a, char *b) {
  int i = 0;
  char aChar, bChar; // the individual char to be checked
  while ((aChar = a[i]) && (bChar = b[i])) {
    unless(aChar == bChar) return false;
    i++;
  }
  unless(aChar == 0 && bChar == 0) return false;
  return true;
}
spec("brainfuck") {
  describe("isBrainfuck()") {
    context("'['") {
      it("is brainfuck") { check(isBrainfuck('[')); }
    }
    context("'x'") {
      it("is not brainfuck") { check(!isBrainfuck('x')); }
    }
  }
  describe("Tape") {
    it("works") {
      Tape *testTape = newTape();
      check(get(testTape) == 0);
      check(inc(testTape) == 1);
      check(advance(testTape) == 0);
      check(dec(testTape) == -1);
      check(devance(testTape) == 1);
      check(advance(testTape) == -1);
    }
  }
  describe("bracket table") {
    it("stores a pair, then finds it later") {
      BracketTable *table = newBracketTable();
      addBrackets(table, 6, 7);
      addBrackets(table, 8, 9);
      check(jump(table, 6) == 7);
      check(jump(table, 8) == 9);
    }
  }
  describe("stack data") {
    it("can be pushed to and popped from") {
      StackData *data = newStack();
      check(data->empty);
      check(stackPush(data, 42) == 42);
      check(data->pos == 1);
      check(!data->empty);
      check(stackPop(data) == 42);
      check(data->empty);
    }
    it("expands when its max-size is reached") {
      StackData *data = newStack();
      for (int i = 1; i < 10; i++) {
        check(stackPush(data, i) == i);
      }
      check(!data->empty);
      for (int i = 9; i >= 0; i--) {
        printf("size: (%lu)\tpos: (%lu)\tdata: (%d)\ti: (%d)\n", data->size,
               data->pos, data->data[data->pos], i);
        check(stackPop(data) == i);
      }
      check(data->empty);
    }
  }
}