path: root/lib94/warrior.cpp

#include <lib94/lib94.hpp>
#include <functional>
#include <cassert>
#include <fstream>
#include <cctype>
#include <cstdio>
#include <memory>
#include <map>

namespace lib94 {

  static const std::string opcode_strings[] = {
    "dat", "mov", "add", "sub", "mul", "div", "mod", "jmp",
    "jmz", "jmn", "djn", "seq", "sne", "slt", "spl", "nop"
  };

  static const std::string modifier_strings[] = {
    "a", "b", "ab", "ba", "f", "x", "i"
  };

  static const char mode_chars[] = "#$*@{<}>";

  std::string instruction_to_string(const instruction &instr) {
    return
      opcode_strings[instr.op] + '.' + modifier_strings[instr.mod] + ' ' +
      mode_chars[instr.amode] + std::to_string(instr.anumber) + ", " +
      mode_chars[instr.bmode] + std::to_string(instr.bnumber);
  }

  static number_t real_mod(number_t input) {
    return (input % LIB94_CORE_SIZE + LIB94_CORE_SIZE) % LIB94_CORE_SIZE;
  }

  typedef std::map<std::string, number_t> label_set;
  typedef std::map<std::string, number_t> inline_macro_set;

  struct number_expr_exception : public std::exception {
    std::string message;
  };

  struct number_expr {
    virtual number_t to_number(number_t our_offset, const inline_macro_set &inline_macros, const label_set &labels) = 0;
  };

  struct identifier_number_expr : public number_expr {
    std::string identifier;

    virtual number_t to_number(number_t our_offset, const inline_macro_set &inline_macros, const label_set &labels) {
      auto result = inline_macros.find(identifier);
      if (result != inline_macros.end())
        return result->second;

      result = labels.find(identifier);
      if (result != labels.end())
        return real_mod(result->second - our_offset);

      number_expr_exception ex;
      ex.message = "unknown label or inline macro";
      throw ex;
    }
  };

  struct number_number_expr : public number_expr {
    number_t value;

    virtual number_t to_number(number_t, const inline_macro_set &, const label_set &) {
      return value;
    }
  };

  struct op_number_expr : public number_expr {
    std::unique_ptr<number_expr> left;
    std::unique_ptr<number_expr> right;
    std::function<number_t (number_t, number_t)> op;

    virtual number_t to_number(number_t our_offset, const inline_macro_set &inline_macros, const label_set &labels) {
      number_t left_result = left->to_number(our_offset, inline_macros, labels);
      number_t right_result = right->to_number(our_offset, inline_macros, labels);
      return op(left_result, right_result);
    }
  };

  struct negative_number_expr : public number_expr {
    std::unique_ptr<number_expr> inner;

    virtual number_t to_number(number_t our_offset, const inline_macro_set &inline_macros, const label_set &labels) {
      return LIB94_CORE_SIZE - inner->to_number(our_offset, inline_macros, labels);
    }
  };

  static bool valid_identifier(std::string candidate) {
    if (candidate == "")
      return false;

    if (!isalpha(candidate[0]) && candidate[0] != '_')
      return false;

    for (char ch : candidate)
      if (!isalnum(ch) && ch != '_')
        return false;

    return true;
  }

  static size_t find_respecting_parentheses(std::string part, std::string candidates) {
    size_t layers = 0;

    for (int i = part.size() - 1; i >= 0; --i)
      if (layers == 0 && candidates.find(part[i]) != std::string::npos) {

        if (part[i] == '-' || part[i] == '+') {
          for (int j = i - 1; j >= 0; --j) {
            if (isalnum(part[j]) || part[j] == '_' || part[j] == ')')
              return i;
            if (part[j] != ' ')
              break;
          }
          continue;
        }

        return i;
      }

      else if (part[i] == ')')
        ++layers;
      else if (part[i] == '(')
        --layers;

    return std::string::npos;
  }

  static std::unique_ptr<number_expr> to_number_expr(std::string part);

  static std::unique_ptr<number_expr> make_op_expr(std::string part, size_t split) {
    std::string left = part.substr(0, split);
    std::string right = part.substr(split + 1);

    auto left_expr = to_number_expr(left);
    auto right_expr = to_number_expr(right);

    auto expr = std::make_unique<op_number_expr>();
    expr->left = std::move(left_expr);
    expr->right = std::move(right_expr);

    switch (part[split]) {

      case '+':
        expr->op = [](number_t a, number_t b) {
          return real_mod(a + b);
        };
        break;

      case '-':
        expr->op = [](number_t a, number_t b) {
          return real_mod(a - b);
        };
        break;

      case '*':
        expr->op = [](number_t a, number_t b) {
          return real_mod(a * b);
        };
        break;

      case '/':
        expr->op = [](number_t a, number_t b) {
          if (b == 0) {
            number_expr_exception ex;
            ex.message = "division by zero";
            throw ex;
          }
          return a / b;
        };
        break;

      case '%':
        expr->op = [](number_t a, number_t b) {
          if (b == 0) {
            number_expr_exception ex;
            ex.message = "modulo by zero";
            throw ex;
          }
          return a % b;
        };
        break;

    }

    return expr;
  }

  static std::string trim_spaces(std::string str) {
    size_t start = str.find_first_not_of(' ');
    size_t end = str.find_last_not_of(' ') + 1;
    if (start == std::string::npos)
      return "";
    return str.substr(start, end - start);
  }

  static std::unique_ptr<number_expr> to_number_expr(std::string part) {
    part = trim_spaces(part);
    if (part == "") {
      number_expr_exception ex;
      ex.message = "empty expression";
      throw ex;
    }

    size_t split = find_respecting_parentheses(part, "+-");
    if (split == std::string::npos)
      split = find_respecting_parentheses(part, "*/%");
    if (split != std::string::npos)
      return make_op_expr(part, split);

    if (part[0] == '(' && part[part.size() - 1] == ')')
      return to_number_expr(part.substr(1, part.size() - 2));

    if (part[0] == '+')
      return to_number_expr(part.substr(1));

    if (part[0] == '-') {
      std::unique_ptr<number_expr> inner = to_number_expr(part.substr(1));
      std::unique_ptr<negative_number_expr> expr = std::make_unique<negative_number_expr>();
      expr->inner = std::move(inner);
      return expr;
    }

    size_t count;
    number_t number = 0;

    try {
      number = real_mod(std::stoul(part, &count));
    }
    catch (const std::exception &e) {
      count = 0;
    }

    if (count == part.size()) {
      std::unique_ptr<number_number_expr> expr = std::make_unique<number_number_expr>();
      expr->value = number;
      return expr;
    }

    if (valid_identifier(part)) {
      std::unique_ptr<identifier_number_expr> expr = std::make_unique<identifier_number_expr>();
      expr->identifier = part;
      return expr;
    }

    number_expr_exception ex;
    ex.message = "unknown expression form";
    throw ex;
  }

  //using unqiue_ptr to refer to this in case i add more types in the future
  struct assert_expr {
    std::unique_ptr<number_expr> left;
    std::unique_ptr<number_expr> right;
    std::function<bool (number_t, number_t)> comparison;

    bool is_true(number_t our_offset, const inline_macro_set &inline_macros, const label_set &labels) {
      number_t left_result = left->to_number(our_offset, inline_macros, labels);
      number_t right_result = right->to_number(our_offset, inline_macros, labels);
      return comparison(left_result, right_result);
    }
  };

  struct assert_expr_exception : public std::exception {
    std::string message;
  };

  static std::optional<std::unique_ptr<assert_expr>> try_make_assert_expr(std::string part, std::string sep, std::function<bool (number_t, number_t)> comparison) {
    size_t pos = part.find(sep);
    if (pos == std::string::npos)
      return {};

    std::unique_ptr<number_expr> left, right;

    left = to_number_expr(part.substr(0, pos));
    right = to_number_expr(part.substr(pos + sep.size()));

    auto expr = std::make_unique<assert_expr>();
    expr->left = std::move(left);
    expr->right = std::move(right);
    expr->comparison = comparison;

    return expr;
  }

  static std::unique_ptr<assert_expr> to_assert_expr(std::string part) {
    try {
      auto result = try_make_assert_expr(part, "==", [](number_t a, number_t b) {return a == b;});
      if (result)
        return std::move(result.value());

      result = try_make_assert_expr(part, "<=", [](number_t a, number_t b) {return a <= b;});
      if (result)
        return std::move(result.value());

      result = try_make_assert_expr(part, ">=", [](number_t a, number_t b) {return a >= b;});
      if (result)
        return std::move(result.value());

      result = try_make_assert_expr(part, "!=", [](number_t a, number_t b) {return a != b;});
      if (result)
        return std::move(result.value());

      result = try_make_assert_expr(part, "<", [](number_t a, number_t b) {return a < b;});
      if (result)
        return std::move(result.value());

      result = try_make_assert_expr(part, ">", [](number_t a, number_t b) {return a > b;});
      if (result)
        return std::move(result.value());
    }
    catch (const number_expr_exception &iex) {
      assert_expr_exception ex;
      ex.message = iex.message;
      throw ex;
    }

    assert_expr_exception ex;
    ex.message = "unknown assert operation";
    throw ex;
  }

  struct future_instruction {
    unsigned source_line;
    opcode op;
    modifier mod;
    mode amode;
    mode bmode;
    std::unique_ptr<number_expr> anumber;
    std::unique_ptr<number_expr> bnumber;
  };

  struct assertion {
    size_t source_line;
    std::unique_ptr<assert_expr> expr;
    number_t offset;
  };

  struct preprocessed_line {
    unsigned source_line;
    std::string the_line;
  };

  struct info_from_preprocessor {
    std::vector<std::unique_ptr<assert_expr>> assertions;
    std::optional<std::string> name;
    std::optional<std::string> author;
  };

  static void preprocess_until_end_block(info_from_preprocessor &info, std::vector<preprocessed_line> &into, unsigned &next_line_number, std::string &source, std::optional<std::string> block_ender) {
    while (source != "") {

      size_t newline = source.find('\n');
      std::string line;

      if (newline == std::string::npos) {
        line = source;
        source = "";
      }
      else {
        line = source.substr(0, newline);
        source = source.substr(newline + 1);
      }

      unsigned line_number = next_line_number;
      ++next_line_number;

      size_t semicolon = line.find(';');
      if (semicolon != std::string::npos) {
        std::string comment = trim_spaces(line.substr(semicolon + 1));
        line = line.substr(0, semicolon);

        if (comment.starts_with("assert ")) {
          std::unique_ptr<assert_expr> assertion;

          try {
            assertion = std::move(to_assert_expr(comment.substr(7)));
          }
          catch (const assert_expr_exception &iex) {
            compiler_exception ex;
            ex.line_number = line_number;
            ex.message = iex.message;
          }

          info.assertions.push_back(std::move(assertion));
        }

        else if (comment.starts_with("name ")) {

          if (info.name.has_value()) {
            compiler_exception ex;
            ex.line_number = line_number;
            ex.message = "duplicate name comment";
            throw ex;
          }

          info.name = trim_spaces(comment.substr(5));
        }

        else if (comment.starts_with("author ")) {

          if (info.author.has_value()) {
            compiler_exception ex;
            ex.line_number = line_number;
            ex.message = "duplicate author comment";
            throw ex;
          }

          info.author = trim_spaces(comment.substr(7));
        }
      }

      line = trim_spaces(line);

      if (block_ender.has_value() && line == block_ender.value())
        return;

      if (line.starts_with("for ")) {

        number_t repeats;
        size_t count;
        try {
          repeats = real_mod(std::stoul(line.substr(4), &count));
        }
        catch (const std::exception &e) {
          count = 0;
        }

        if (!count || count != line.size() - 4) {
          compiler_exception ex;
          ex.line_number = line_number;
          ex.message = "bad for argument";
          throw ex;
        }

        std::vector<preprocessed_line> inside_for;
        preprocess_until_end_block(info, inside_for, next_line_number, source, "rof");

        for (number_t i = 0; i < repeats; ++i)
          for (const preprocessed_line &l : inside_for)
            into.push_back(l);

        continue;
      }

      into.push_back((preprocessed_line){.source_line = line_number, .the_line = line});
    }

    if (block_ender.has_value()) {
      compiler_exception ex;
      ex.line_number = next_line_number;
      ex.message = "end of file encountered where " + block_ender.value() + " expected";
      throw ex;
    }
  }

  struct future_inline_macro {
    std::string name;
    unsigned source_line;
    std::unique_ptr<number_expr> definition;
    number_t offset;
  };

  typedef std::vector<future_inline_macro> future_inline_macro_set;

  struct org_info {
    std::unique_ptr<number_expr> expr;
    number_t offset;
    unsigned source_line;
  };

  static const std::map<char, mode> mode_symbols = {
    {'#', IMMEDIATE},   {'$', DIRECT},
    {'*', A_INDIRECT},  {'@', B_INDIRECT},
    {'{', A_DECREMENT}, {'<', B_DECREMENT},
    {'}', A_INCREMENT}, {'>', B_INCREMENT}
  };

  typedef std::pair<mode, std::unique_ptr<number_expr>> field;

  static field make_empty_field() {
    auto expr = std::make_unique<number_number_expr>();
    expr->value = 0;
    return std::make_pair<>(DIRECT, std::move(expr));
  }

  static field to_field(std::string part) {
    if (part == "")
      return {};

    mode m = DIRECT;

    auto result = mode_symbols.find(part[0]);
    if (result != mode_symbols.end()) {
      m = result->second;
      part = trim_spaces(part.substr(1));
    }

    return std::make_pair<>(m, to_number_expr(part));
  }

  static modifier get_default_modifier(opcode op, mode amode, mode bmode) {
    switch (op) {

      case DAT:
        return F;

      case MOV:
      case SEQ:
      case SNE:
        if (amode == IMMEDIATE)
          return AB;
        if (bmode == IMMEDIATE)
          return B;
        return I;

      case ADD:
      case SUB:
      case MUL:
      case DIV:
      case MOD:
        if (amode == IMMEDIATE)
          return AB;
        if (bmode == IMMEDIATE)
          return B;
        return F;

      case SLT:
        if (amode == IMMEDIATE)
          return AB;
        return B;

      case JMP:
      case JMZ:
      case JMN:
      case DJN:
      case SPL:
      case NOP:
        return B;

    }

    assert(false);
  }

  static const std::map<std::string, opcode> opcode_names = {
    {"dat", DAT}, {"mov", MOV}, {"add", ADD}, {"sub", SUB},
    {"mul", MUL}, {"div", DIV}, {"mod", MOD}, {"jmp", JMP},
    {"jmz", JMZ}, {"jmn", JMN}, {"djn", DJN}, {"seq", SEQ},
    {"sne", SNE}, {"slt", SLT}, {"spl", SPL}, {"nop", NOP},
    {"cmp", SEQ}, {"jnz", JMN}
  };

  static void process_line(std::vector<future_instruction> &into, const preprocessed_line &line, future_inline_macro_set &future_inline_macros, label_set &labels, std::optional<org_info> &org) {
    assert(into.size() < LIB94_CORE_SIZE);

    if (line.the_line == "")
      return;

    size_t opcode_len = line.the_line.find_first_of(" .");
    if (opcode_len == std::string::npos)
      opcode_len = line.the_line.size();

    std::string opcode_name = line.the_line.substr(0, opcode_len);
    std::string rest = trim_spaces(line.the_line.substr(opcode_len));

    if (opcode_name == "org" || opcode_name == "end") {

      if (org.has_value()) {
        compiler_exception ex;
        ex.line_number = line.source_line;
        ex.message = "duplicate org";
        throw ex;
      }

      try {
        org = std::move((org_info){
          .expr = to_number_expr(rest),
          .offset = (number_t)into.size(),
          .source_line = line.source_line
        });
      }

      catch (const number_expr_exception &iex) {
        compiler_exception ex;
        ex.line_number = line.source_line;
        ex.message = iex.message;
        throw ex;
      }

      return;

    }

    auto opcode_result = opcode_names.find(opcode_name);

    if (opcode_result == opcode_names.end() && valid_identifier(opcode_name)) {

      if (rest.starts_with("equ ")) {

        try {
          future_inline_macros.push_back((future_inline_macro){
            .name = opcode_name,
            .source_line = line.source_line,
            .definition = to_number_expr(rest.substr(4)),
            .offset = (number_t)into.size()
          });
        }

        catch (const number_expr_exception &iex) {
          compiler_exception ex;
          ex.line_number = line.source_line;
          ex.message = iex.message;
          throw ex;
        }

        return;

      }

      if (labels.contains(opcode_name)) {
        compiler_exception ex;
        ex.line_number = line.source_line;
        ex.message = "duplicate label";
        throw ex;
      }

      labels[opcode_name] = into.size();
      preprocessed_line new_line = {.source_line = line.source_line, .the_line = rest};
      return process_line(into, new_line, future_inline_macros, labels, org);

    }

    opcode real_opcode = opcode_result->second;
    std::optional<modifier> real_modifier;

    if (rest != "" && rest[0] == '.') {

      if (rest.starts_with(".ab")) {
        real_modifier = AB;
        rest = trim_spaces(rest.substr(3));
      }

      if (rest.starts_with(".ba")) {
        real_modifier = BA;
        rest = trim_spaces(rest.substr(3));
      }

      if (rest.starts_with(".a")) {
        real_modifier = A;
        rest = trim_spaces(rest.substr(2));
      }

      if (rest.starts_with(".b")) {
        real_modifier = B;
        rest = trim_spaces(rest.substr(2));
      }

      if (rest.starts_with(".f")) {
        real_modifier = F;
        rest = trim_spaces(rest.substr(2));
      }

      if (rest.starts_with(".x")) {
        real_modifier = X;
        rest = trim_spaces(rest.substr(2));
      }

      if (rest.starts_with(".i")) {
        real_modifier = I;
        rest = trim_spaces(rest.substr(2));
      }

    }

    field a_field, b_field;

    try {

      if (rest == "") {
        a_field = make_empty_field();
        b_field = make_empty_field();
      }

      else {
        size_t comma = rest.find(',');

        if (comma == std::string::npos) {
          a_field = to_field(rest);
          b_field = make_empty_field();
        }

        else {
          a_field = to_field(rest.substr(0, comma));
          b_field = to_field(trim_spaces(rest.substr(comma + 1)));
        }
      }

    }

    catch (const number_expr_exception &iex) {
      compiler_exception ex;
      ex.line_number = line.source_line;
      ex.message = iex.message;
      throw ex;
    }

    if (!real_modifier.has_value())
      real_modifier = get_default_modifier(real_opcode, a_field.first, b_field.first);

    into.push_back((future_instruction){
      .source_line = line.source_line,
      .op = real_opcode,
      .mod = real_modifier.value(),
      .amode = a_field.first,
      .bmode = b_field.first,
      .anumber = std::move(a_field.second),
      .bnumber = std::move(b_field.second)
    });
  }

  warrior * compile_warrior(std::string source) {
    for (char &ch : source)
      if (ch == '\t' || ch == '\r')
        ch = ' ';

    info_from_preprocessor info;
    std::vector<preprocessed_line> lines;
    unsigned line_number = 1;
    preprocess_until_end_block(info, lines, line_number, source, {});

    if (!info.name.has_value() || info.name == "") {
      compiler_exception ex;
      ex.line_number = line_number;
      ex.message = "no warrior name";
      throw ex;
    }

    if (!info.author.has_value() || info.author == "") {
      compiler_exception ex;
      ex.line_number = line_number;
      ex.message = "no warrior author";
      throw ex;
    }

    std::vector<future_instruction> future_instructions;
    future_inline_macro_set future_inline_macros;
    label_set labels;
    std::optional<org_info> org;

    for (const preprocessed_line &line : lines)
      process_line(future_instructions, line, future_inline_macros, labels, org);

    inline_macro_set inline_macros;
    for (const auto &fim : future_inline_macros) {

      if (inline_macros.contains(fim.name)) {
        compiler_exception ex;
        ex.line_number = fim.source_line;
        ex.message = "duplicate inline macro";
        throw ex;
      }

      if (labels.contains(fim.name)) {
        compiler_exception ex;
        ex.line_number = fim.source_line;
        ex.message = "inline macro with same name as label";
        throw ex;
      }

      try {
        inline_macros[fim.name] = fim.definition->to_number(fim.offset, inline_macros, labels);
      }

      catch (const number_expr_exception &iex) {
        compiler_exception ex;
        ex.line_number = fim.source_line;
        ex.message = iex.message;
        throw ex;
      }

    }

    std::vector<instruction> actual_instructions;

    for (number_t offset = 0; offset < (number_t)future_instructions.size(); ++offset) {
      const future_instruction &fi = future_instructions[offset];

      try {
        actual_instructions.push_back((instruction){
          .op = fi.op,
          .mod = fi.mod,
          .amode = fi.amode,
          .bmode = fi.bmode,
          .anumber = fi.anumber->to_number(offset, inline_macros, labels),
          .bnumber = fi.bnumber->to_number(offset, inline_macros, labels)
        });
      }

      catch (const number_expr_exception &iex) {
        compiler_exception ex;
        ex.line_number = fi.source_line;
        ex.message = iex.message;
        throw ex;
      }
    }

    number_t org_result;

    if (!org.has_value())
      org_result = 0;

    else {
      try {
        org_result = real_mod(org.value().expr->to_number(org.value().offset, inline_macros, labels) + org.value().offset);
      }
      catch (const number_expr_exception &iex) {
        compiler_exception ex;
        ex.line_number = org.value().source_line;
        ex.message = iex.message;
        throw ex;
      }
    }

    return new warrior {
      .name = info.name.value(),
      .author = info.author.value(),
      .org = org_result,
      .instructions = actual_instructions
    };
  }

  struct wheader {
    size_t name_size;
    size_t author_size;
    size_t instructions_size;
    number_t org;
  };

  bool save_warrior(const warrior &w, const std::filesystem::path &to) {
    FILE *f = fopen(to.c_str(), "wb");
    if (!f)
      return false;

    wheader wh = {
      .name_size = w.name.size(), .author_size = w.author.size(),
      .instructions_size = w.instructions.size(), .org = w.org
    };

    fwrite(&wh, sizeof(wheader), 1, f);
    fwrite(w.name.c_str(), w.name.size(), 1, f);
    fwrite(w.author.c_str(), w.author.size(), 1, f);
    fwrite(w.instructions.data(), sizeof(instruction) * w.instructions.size(), 1, f);

    fclose(f);
    return true;
  }

  std::optional<warrior *> load_warrior(const std::filesystem::path &from) {
    FILE *f = fopen(from.c_str(), "rb");
    if (!f)
      return {};

    std::unique_ptr<warrior> w = std::make_unique<warrior>();

    wheader wh;
    fread(&wh, sizeof(wheader), 1, f);

    w->name.resize(wh.name_size);
    w->author.resize(wh.author_size);
    w->instructions.resize(wh.instructions_size);
    w->org = wh.org;

    fread(w->name.data(), wh.name_size, 1, f);
    fread(w->author.data(), wh.author_size, 1, f);
    fread(w->instructions.data(), wh.instructions_size, 1, f);

    fclose(f);

    for (const instruction &i : w->instructions)
      if (i.op > NOP || i.mod > I || i.amode > B_INCREMENT || i.bmode > B_INCREMENT ||
          i.anumber >= LIB94_CORE_SIZE || i.bnumber >= LIB94_CORE_SIZE)
        return {};

    return w.release();
  }

}