path: root/lib94/warrior.cpp

#include <lib94/lib94.hpp>
#include <functional>
#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);
  }

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

  struct number_expr {
    virtual std::optional<number_t> to_number(const std::map<std::string, number_t> &label_offsets, const std::map<std::string, number_t> &macro_values, number_t this_offset) = 0;
  };

  struct label_number_expr : public number_expr {
    std::string label;

    virtual std::optional<number_t> to_number(const std::map<std::string, number_t> &label_offsets, const std::map<std::string, number_t> &macro_values, number_t this_offset) {
      auto result = label_offsets.find(label);
      if (result != label_offsets.end())
        return real_mod(result->second - this_offset);
      result = macro_values.find(label);
      if (result != macro_values.end())
        return result->second;
      return {};
    }
  };

  struct number_number_expr : public number_expr {
    number_t value;

    virtual std::optional<number_t> to_number(const std::map<std::string, number_t> &, const std::map<std::string, number_t> &, number_t) {
      return real_mod(value);
    }
  };

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

    virtual std::optional<number_t> to_number(const std::map<std::string, number_t> &label_offsets, const std::map<std::string, number_t> &macro_values, number_t this_offset) {
      std::optional<number_t> left_result = left->to_number(label_offsets, macro_values, this_offset);
      std::optional<number_t> right_result = right->to_number(label_offsets, macro_values, this_offset);
      if (left_result.has_value() && right_result.has_value()) {
        std::optional<number_t> op_result = op(left_result.value(), right_result.value());
        if (op_result.has_value())
          return real_mod(op_result.value());
      }
      return {};
    }
  };

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

    virtual std::optional<number_t> to_number(const std::map<std::string, number_t> &label_offsets, const std::map<std::string, number_t> &macro_values, number_t this_offset) {
      std::optional<number_t> inner_result = inner->to_number(label_offsets, macro_values, this_offset);
      if (inner_result.has_value())
        return LIB94_CORE_SIZE - inner_result.value();
      return {};
    }
  };

  bool valid_label(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;
  }

  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;
  }

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

  std::optional<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);

    std::optional<std::unique_ptr<number_expr>> left_expr = to_number_expr(left);
    std::optional<std::unique_ptr<number_expr>> right_expr = to_number_expr(right);
    if (!left_expr.has_value() || !right_expr.has_value())
      return {};

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

    switch (part[split]) {
      case '+': expr->op = [](number_t a, number_t b) {return a + b;}; break;
      case '-': expr->op = [](number_t a, number_t b) {return a - b;}; break;
      case '*': expr->op = [](number_t a, number_t b) {return a * b;}; break;
      case '/': expr->op = [](number_t a, number_t b) -> std::optional<number_t> {
        if (b == 0)
          return {};
        return a / b;
        }; break;
      case '%': expr->op = [](number_t a, number_t b) -> std::optional<number_t> {
        if (b == 0)
          return {};
        return a % b;
        }; break;
    }

    return expr;
  }

  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);
  }

  std::optional<std::unique_ptr<number_expr>> to_number_expr(std::string part) {
    part = trim_spaces(part);
    if (part == "")
      return {};

    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::optional<std::unique_ptr<number_expr>> inner = to_number_expr(part.substr(1));
      if (!inner.has_value())
        return {};
      std::unique_ptr<negative_number_expr> expr = std::make_unique<negative_number_expr>();
      expr->inner = std::move(inner.value());
      return expr;
    }

    try {
      size_t count;
      number_t number = std::stoul(part, &count);
      if (count == part.size()) {
        std::unique_ptr<number_number_expr> expr = std::make_unique<number_number_expr>();
        expr->value = number;
        return expr;
      }
    }
    catch (const std::exception &e) {}

    if (valid_label(part)) {
      std::unique_ptr<label_number_expr> expr = std::make_unique<label_number_expr>();
      expr->label = part;
      return expr;
    }

    return {};
  }

  //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;

    std::optional<bool> is_true(const std::map<std::string, number_t> &label_offsets, const std::map<std::string, number_t> &macro_values, number_t this_offset) {
      auto left_result = left->to_number(label_offsets, macro_values, this_offset);
      auto right_result = right->to_number(label_offsets, macro_values, this_offset);
      if (left_result.has_value() && right_result.has_value())
        return comparison(left_result.value(), right_result.value());
      return {};
    }
  };

  std::optional<std::unique_ptr<assert_expr>> 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 {};

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

    if (!left.has_value() || !right.has_value())
      return {};

    return std::make_unique<assert_expr>((assert_expr){
      .left = std::move(left.value()), .right = std::move(right.value()), .comparison = comparison
    });
  }

  std::optional<std::unique_ptr<assert_expr>> to_assert_expr(std::string part) {
    std::optional<std::unique_ptr<assert_expr>> result;

    result = make_assert_expr(part, "==", [](number_t a, number_t b) {return a == b;});
    if (result)
      return result;

    result = make_assert_expr(part, "<=", [](number_t a, number_t b) {return a <= b;});
    if (result)
      return result;

    result = make_assert_expr(part, ">=", [](number_t a, number_t b) {return a >= b;});
    if (result)
      return result;

    result = make_assert_expr(part, "!=", [](number_t a, number_t b) {return a != b;});
    if (result)
      return result;

    result = make_assert_expr(part, "<", [](number_t a, number_t b) {return a < b;});
    if (result)
      return result;

    return make_assert_expr(part, ">", [](number_t a, number_t b) {return a > b;});
  }

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

  std::optional<std::pair<mode, std::unique_ptr<number_expr>>> 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));
    }

    std::optional<std::unique_ptr<number_expr>> expr = to_number_expr(part);
    if (expr.has_value())
      return std::make_pair<>(m, std::move(expr.value()));

    return {};
  }

  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}
  };

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

  struct macro_definition {
    size_t source_line;
    std::unique_ptr<number_expr> definition;
    number_t offset;
  };

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

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

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

    std::vector<future_instruction> instructions;
    std::map<std::string, number_t> label_offsets;
    std::map<std::string, macro_definition> macro_definitions;
    std::vector<assertion> assertions;
    std::optional<std::unique_ptr<number_expr>> org = {};
    number_t org_offset = -1;
    size_t org_source_line = -1;

    size_t on_line = 0;

    while (true) {
      if (source == "")
        break;

      ++on_line;

      size_t newline = source.find('\n');
      if (newline == std::string::npos)
        newline = source.size();

      std::string line = source.substr(0, newline);
      source = source.substr(newline + 1);

      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("name "))
          w->name = trim_spaces(comment.substr(5));
        else if (comment.starts_with("author "))
          w->author = trim_spaces(comment.substr(7));

        else if (comment.starts_with("assert ")) {
          auto expr = to_assert_expr(comment.substr(7));
          if (expr.has_value())
            assertions.emplace_back((assertion){
              .source_line = on_line,
              .expr = std::move(expr.value()),
              .offset = (number_t)instructions.size()
            });
          else
            return std::string("bad expression on line ") + std::to_string(on_line);
        }
      }

      for (char &ch : line)
        ch = tolower(ch);

      while (true) {
        size_t colon = line.find(':');
        if (colon == std::string::npos)
          break;

        std::string label = trim_spaces(line.substr(0, colon));
        line = line.substr(colon + 1);

        if (!valid_label(label))
          return std::string("bad label on line ") + std::to_string(on_line);
        if (label_offsets.contains(label) || macro_definitions.contains(label))
          return std::string("duplicate label on line ") + std::to_string(on_line);

        label_offsets[label] = instructions.size();
      }

      line = trim_spaces(line);
      if (line == "")
        continue;

      size_t equ = line.find(" equ ");
      if (equ != std::string::npos) {

        std::string macro_name = trim_spaces(line.substr(0, equ).substr());

        if (!valid_label(macro_name))
          return std::string("bad label on line ") + std::to_string(on_line);
        if (macro_definitions.contains(macro_name) || label_offsets.contains(macro_name))
          return std::string("duplicate label on line ") + std::to_string(on_line);

        auto macro_def = to_number_expr(line.substr(equ + 5));
        if (!macro_def.has_value())
          return std::string("bad expression on line ") + std::to_string(on_line);

        macro_definitions.emplace(macro_name,
          (macro_definition){
            .source_line = on_line,
            .definition = std::move(macro_def.value()),
            .offset = (number_t)instructions.size()
          }
        );

        continue;

      }

      future_instruction instr;
      instr.source_line = on_line;

      std::string opcode_str = line.substr(0, 3);
      line = trim_spaces(line.substr(3));

      if (opcode_str == "org" || opcode_str == "end") {
        if (org.has_value())
          return std::string("duplicate org on line ") + std::to_string(on_line);

        org = to_number_expr(line);

        if (!org.has_value())
          return std::string("bad expression on line ") + std::to_string(on_line);

        org_offset = instructions.size();
        org_source_line = on_line;
        continue;
      }

      auto opcode_it = opcode_names.find(opcode_str);

      if (opcode_it == opcode_names.end())
        return std::string("unknown opcode on line ") + std::to_string(on_line);

      instr.op = opcode_it->second;

      bool got_mod = false;

      if (line != "" && line[0] == '.') {
        line = trim_spaces(line.substr(1));

        if (line == "")
          return std::string("dot with no modifier on line ") + std::to_string(on_line);

        got_mod = true;

        size_t mod_length = 2;

        if (line.starts_with("ab"))
          instr.mod = AB;
        else if (line.starts_with("ba"))
          instr.mod = BA;
        else {

          mod_length = 1;

          if (line[0] == 'a')
            instr.mod = A;
          else if (line[0] == 'b')
            instr.mod = B;
          else if (line[0] == 'f')
            instr.mod = F;
          else if (line[0] == 'x')
            instr.mod = X;
          else if (line[0] == 'i')
            instr.mod = I;

          else
            return std::string("unknown opcode modifier on line ") + std::to_string(on_line);

        }

        line = trim_spaces(line.substr(mod_length));
      }

      std::optional<std::pair<mode, std::unique_ptr<number_expr>>> afield, bfield;

      if (line == "") {
        afield = to_field("0");
        bfield = to_field("0");
      }

      else {
        size_t comma = line.find(",");

        if (comma == std::string::npos) {
          afield = to_field(line);
          bfield = to_field("0");
        }

        else {
          std::string apart = trim_spaces(line.substr(0, comma));
          std::string bpart = trim_spaces(line.substr(comma + 1));
          afield = to_field(apart);
          bfield = to_field(bpart);
        }
      }

      if (!afield.has_value() || !bfield.has_value())
        return std::string("bad expression on line ") + std::to_string(on_line);

      instr.amode = afield.value().first;
      instr.bmode = bfield.value().first;
      instr.anumber = std::move(afield.value().second);
      instr.bnumber = std::move(bfield.value().second);

      if (!got_mod)
        switch (instr.op) {

          case DAT:
            instr.mod = F;
            break;

          case MOV:
          case SEQ:
          case SNE:
            if (instr.amode == IMMEDIATE)
              instr.mod = AB;
            else if (instr.bmode == IMMEDIATE)
              instr.mod = B;
            else
              instr.mod = I;
            break;

          case ADD:
          case SUB:
          case MUL:
          case DIV:
          case MOD:
            if (instr.amode == IMMEDIATE)
              instr.mod = AB;
            else if (instr.bmode == IMMEDIATE)
              instr.mod = B;
            else
              instr.mod = F;
            break;

          case SLT:
            if (instr.amode == IMMEDIATE)
              instr.mod = AB;
            instr.mod = B;
            break;

          case JMP:
          case JMZ:
          case JMN:
          case DJN:
          case SPL:
          case NOP:
            instr.mod = B;
            break;

        }

      instructions.push_back(std::move(instr));
    }

    if (w->name == "")
      return "no name";
    if (w->author == "")
      return "no author";

    std::map<std::string, number_t> macro_values;
    for (const auto &macro : macro_definitions) {
      auto result = macro.second.definition->to_number(label_offsets, macro_values, macro.second.offset);
      if (result.has_value())
        macro_values[macro.first] = result.value();
      else
        return std::string("bad expression on line ") + std::to_string(macro.second.source_line);
    }

    for (const auto &a : assertions) {
      auto result = a.expr->is_true(label_offsets, macro_values, a.offset);
      if (!result.has_value())
        return std::string("bad expression on line ") + std::to_string(a.source_line);
      if (!result.value())
        return std::string("failed assertion on line ") + std::to_string(a.source_line);
    }

    if (org.has_value()) {
      std::optional<number_t> org_number = org.value()->to_number(label_offsets, macro_values, org_offset);
      if (org_number.has_value())
        w->org = real_mod(org_number.value() + org_offset);
      else
        return std::string("bad expression on line ") + std::to_string(org_source_line);
    }

    for (size_t i = 0; i < instructions.size(); ++i) {
      const future_instruction &instr = instructions[i];
      std::optional<number_t> anumber = instr.anumber->to_number(label_offsets, macro_values, i);
      std::optional<number_t> bnumber = instr.bnumber->to_number(label_offsets, macro_values, i);
      if (!anumber.has_value() || !bnumber.has_value())
        return std::string("bad expression on line ") + std::to_string(instr.source_line);
      w->instructions.push_back({
        .op = instr.op, .mod = instr.mod, .amode = instr.amode, .bmode = instr.bmode,
        .anumber = anumber.value(), .bnumber = bnumber.value()
      });
    }

    return w.release();
  }

  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();
  }

}