Compiler Explorer

Source code

#include <array>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <iostream>
#include <memory>
#include <new>
#include <optional>
#include <sstream>
#include <string>
#include <string_view>
#include <vector>

namespace Flags {
constexpr auto bench = false;

constexpr auto logs = false;
constexpr auto compilerLogs = logs && !bench;
constexpr auto vmLogs = logs && !bench;

constexpr auto typeErrors = true;
};

//
// Value
//

struct Value {
  struct Nil {};

struct String {
    const std::string str;
    const uint32_t hash = computeHash(str);

explicit String(std::string_view str_)
        : str(str_) {
    }

friend auto operator==(const String &a, const String &b) -> bool {
      return a.str == b.str;
    }

static auto computeHash(std::string_view key) -> uint32_t {
      uint32_t hash = 2166136261u;
      for (char c : key) {
        hash ^= c;
        hash *= 16777619;
      }
      return hash;
    }
  };

template<typename T>
  [[nodiscard]] auto is() const -> bool;
  template<typename T>
  [[nodiscard]] auto as() const -> T;

explicit Value(double d)
      : data(pun<uint64_t>(d)) {
  }
  template<>
  [[nodiscard]] auto is<double>() const -> bool {
    return (data & qNan) != qNan;
  }
  template<>
  [[nodiscard]] auto as<double>() const -> double {
    return pun<double>(data);
  }

explicit Value(Nil)
      : data(nilData) {
  }
  template<>
  [[nodiscard]] auto is<Nil>() const -> bool {
    return data == nilData;
  }

explicit Value(bool b)
      : data(b ? trueData : falseData) {
  }
  template<>
  [[nodiscard]] auto is<bool>() const -> bool {
    return data == trueData || data == falseData;
  }
  template<>
  [[nodiscard]] auto as<bool>() const -> bool {
    return data == trueData;
  }

explicit Value(String *s)
      : data(signBit | qNan | uint64_t(uintptr_t(s))) {
  }
  template<>
  [[nodiscard]] auto is<String *>() const -> bool {
    return (data & (qNan | signBit)) == (qNan | signBit);
  }
  template<>
  [[nodiscard]] auto as<String *>() const -> String * {
    return (String *)(uintptr_t(data & ~(signBit | qNan)));
  }

[[nodiscard]] auto isFalsey() const -> bool {
    return is<Nil>() || (is<bool>() && !as<bool>());
  }

friend auto operator==(const Value &a, const Value &b) -> bool {
    return a.data == b.data;
  }

friend auto operator!=(const Value &a, const Value &b) -> bool {
    return !(a == b);
  }

auto print() const -> void {
    if (is<Nil>()) {
    } else if (is<bool>()) {
      std::printf(as<bool>() ? "true" : "false");
    } else if (is<double>()) {
      std::printf("%g", as<double>());
    } else if (is<String *>()) {
      std::printf("%s", as<String *>()->str.c_str());
    }
  }

private:
  uint64_t data;

static constexpr uint64_t signBit = 0x8000000000000000;
  static constexpr uint64_t qNan = 0x7ffc000000000000;

static constexpr uint64_t nilData = qNan | 1;
  static constexpr uint64_t falseData = qNan | 2;
  static constexpr uint64_t trueData = qNan | 3;

template<class To, class From>
  static auto pun(From f) noexcept -> To {
    To t;
    std::memcpy(&t, &f, sizeof(t));
    return t;
  }
};

static_assert(std::is_trivially_destructible_v<Value>);

//
// Table
//

template<typename Key>
struct Table {
  static_assert(
      std::is_same_v<Key, Value::String *> || std::is_same_v<Key, std::unique_ptr<Value::String>>);

auto get(const Value::String *key) -> Value * {
    if (count > 0) {
      if (auto &entry = select(entries.get(), capacity, key); entry.key) {
        return &entry.value;
      }
    }
    return nullptr;
  }

auto set(Key key, Value value) -> bool {
    if (count + 1 > maxLoad * capacity) {
      resize(capacity < 8 ? 8 : 2 * capacity);
    }

auto &entry = select(entries.get(), capacity, ptr(key));
    auto isNew = !entry.key;
    if (isNew && entry.value.template is<Value::Nil>()) {
      ++count;
    }
    entry.key = std::move(key);
    entry.value = value;
    return isNew;
  }

auto remove(const Value::String *key) -> bool {
    if (count > 0) {
      if (auto &entry = select(entries.get(), capacity, key); entry.key) {
        entry.key = nullptr;
        entry.value = Value(true); // Tombstone
        return true;
      }
    }
    return false;
  }

auto intern(std::string_view str) -> Value::String * {
    static_assert(std::is_same_v<Key, std::unique_ptr<Value::String>>,
        "only owning tables can intern strings");
    if (auto found = select(str)) {
      return found;
    } else {
      auto holder = std::make_unique<Value::String>(str);
      auto result = ptr(holder);
      set(std::move(holder), Value(Value::Nil()));
      return result;
    }
  }

private:
  static constexpr auto maxLoad = 0.75;

int count = 0;
  int capacity = 0;

struct Entry {
    Key key = nullptr;
    Value value { Value::Nil() };
  };
  std::unique_ptr<Entry[]> entries = nullptr;

static auto ptr(std::unique_ptr<Value::String> &key) -> Value::String * {
    return key.get();
  }

static auto ptr(Value::String *p) -> Value::String * {
    return p;
  }

static auto select(Entry *entries, int capacity, const Value::String *key) -> Entry & {
    uint32_t index = key->hash % capacity;
    Entry *tombstone = nullptr;
    for (;;) {
      if (auto &entry = entries[index]; !entry.key) {
        if (entry.value.template is<Value::Nil>()) {
          return tombstone ? *tombstone : entry;
        } else if (!tombstone) {
          tombstone = &entry;
        }
      } else if (ptr(entry.key) == key) {
        return entry;
      }
      index = (index + 1) % capacity;
    }
  }

auto select(std::string_view str) -> Value::String * {
    if (count == 0) {
      return nullptr;
    }
    auto hash = Value::String::computeHash(str);
    uint32_t index = hash % capacity;
    for (;;) {
      if (auto &entry = entries[index]; !entry.key) {
        if (entry.value.template is<Value::Nil>()) {
          return nullptr;
        }
      } else if (entry.key->hash == hash && entry.key->str == str) {
        return ptr(entry.key);
      }
      index = (index + 1) % capacity;
    }
  }

auto resize(int newCapacity) -> void {
    auto newEntries = std::make_unique<Entry[]>(newCapacity);
    auto newCount = 0;
    for (auto i = 0; i < capacity; ++i) {
      if (auto &src = entries[i]; src.key) {
        auto &dest = select(newEntries.get(), newCapacity, ptr(src.key));
        dest = std::move(src);
        ++newCount;
      }
    }
    entries = std::move(newEntries);
    count = newCount;
    capacity = newCapacity;
  }
};

using OwnTable = Table<std::unique_ptr<Value::String>>; // Owns keys
using RefTable = Table<Value::String *>; // References keys

//
// Chunk
//

// clang-format off
#define OP_NAMES(prefix)                 \
  prefix##Constant,                      \
  prefix##Zero,                          \
  prefix##One,                           \
  prefix##NegativeOne,                   \
  prefix##Nil,                           \
  prefix##True,                          \
  prefix##False,                         \
  prefix##Pop,                           \
  prefix##GetLocal,                      \
  prefix##GetLocal0,                     \
  prefix##GetLocal1,                     \
  prefix##GetLocal2,                     \
  prefix##GetLocal3,                     \
  prefix##GetLocal4,                     \
  prefix##GetLocal5,                     \
  prefix##SetLocal,                      \
  prefix##SetLocal0,                     \
  prefix##SetLocal1,                     \
  prefix##SetLocal2,                     \
  prefix##SetLocal3,                     \
  prefix##SetLocal4,                     \
  prefix##SetLocal5,                     \
  prefix##DefineGlobal,                  \
  prefix##GetGlobal,                     \
  prefix##SetGlobal,                     \
  prefix##Equal,                         \
  prefix##Greater,                       \
  prefix##Less,                          \
  prefix##Add,                           \
  prefix##Subtract,                      \
  prefix##Multiply,                      \
  prefix##Divide,                        \
  prefix##Not,                           \
  prefix##Negate,                        \
  prefix##Print,                         \
  prefix##Jump,                          \
  prefix##JumpIfFalse,                   \
  prefix##Loop,                          \
  prefix##Return,                        \
// clang-format on

enum class Op : uint8_t { OP_NAMES() };

struct Chunk {
  auto write(uint8_t byte, int line) -> void {
    code.push_back(byte);
    lines.push_back(line);
  }

auto write(Op op, int line) -> void {
    write(uint8_t(op), line);
  }

auto set(int offset, uint8_t byte) -> void {
    code[offset] = byte;
  }

template<typename... Args>
  auto addConstant(Args &&... args) -> int {
    constants.emplace_back(std::forward<Args>(args)...);
    return int(constants.size() - 1);
  }

[[nodiscard]] auto size() const -> size_t {
    return code.size();
  }

[[nodiscard]] auto start() const -> const uint8_t * {
    return code.data();
  }

[[nodiscard]] auto read(size_t offset) const -> uint8_t {
    return code[offset];
  }

[[nodiscard]] auto line(size_t offset) const -> int {
    return lines[offset];
  }

[[nodiscard]] auto constant(size_t id) const -> const Value & {
    return constants[id];
  }

private:
  std::vector<uint8_t> code;
  std::vector<int> lines;
  std::vector<Value> constants;
};

//
// Disassembly
//

struct Disassembly {
  explicit Disassembly(const Chunk &chunk_)
      : chunk(chunk_) {
  }

auto instruction(int offset) -> int {
    std::printf("%04d ", offset);

if (offset > 0 && chunk.line(offset) == chunk.line(offset - 1)) {
      std::printf("   | ");
    } else {
      std::printf("%4d ", chunk.line(offset));
    }

switch (auto opCode = Op(chunk.read(offset))) {
    case Op::Constant:
      return constant("OP_CONSTANT", offset);
    case Op::Zero:
      return simple("OP_ZERO", offset);
    case Op::One:
      return simple("OP_ONE", offset);
    case Op::NegativeOne:
      return simple("OP_NEGATIVE_ONE", offset);
    case Op::Nil:
      return simple("OP_NIL", offset);
    case Op::True:
      return simple("OP_TRUE", offset);
    case Op::False:
      return simple("OP_FALSE", offset);
    case Op::Pop:
      return simple("OP_POP", offset);
    case Op::GetLocal:
      return byte("OP_GET_LOCAL", offset);
    case Op::GetLocal0:
      return simple("OP_GET_LOCAL_0", offset);
    case Op::GetLocal1:
      return simple("OP_GET_LOCAL_1", offset);
    case Op::GetLocal2:
      return simple("OP_GET_LOCAL_2", offset);
    case Op::GetLocal3:
      return simple("OP_GET_LOCAL_3", offset);
    case Op::GetLocal4:
      return simple("OP_GET_LOCAL_4", offset);
    case Op::GetLocal5:
      return simple("OP_GET_LOCAL_5", offset);
    case Op::SetLocal:
      return byte("OP_SET_LOCAL", offset);
    case Op::SetLocal0:
      return simple("OP_SET_LOCAL_0", offset);
    case Op::SetLocal1:
      return simple("OP_SET_LOCAL_1", offset);
    case Op::SetLocal2:
      return simple("OP_SET_LOCAL_2", offset);
    case Op::SetLocal3:
      return simple("OP_SET_LOCAL_3", offset);
    case Op::SetLocal4:
      return simple("OP_SET_LOCAL_4", offset);
    case Op::SetLocal5:
      return simple("OP_SET_LOCAL_5", offset);
    case Op::DefineGlobal:
      return constant("OP_DEFINE_GLOBAL", offset);
    case Op::GetGlobal:
      return constant("OP_GET_GLOBAL", offset);
    case Op::SetGlobal:
      return constant("OP_SET_GLOBAL", offset);
    case Op::Equal:
      return simple("OP_EQUAL", offset);
    case Op::Greater:
      return simple("OP_GREATER", offset);
    case Op::Less:
      return simple("OP_LESS", offset);
    case Op::Add:
      return simple("OP_ADD", offset);
    case Op::Subtract:
      return simple("OP_SUBTRACT", offset);
    case Op::Multiply:
      return simple("OP_MULTIPLY", offset);
    case Op::Divide:
      return simple("OP_DIVIDE", offset);
    case Op::Not:
      return simple("OP_NOT", offset);
    case Op::Negate:
      return simple("OP_NEGATE", offset);
    case Op::Print:
      return simple("OP_PRINT", offset);
    case Op::Jump:
      return jump("OP_JUMP", 1, offset);
    case Op::JumpIfFalse:
      return jump("OP_JUMP_IF_FALSE", 1, offset);
    case Op::Loop:
      return jump("OP_LOOP", -1, offset);
    case Op::Return:
      return simple("OP_RETURN", offset);
    default:
      std::printf("Unknown opcode %hhu\n", opCode);
      return offset + 1;
    }
  }

auto all(std::string_view name) {
    std::printf("== %.*s ==\n", int(name.size()), name.data());

for (auto offset = 0; offset < chunk.size();) {
      offset = instruction(offset);
    }
  }

private:
  const Chunk &chunk;

auto simple(std::string_view name, int offset) -> int {
    std::printf("%.*s\n", int(name.size()), name.data());
    return offset + 1;
  }

auto constant(std::string_view name, int offset) -> int {
    auto id = chunk.read(offset + 1);
    std::printf("%-16.*s %4d '", int(name.size()), name.data(), id);
    chunk.constant(id).print();
    std::printf("'\n");
    return offset + 2;
  }

auto byte(std::string_view name, int offset) -> int {
    auto id = chunk.read(offset + 1);
    std::printf("%-16.*s %4d\n", int(name.size()), name.data(), id);
    return offset + 2;
  }

auto jump(std::string_view name, int sign, int offset) -> int {
    uint16_t jump = chunk.read(offset + 1) << 8;
    jump |= chunk.read(offset + 2);
    printf("%-16.*s %4d -> %d\n", int(name.size()), name.data(), offset, offset + 3 + sign * jump);
    return offset + 3;
  }
};

//
// Scanner
//

struct Token {
  enum class Type {
    // clang-format off
    LeftParen, RightParen,
    LeftBrace, RightBrace,
    Comma, Dot, Minus, Plus,
    Semicolon, Slash, Star,

Bang, BangEqual,
    Equal, EqualEqual,
    Greater, GreaterEqual,
    Less, LessEqual,

Identifier, String, Number,

And, Class, Else, False,
    For, Fun, If, Nil, Or,
    Print, Return, Super, This,
    True, Var, While,

Error, Eof,
    // clang-format on
  };

Type type = Type::Eof;
  std::string_view str;
  int line = 1;
};

struct Scanner {
  explicit Scanner(std::string_view source_)
      : source(source_) {
  }

auto next() -> Token {
    skip();

start = current;

if (end()) {
      return make(Token::Type::Eof);
    }

auto c = advance();

if (alpha(c)) {
      return identifier();
    }

if (digit(c)) {
      return number();
    }

switch (c) {
    case '(':
      return make(Token::Type::LeftParen);
    case ')':
      return make(Token::Type::RightParen);
    case '{':
      return make(Token::Type::LeftBrace);
    case '}':
      return make(Token::Type::RightBrace);
    case ';':
      return make(Token::Type::Semicolon);
    case ',':
      return make(Token::Type::Comma);
    case '.':
      return make(Token::Type::Dot);
    case '-':
      return make(Token::Type::Minus);
    case '+':
      return make(Token::Type::Plus);
    case '/':
      return make(Token::Type::Slash);
    case '*':
      return make(Token::Type::Star);

case '!':
      return make(match('=') ? Token::Type::BangEqual : Token::Type::Bang);
    case '=':
      return make(match('=') ? Token::Type::EqualEqual : Token::Type::Equal);
    case '<':
      return make(match('=') ? Token::Type::LessEqual : Token::Type::Less);
    case '>':
      return make(match('=') ? Token::Type::GreaterEqual : Token::Type::Greater);

case '"':
      return string();
    }

return error("Unexpected character.");
  }

private:
  std::string_view source;
  const char *start = source.data();
  const char *current = source.data();
  int line = 1;

[[nodiscard]] auto end() const -> bool {
    return current == source.end();
  }

[[nodiscard]] auto make(Token::Type type) const -> Token {
    return { type, { start, size_t(current - start) }, line };
  }

[[nodiscard]] auto error(std::string_view message) const -> Token {
    return { Token::Type::Error, message, line };
  }

auto advance() -> char {
    return *current++;
  }

auto match(char expected) -> bool {
    if (end() || *current != expected) {
      return false;
    } else {
      ++current;
      return true;
    }
  }

auto skip() -> void {
    for (;;) {
      if (end()) {
        break;
      }
      switch (auto c = peek()) {
      case ' ':
      case '\r':
      case '\t':
        advance();
        break;

case '\n':
        ++line;
        advance();
        break;

case '/':
        if (peekNext() == '/') {
          while (!end() && peek() != '\n') {
            advance();
          }
        } else {
          return;
        }
        break;

default:
        return;
      }
    }
  }

auto string() -> Token {
    while (!end() && peek() != '"') {
      if (peek() == '\n') {
        ++line;
      }
      advance();
    }
    if (end()) {
      return error("Unterminated string.");
    }
    advance(); // Closing quote
    return make(Token::Type::String);
  }

auto number() -> Token {
    while (!end() && digit(peek())) {
      advance();
    }
    if (!end() && peek() == '.' && digit(peekNext())) { // Fractional
      advance(); // Dot
      while (!end() && digit(peek())) {
        advance();
      }
    }
    return make(Token::Type::Number);
  }

auto identifier() -> Token {
    while (!end() && (alpha(peek()) || digit(peek()))) {
      advance();
    }

const auto check = [&](int offset, std::string_view rest, Token::Type type) -> Token::Type {
      if (current - start == offset + rest.size()
          && std::memcmp(start + offset, rest.data(), rest.size()) == 0) {
        return type;
      }
      return Token::Type::Identifier;
    };

const auto type = [&]() -> Token::Type {
      switch (start[0]) {
      case 'a':
        return check(1, "nd", Token::Type::And);
      case 'c':
        return check(1, "lass", Token::Type::Class);
      case 'e':
        return check(1, "lse", Token::Type::Else);
      case 'i':
        return check(1, "f", Token::Type::If);
      case 'n':
        return check(1, "il", Token::Type::Nil);
      case 'o':
        return check(1, "r", Token::Type::Or);
      case 'p':
        return check(1, "rint", Token::Type::Print);
      case 'r':
        return check(1, "eturn", Token::Type::Return);
      case 's':
        return check(1, "uper", Token::Type::Super);
      case 'v':
        return check(1, "ar", Token::Type::Var);
      case 'w':
        return check(1, "hile", Token::Type::While);
      case 'f':
        if (current - start > 1) {
          switch (start[1]) {
          case 'a':
            return check(2, "lse", Token::Type::False);
          case 'o':
            return check(2, "r", Token::Type::For);
          case 'u':
            return check(2, "n", Token::Type::Fun);
          }
        }
        break;
      case 't':
        if (current - start > 1) {
          switch (start[1]) {
          case 'h':
            return check(2, "is", Token::Type::This);
          case 'r':
            return check(2, "ue", Token::Type::True);
          }
        }
        break;
      }
      return Token::Type::Identifier;
    };

return make(type());
  }

[[nodiscard]] auto peek() const -> char {
    return *current;
  }

[[nodiscard]] auto peekNext() const -> char {
    if (end() || current + 1 == source.end()) {
      return '\0';
    } else {
      return *(current + 1);
    }
  }

[[nodiscard]] static auto digit(char c) -> bool {
    return c >= '0' && c <= '9';
  }

[[nodiscard]] static auto alpha(char c) -> bool {
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || c == '_';
  }
};

//
// Compiler
//

struct Compiler {
  explicit Compiler(std::string_view source, OwnTable &strings_)
      : scan(source)
      , strings(strings_) {
  }

auto compile() -> std::optional<Chunk> {
    Function top;
    func = &top;

advance();

while (!match(Token::Type::Eof)) {
      declaration();
    }
    emit(Op::Return);

if (errored) {
      return std::nullopt;
    } else {
      if constexpr (Flags::compilerLogs) {
        Disassembly(root).all("code");
      }
      return std::move(root);
    }
  }

private:
  Scanner scan;

Token current;
  Token previous;

bool errored = false;
  bool panic = false;

Chunk root;

OwnTable &strings;

struct Function {
    struct Local {
      Token name;
      int depth = 0;
    };
    std::vector<Local> locals;
    int depth = 0;
  };
  Function *func = nullptr;

auto chunk() -> Chunk & {
    return root;
  }

auto error(Token &token, std::string_view message) -> void {
    if (panic) {
      return;
    }
    panic = true;

std::fprintf(stderr, "[line %d] Error", token.line);

if (token.type == Token::Type::Eof) {
      std::fprintf(stderr, " at end");
    } else if (token.type == Token::Type::Error) {
    } else {
      std::fprintf(stderr, " at '%.*s'", int(token.str.size()), token.str.data());
    }

std::fprintf(stderr, ": %.*s\n", int(message.size()), message.data());
    errored = true;
  }

auto synchronize() -> void {
    panic = false;
    while (current.type != Token::Type::Eof) {
      // Keep going till we end a statement or are about to start one
      if (previous.type == Token::Type::Semicolon) {
        return;
      }
      switch (current.type) {
      case Token::Type::Class:
      case Token::Type::Fun:
      case Token::Type::Var:
      case Token::Type::For:
      case Token::Type::If:
      case Token::Type::While:
      case Token::Type::Print:
      case Token::Type::Return:
        return;
      default:;
      }
      advance();
    }
  }

template<typename... Args>
  auto emit(Args &&... args) -> void {
    (chunk().write(args, previous.line), ...);
  }

template<typename... Args>
  auto emitConstant(Args &&... args) -> void {
    emit(Op::Constant, addConstant(std::forward<Args>(args)...));
  }

template<typename... Args>
  auto addConstant(Args &&... args) -> uint8_t {
    if (auto constant = chunk().addConstant(std::forward<Args>(args)...);
        constant > std::numeric_limits<uint8_t>::max()) {
      error(previous, "Too many constants.");
      return 0;
    } else {
      return uint8_t(constant);
    }
  }

auto identifierConstant(const Token &name) -> uint8_t {
    return addConstant(strings.intern(name.str));
  }

auto advance() -> void {
    previous = current;
    for (;;) {
      current = scan.next();
      if (current.type != Token::Type::Error) {
        break;
      }
    }
  }

auto consume(Token::Type type, std::string_view message) -> void {
    if (current.type == type) {
      advance();
    } else {
      error(current, message);
    }
  }

auto match(Token::Type type) -> bool {
    if (current.type == type) {
      advance();
      return true;
    } else {
      return false;
    }
  }

auto number(bool) -> void {
    auto value = std::strtod(previous.str.data(), nullptr);
    if (value == 0) {
      emit(Op::Zero);
    } else if (value == 1) {
      emit(Op::One);
    } else if (value == -1) {
      emit(Op::NegativeOne);
    } else {
      emitConstant(value);
    }
  }

auto grouping(bool) -> void {
    expression();
    consume(Token::Type::RightParen, "Expect ')' after expression.");
  }

auto unary(bool) -> void {
    auto type = previous.type;
    expression(Precedence::Unary);
    switch (type) {
    case Token::Type::Minus:
      emit(Op::Negate);
      break;

case Token::Type::Bang:
      emit(Op::Not);
      break;

default:
      break;
    }
  }

auto binary(bool) -> void {
    auto type = previous.type;
    expression(Precedence(int(getRule(type).precedence) + 1));
    switch (type) {
    case Token::Type::Plus:
      emit(Op::Add);
      break;
    case Token::Type::Minus:
      emit(Op::Subtract);
      break;
    case Token::Type::Star:
      emit(Op::Multiply);
      break;
    case Token::Type::Slash:
      emit(Op::Divide);
      break;

case Token::Type::EqualEqual:
      emit(Op::Equal);
      break;
    case Token::Type::BangEqual:
      emit(Op::Equal, Op::Not);
      break;
    case Token::Type::Greater:
      emit(Op::Greater);
      break;
    case Token::Type::GreaterEqual:
      emit(Op::Less, Op::Not);
      break;
    case Token::Type::Less:
      emit(Op::Less);
      break;
    case Token::Type::LessEqual:
      emit(Op::Greater, Op::Not);
      break;

default:
      break;
    }
  }

auto literal(bool) -> void {
    switch (previous.type) {
    case Token::Type::Nil:
      emit(Op::Nil);
      break;
    case Token::Type::True:
      emit(Op::True);
      break;
    case Token::Type::False:
      emit(Op::False);
    default:
      break;
    }
  }

auto string(bool) -> void {
    emitConstant(strings.intern(previous.str.substr(1, previous.str.size() - 2)));
  }

auto variable(bool assignable) -> void {
    variable(previous, assignable);
  }

auto variable(const Token &name, bool assignable) -> void {
    auto id = resolveLocal(*func, name);
    Op set = Op::SetLocal, get = Op::GetLocal;
    if (id == -1) { // Global
      id = identifierConstant(name);
      set = Op::SetGlobal;
      get = Op::GetGlobal;
    } else if (id <= 5) {
      set = Op(int(Op::SetLocal0) + id);
      get = Op(int(Op::GetLocal0) + id);
    }
    if (assignable && match(Token::Type::Equal)) {
      expression();
      emit(set);
      if (set == Op::SetLocal || set == Op::SetGlobal) {
        emit(id);
      }
    } else {
      emit(get);
      if (get == Op::GetLocal || get == Op::GetGlobal) {
        emit(id);
      }
    }
  }

auto and_(bool) -> void {
    // If a is false, return a, else return b
    int returnA = emitJump(Op::JumpIfFalse);
    emit(Op::Pop);
    expression(Precedence::And);
    setJump(returnA);
  }

auto or_(bool) -> void {
    // If a is false, return b, else return a
    int returnB = emitJump(Op::JumpIfFalse);
    int returnA = emitJump(Op::Jump);

setJump(returnB);
    emit(Op::Pop);
    expression(Precedence::Or);

setJump(returnA);
  }

enum class Precedence {
    None,
    Assignment, // =
    Or, //         or
    And, //        and
    Equality, //   == !=
    Comparison, // < > <= >=
    Term, //       + -
    Factor, //     * /
    Unary, //      ! -
    Call, //       . ()
    Primary,
  };

struct Rule {
    void (Compiler::*prefix)(bool assignable);
    void (Compiler::*infix)(bool assignable);
    Precedence precedence;
  };

inline static std::array<Rule, size_t(Token::Type::Eof) + 1> rules = []() {
    decltype(rules) result {};
    result.fill({ nullptr, nullptr, Precedence::None });

const auto set = [&](Token::Type type, const Rule &rule) {
      result[size_t(type)] = rule;
    };

set(Token::Type::LeftParen, { &Compiler::grouping, nullptr, Precedence::None });

set(Token::Type::Plus, { nullptr, &Compiler::binary, Precedence::Term });
    set(Token::Type::Minus, { &Compiler::unary, &Compiler::binary, Precedence::Term });
    set(Token::Type::Star, { nullptr, &Compiler::binary, Precedence::Factor });
    set(Token::Type::Slash, { nullptr, &Compiler::binary, Precedence::Factor });

set(Token::Type::Number, { &Compiler::number, nullptr, Precedence::None });

set(Token::Type::Nil, { &Compiler::literal, nullptr, Precedence::None });
    set(Token::Type::True, { &Compiler::literal, nullptr, Precedence::None });
    set(Token::Type::False, { &Compiler::literal, nullptr, Precedence::None });

set(Token::Type::Bang, { &Compiler::unary, nullptr, Precedence::None });

set(Token::Type::EqualEqual, { nullptr, &Compiler::binary, Precedence::Equality });
    set(Token::Type::BangEqual, { nullptr, &Compiler::binary, Precedence::Equality });
    set(Token::Type::Greater, { nullptr, &Compiler::binary, Precedence::Comparison });
    set(Token::Type::GreaterEqual, { nullptr, &Compiler::binary, Precedence::Comparison });
    set(Token::Type::Less, { nullptr, &Compiler::binary, Precedence::Comparison });
    set(Token::Type::LessEqual, { nullptr, &Compiler::binary, Precedence::Comparison });

set(Token::Type::String, { &Compiler::string, nullptr, Precedence::None });

set(Token::Type::Identifier, { &Compiler::variable, nullptr, Precedence::None });

set(Token::Type::And, { nullptr, &Compiler::and_, Precedence::And });
    set(Token::Type::Or, { nullptr, &Compiler::or_, Precedence::Or });

return result;
  }();

auto getRule(Token::Type type) -> Rule & {
    return rules[size_t(type)];
  }

auto expression(Precedence precedence = Precedence::Assignment) -> void {
    advance();
    if (auto prefix = getRule(previous.type).prefix) {
      auto assignable = precedence <= Precedence::Assignment;
      (this->*prefix)(assignable);
      while (precedence <= getRule(current.type).precedence) {
        advance();
        (this->*(getRule(previous.type).infix))(assignable);
      }
    } else {
      error(previous, "Expect expression.");
    }
  }

auto declaration() -> void {
    if (match(Token::Type::Var)) {
      varStatement();
    } else {
      statement();
    }
    if (panic) {
      synchronize();
    }
  }

auto statement() -> void {
    if (match(Token::Type::Print)) {
      printStatement();
    } else if (match(Token::Type::If)) {
      ifStatement();
    } else if (match(Token::Type::While)) {
      whileStatement();
    } else if (match(Token::Type::LeftBrace)) {
      beginScope();
      block();
      endScope();
    } else {
      expressionStatement();
    }
  }

auto printStatement() -> void {
    expression();
    consume(Token::Type::Semicolon, "Expect ';' after value.");
    emit(Op::Print);
  }

auto expressionStatement() -> void {
    expression();
    consume(Token::Type::Semicolon, "Expect ';' after expression.");
    emit(Op::Pop);
  }

auto varStatement() -> void {
    uint8_t id = consumeVariable("Expect variable name.");
    if (match(Token::Type::Equal)) {
      expression();
    } else {
      emit(Op::Nil);
    }
    consume(Token::Type::Semicolon, "Expect ';' after variable declaration.");
    defineVariable(id);
  }

auto consumeVariable(std::string_view message) -> uint8_t {
    consume(Token::Type::Identifier, message);
    declareVariable();
    if (func->depth == 0) { // Global
      return identifierConstant(previous);
    } else { // Local
      return 0;
    }
  }

auto declareVariable() -> void {
    if (func->depth != 0) { // Local
      if (func->locals.size() - 1 == std::numeric_limits<uint8_t>::max()) {
        error(previous, "Too many local variables in function.");
        return;
      }
      for (int i = int(func->locals.size()) - 1; i >= 0; --i) {
        auto &local = func->locals[i];
        if (local.depth != -1 && local.depth < func->depth) {
          break;
        }
        if (previous.str == local.name.str) {
          error(previous, "Variable with this name already declared in this scope.");
        }
      }
      func->locals.push_back({ previous, -1 });
    } // Globals are implicitly declared
  }

auto defineVariable(uint8_t id) -> void {
    if (func->depth == 0) { // Global
      emit(Op::DefineGlobal, id);
    } else { // Locl
      initializeLocal();
    }
  }

auto resolveLocal(Function &func, const Token &name) -> int {
    for (int i = int(func.locals.size()) - 1; i >= 0; --i) {
      auto &local = func.locals[i];
      if (local.name.str == name.str) {
        if (local.depth == -1) {
          error(previous, "Cannot read variable in its own initializer.");
        }
        return i;
      }
    }
    return -1;
  }

auto initializeLocal() -> void {
    func->locals.back().depth = func->depth;
  }

auto block() -> void {
    while (current.type != Token::Type::RightBrace && current.type != Token::Type::Eof) {
      declaration();
    }
    consume(Token::Type::RightBrace, "Expect '}' after block.");
  }

auto beginScope() -> void {
    ++func->depth;
  }

auto endScope() -> void {
    --func->depth;
    while (func->locals.size() > 0 && func->locals.back().depth > func->depth) {
      emit(Op::Pop);
      func->locals.pop_back();
    }
  }

auto ifStatement() -> void {
    consume(Token::Type::LeftParen, "Expect '(' after 'if'.");
    expression();
    consume(Token::Type::RightParen, "Expect ')' after condition.");

int skipThen = emitJump(Op::JumpIfFalse); // Skip then part if false
    emit(Op::Pop);
    statement();
    int skipElse = emitJump(Op::Jump); // Skip else part if true
    setJump(skipThen);
    emit(Op::Pop);
    if (match(Token::Type::Else)) {
      statement();
    }
    setJump(skipElse);
  }

auto whileStatement() -> void {
    int start = chunk().size();

consume(Token::Type::LeftParen, "Expect '(' after 'while'.");
    expression();
    consume(Token::Type::RightParen, "Expect ')' after condition.");

int exit = emitJump(Op::JumpIfFalse);
    emit(Op::Pop);
    statement();
    emitLoop(start);

setJump(exit);
    emit(Op::Pop);
  }

auto emitJump(Op op) -> int {
    emit(op, 0xff, 0xff);
    return int(chunk().size() - 2);
  }

auto setJump(int offset) -> void {
    if (auto jump = int(chunk().size()) - offset - 2;
        jump <= std::numeric_limits<uint16_t>::max()) {
      chunk().set(offset, (jump >> 8) & 0xff);
      chunk().set(offset + 1, jump & 0xff);
    } else {
      error(previous, "Too much code to jump over.");
    }
  }

auto emitLoop(int offset) -> void {
    emit(Op::Loop);
    if (auto jump = int(chunk().size() - offset + 2);
        jump <= std::numeric_limits<uint16_t>::max()) {
      emit((jump >> 8) & 0xff);
      emit(jump & 0xff);
    } else {
      error(previous, "Loop body too large.");
    }
  }
};

//
// VM
//

struct VM {
  enum class Result {
    Ok,
    CompileError,
    RuntimeError,
  };

auto interpret(Chunk &chunk) -> Result {
    alignas(Value) std::byte stack[256 * sizeof(Value)];
    const auto stackBottom = reinterpret_cast<Value *>(stack);
    auto stackTop = stackBottom;

const auto push = [&](auto &&value) -> void {
      *stackTop++ = Value(value);
    };

const auto pop = [&]() -> Value {
      return *--stackTop;
    };

const auto peek = [&](int distance) -> const Value & {
      return stackTop[-1 - distance];
    };

const auto clear = [&]() -> void {
      while (stackTop > stackBottom) {
        pop();
      }
    };

auto ip = chunk.start();

const auto readByte = [&]() -> uint8_t {
      return *ip++;
    };

const auto readShort = [&]() -> uint16_t {
      ip += 2;
      return ip[-2] << 8 | ip[-1];
    };

const auto readConstant = [&]() -> Value {
      return chunk.constant(readByte());
    };

auto errored = false;

const auto error = [&](const char *fmt, auto &&... args) -> void {
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wformat-security"
      fprintf(stderr, fmt, args...);
#pragma clang diagnostic pop

auto offset = ip - chunk.start() - 1;
      auto line = chunk.line(offset);
      fprintf(stderr, "\n[line %d] in script\n", line);

clear();
      errored = true;
    };

const auto binary = [&](auto &&f) -> void {
      if constexpr (Flags::typeErrors) {
        if (!(peek(0).is<double>() && peek(1).is<double>())) {
          error("Operands must be numbers.");
          return;
        }
      }
      auto b = pop().as<double>();
      auto a = pop().as<double>();
      push(f(a, b));
    };

const auto log = [&]() {
      std::printf("          ");
      for (auto slot = stackBottom; slot < stackTop; ++slot) {
        std::printf("[ ");
        slot->print();
        std::printf(" ]");
      }
      std::printf("\n");
      Disassembly(chunk).instruction(int(ip - 1 - chunk.start()));
    };

static std::array dispatch { OP_NAMES(&&Label) };
#define DISPATCH()                                                                                 \
  do {                                                                                             \
    if (errored) {                                                                                 \
      return Result::RuntimeError;                                                                 \
    }                                                                                              \
    goto *dispatch[readByte()];                                                                    \
  } while (0)
#define CASE(type)                                                                                 \
  Label##type : if constexpr (Flags::vmLogs) {                                                     \
    log();                                                                                         \
  }
    DISPATCH();

CASE(Constant) {
      push(readConstant());
      DISPATCH();
    }
    CASE(Zero) {
      push(0.0);
      DISPATCH();
    }
    CASE(One) {
      push(1.0);
      DISPATCH();
    }
    CASE(NegativeOne) {
      push(-1.0);
      DISPATCH();
    }
    CASE(Nil) {
      push(Value::Nil());
      DISPATCH();
    }
    CASE(True) {
      push(true);
      DISPATCH();
    }
    CASE(False) {
      push(false);
      DISPATCH();
    }

CASE(Pop) {
      pop();
      DISPATCH();
    }

CASE(GetLocal) {
      push(stackBottom[readByte()]);
      DISPATCH();
    }
    CASE(SetLocal) {
      stackBottom[readByte()] = peek(0);
      DISPATCH();
    }
    CASE(GetLocal0) {
      push(stackBottom[0]);
      DISPATCH();
    }
    CASE(SetLocal0) {
      stackBottom[0] = peek(0);
      DISPATCH();
    }
    CASE(GetLocal1) {
      push(stackBottom[1]);
      DISPATCH();
    }
    CASE(SetLocal1) {
      stackBottom[1] = peek(0);
      DISPATCH();
    }
    CASE(GetLocal2) {
      push(stackBottom[2]);
      DISPATCH();
    }
    CASE(SetLocal2) {
      stackBottom[2] = peek(0);
      DISPATCH();
    }
    CASE(GetLocal3) {
      push(stackBottom[3]);
      DISPATCH();
    }
    CASE(SetLocal3) {
      stackBottom[3] = peek(0);
      DISPATCH();
    }
    CASE(GetLocal4) {
      push(stackBottom[4]);
      DISPATCH();
    }
    CASE(SetLocal4) {
      stackBottom[4] = peek(0);
      DISPATCH();
    }
    CASE(GetLocal5) {
      push(stackBottom[5]);
      DISPATCH();
    }
    CASE(SetLocal5) {
      stackBottom[5] = peek(0);
      DISPATCH();
    }

CASE(DefineGlobal) {
      auto name = readConstant().as<Value::String *>();
      globals.set(name, peek(0));
      pop();
      DISPATCH();
    }
    CASE(GetGlobal) {
      auto name = readConstant().as<Value::String *>();
      if (auto value = globals.get(name)) {
        push(value);
      } else {
        error("Undefined variable '%s'.", name->str.c_str());
        return Result::RuntimeError;
      }
      DISPATCH();
    }
    CASE(SetGlobal) {
      auto name = readConstant().as<Value::String *>();
      if (globals.set(name, peek(0))) {
        globals.remove(name);
        error("Undefined variable '%s'.", name->str.c_str());
        return Result::RuntimeError;
      }
      DISPATCH();
    }

CASE(Equal) {
      auto b = pop();
      auto a = pop();
      push(a == b);
      DISPATCH();
    }

CASE(Greater) {
      binary(std::greater());
      DISPATCH();
    }
    CASE(Less) {
      binary(std::less());
      DISPATCH();
    }
    CASE(Add) {
      binary(std::plus());
      DISPATCH();
    }
    CASE(Subtract) {
      binary(std::minus());
      DISPATCH();
    }
    CASE(Multiply) {
      binary(std::multiplies());
      DISPATCH();
    }
    CASE(Divide) {
      binary(std::divides());
      DISPATCH();
    }

CASE(Not) {
      push(pop().isFalsey());
      DISPATCH();
    }
    CASE(Negate) {
      if constexpr (Flags::typeErrors) {
        if (!peek(0).is<double>()) {
          error("Operator must be a number");
          return Result::RuntimeError;
        }
      }
      push(-pop().as<double>());
      DISPATCH();
    }

CASE(Print) {
      pop().print();
      std::printf("\n");
      DISPATCH();
    }

CASE(Jump) {
      ip += readShort();
      DISPATCH();
    }
    CASE(JumpIfFalse) {
      auto jump = readShort();
      if (peek(0).isFalsey()) {
        ip += jump;
      }
      DISPATCH();
    }
    CASE(Loop) {
      ip -= readShort();
      DISPATCH();
    }
    CASE(Return) {
      return Result::Ok;
    }
#undef CASE
#undef DISPATCH
  }

auto interpret(std::string_view source) -> Result {
    if (auto chunk = Compiler(source, strings).compile()) {
      return interpret(*chunk);
    } else {
      return Result::CompileError;
    }
  }

private:
  OwnTable strings;
  RefTable globals;
};

//
// main
//

auto main(int argc, const char *argv[]) -> int {
  //  Quick example program:

VM().interpret(R"(
    {
      print "hello, fibonacci!";
      var a = 0;
      var b = 1;
      print a;
      print b;
      while (b < 50) {
        var t = b;
        b = a + b;
        a = t;
        print b;
      }
    }
  )");

//  The language doesn't have functions (yet!)

//  I ran the following benchmark on my computer in a few
  //  non-JIT VMs including this one:
  //  
  //    {
  //      var x = 0;
  //      var y = 2;
  //      while (x < 100000000) {
  //        x = x + 1;
  //        y = y + x;
  //      }
  //      print x + y;
  //    }
  //  
  //  Results:
  //  
  //    luajit (jit off)   0.59s
  //    *this vm*          0.99s         <---
  //    node.js (jit off)  1.47s
  //    lua                1.64s
  //    jsc (jit off)      3.56s
  //    python             9.69s

return 0;
}