Bytecode.H

Go to the documentation of this file.

/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
#ifndef BYTECODE_H
#define BYTECODE_H
 
#include <cctype>
#include <cstdlib>
#include <limits>
#include <sstream>
#include <string>
#include <utility>
 
#include <Compiler_IR_Model.H>
#include <ah-arena.H>
#include <ah-errors.H>
#include <tpl_dynArray.H>
 
namespace Aleph
{
  using Compiler_Bytecode_Register_Id = size_t;
  using Compiler_Bytecode_Constant_Id = size_t;
  using Compiler_Bytecode_Function_Id = size_t;
  using Compiler_Bytecode_Block_Id = size_t;
  using Compiler_Bytecode_PC = size_t;
 
  inline constexpr size_t
  compiler_bytecode_invalid_id() noexcept
  {
    return std::numeric_limits<size_t>::max();
  }
 
  enum class Compiler_Bytecode_Constant_Kind
  {
    Unit,      
    Boolean,   
    Integer,   
    String,    
    Character, 
    Raw_Text   
  };
 
  enum class Compiler_Bytecode_Opcode
  {
    Load_Constant, 
    Load_Local,    
    Store_Local,   
    Load_Global,   
    Store_Global,  
    Load_Function, 
    Unary,         
    Binary,        
    Call,          
    Jump,          
    Branch,        
    Return,        
    Halt,          
    Trap           
  };
 
  inline const char *
  compiler_bytecode_constant_kind_name(const Compiler_Bytecode_Constant_Kind kind) noexcept
  {
    switch (kind)
      {
      case Compiler_Bytecode_Constant_Kind::Unit:
        return "Unit";
      case Compiler_Bytecode_Constant_Kind::Boolean:
        return "Boolean";
      case Compiler_Bytecode_Constant_Kind::Integer:
        return "Integer";
      case Compiler_Bytecode_Constant_Kind::String:
        return "String";
      case Compiler_Bytecode_Constant_Kind::Character:
        return "Character";
      case Compiler_Bytecode_Constant_Kind::Raw_Text:
        return "RawText";
      }
 
    return "Unknown";
  }
 
  inline const char *
  compiler_bytecode_opcode_name(const Compiler_Bytecode_Opcode opcode) noexcept
  {
    switch (opcode)
      {
      case Compiler_Bytecode_Opcode::Load_Constant:
        return "LoadConst";
      case Compiler_Bytecode_Opcode::Load_Local:
        return "LoadLocal";
      case Compiler_Bytecode_Opcode::Store_Local:
        return "StoreLocal";
      case Compiler_Bytecode_Opcode::Load_Global:
        return "LoadGlobal";
      case Compiler_Bytecode_Opcode::Store_Global:
        return "StoreGlobal";
      case Compiler_Bytecode_Opcode::Load_Function:
        return "LoadFunction";
      case Compiler_Bytecode_Opcode::Unary:
        return "Unary";
      case Compiler_Bytecode_Opcode::Binary:
        return "Binary";
      case Compiler_Bytecode_Opcode::Call:
        return "Call";
      case Compiler_Bytecode_Opcode::Jump:
        return "Jump";
      case Compiler_Bytecode_Opcode::Branch:
        return "Branch";
      case Compiler_Bytecode_Opcode::Return:
        return "Return";
      case Compiler_Bytecode_Opcode::Halt:
        return "Halt";
      case Compiler_Bytecode_Opcode::Trap:
        return "Trap";
      }
 
    return "Unknown";
  }
 
  struct Compiler_Bytecode_Constant
  {
    Compiler_Bytecode_Constant_Kind kind = Compiler_Bytecode_Constant_Kind::Raw_Text; 
    Compiler_Type_Id type_id = 0; 
    std::string text; 
    long long integer_value = 0; 
    bool bool_value = false; 
    char char_value = '\0'; 
  };
 
  struct Compiler_Bytecode_Instruction
  {
    Compiler_Bytecode_PC pc = compiler_bytecode_invalid_id(); 
    Compiler_Bytecode_Opcode opcode = Compiler_Bytecode_Opcode::Trap; 
    Compiler_Bytecode_Register_Id destination = 0; 
    Compiler_Type_Id type_id = 0; 
    Source_Span span; 
    Compiler_Operator_Kind op = Compiler_Operator_Kind::Invalid; 
    Compiler_IR_Local_Slot_Id local_slot_id = compiler_ir_invalid_id(); 
    Compiler_IR_Global_Slot_Id global_slot_id = compiler_ir_invalid_id(); 
    Compiler_Bytecode_Constant_Id constant_id = compiler_bytecode_invalid_id(); 
    Compiler_Bytecode_Function_Id function_id = compiler_bytecode_invalid_id(); 
    DynArray<Compiler_Bytecode_Register_Id> operands; 
    Compiler_Bytecode_PC target_pc = compiler_bytecode_invalid_id(); 
    Compiler_Bytecode_PC false_target_pc = compiler_bytecode_invalid_id(); 
  };
 
  struct Compiler_Bytecode_Block_Info
  {
    Compiler_Bytecode_Block_Id id = compiler_bytecode_invalid_id(); 
    Compiler_IR_Block_Id source_block_id = compiler_ir_invalid_id(); 
    std::string label; 
    Compiler_Bytecode_PC begin_pc = compiler_bytecode_invalid_id(); 
    Compiler_Bytecode_PC end_pc = compiler_bytecode_invalid_id(); 
  };
 
  struct Compiler_Bytecode_Function
  {
    Compiler_Bytecode_Function_Id id = compiler_bytecode_invalid_id(); 
    std::string name; 
    bool top_level = false; 
    Source_Span span; 
    Compiler_Type_Id type_id = 0; 
    const Compiler_IR_Function * source_function = nullptr; 
    DynArray<Compiler_IR_Slot> local_slots; 
    DynArray<Compiler_Bytecode_Constant> constants; 
    DynArray<Compiler_Bytecode_Block_Info> blocks; 
    DynArray<Compiler_Bytecode_Instruction> code; 
    Compiler_Bytecode_PC entry_pc = compiler_bytecode_invalid_id(); 
    Compiler_Bytecode_PC exit_pc = compiler_bytecode_invalid_id(); 
    size_t register_count = 0; 
 
    bool is_top_level() const noexcept
    {
      return top_level;
    }
  };
 
  struct Compiler_Bytecode_Module
  {
    DynArray<Compiler_IR_Slot> global_slots; 
    DynArray<Compiler_Bytecode_Function *> functions; 
    Compiler_Bytecode_Function * top_level = nullptr; 
  };
 
  class Compiler_Bytecode_Context
  {
    struct Owned_Object
    {
      void * ptr = nullptr;
      void (*destroy)(void *) noexcept = nullptr;
    };
 
    AhArenaAllocator arena;
    DynArray<Owned_Object> owned;
 
  public:
    explicit Compiler_Bytecode_Context(const size_t arena_size = AhArenaAllocator::DEFAULT_SIZE)
      : arena(arena_size)
    {}
 
    Compiler_Bytecode_Context(const Compiler_Bytecode_Context &) = delete;
    Compiler_Bytecode_Context & operator=(const Compiler_Bytecode_Context &) = delete;
 
    ~Compiler_Bytecode_Context() noexcept
    {
      reset();
    }
 
    template <typename T, typename... Args> T *
    make(Args &&... args)
    {
      T * ptr = allocate<T>(arena, std::forward<Args>(args)...);
      ah_runtime_error_unless(ptr != nullptr)
        << "Compiler_Bytecode_Context: arena allocation failed";
 
      owned.append({
          ptr,
          [](void * raw) noexcept
          {
            static_cast<T *>(raw)->~T();
          }
        });
      return ptr;
    }
 
    void reset() noexcept
    {
      for (size_t i = owned.size(); i > 0; --i)
        {
          auto &[ptr, destroy] = owned.access(i - 1);
          if (destroy != nullptr and ptr != nullptr)
            destroy(ptr);
        }
      owned.clear();
      arena.reset();
    }
  };
 
  struct Compiler_Bytecode_Validation_Report
  {
    bool valid = true; 
    DynArray<std::string> errors; 
    DynArray<std::string> warnings; 
  };
 
  namespace Compiler_Bytecode_Detail
  {
    inline std::string
    register_name(const Compiler_Bytecode_Register_Id id)
    {
      return "r" + std::to_string(id);
    }
 
    inline std::string
    constant_name(const Compiler_Bytecode_Constant_Id id)
    {
      return "k" + std::to_string(id);
    }
 
    inline std::string
    block_name(const Compiler_Bytecode_Block_Id id)
    {
      return "B" + std::to_string(id);
    }
 
    inline std::string
    local_slot_name(const Compiler_IR_Local_Slot_Id id)
    {
      return "s" + std::to_string(id);
    }
 
    inline std::string
    global_slot_name(const Compiler_IR_Global_Slot_Id id)
    {
      return "g" + std::to_string(id);
    }
 
    inline std::string
    function_name(const Compiler_Bytecode_Function_Id id)
    {
      return "f" + std::to_string(id);
    }
 
    inline const char *
    token_name(const Compiler_Operator_Kind kind) noexcept
    {
      return compiler_operator_name(kind);
    }
 
    inline void
    append_indented_text(std::ostream & out,
                         const std::string & text,
                         const size_t indent)
    {
      const std::string padding(indent, ' ');
      size_t begin = 0;
      while (begin < text.size())
        {
          const auto end = text.find('\n', begin);
          if (end == std::string::npos)
            {
              out << padding << text.substr(begin) << '\n';
              return;
            }
 
          if (end > begin)
            out << padding << text.substr(begin, end - begin) << '\n';
          else
            out << padding << '\n';
          begin = end + 1;
        }
    }
 
    inline bool
    parse_integer(const std::string & text,
                  long long & value) noexcept
    {
      if (text.empty())
        return false;
 
      char * end = nullptr;
      value = std::strtoll(text.c_str(), &end, 10);
      return end != nullptr and *end == '\0';
    }
 
    inline std::string
    decode_escape_string(const std::string & raw)
    {
      std::string result;
      result.reserve(raw.size());
      for (size_t i = 0; i < raw.size(); ++i)
        {
          if (raw[i] != '\\' or i + 1 >= raw.size())
            {
              result += raw[i];
              continue;
            }
          ++i;
          switch (raw[i])
            {
            case 'n':  result += '\n'; break;
            case 't':  result += '\t'; break;
            case 'r':  result += '\r'; break;
            case '\\': result += '\\'; break;
            case '\'': result += '\''; break;
            case '"':  result += '"';  break;
            case '0':  result += '\0'; break;
            case 'a':  result += '\a'; break;
            case 'b':  result += '\b'; break;
            case 'f':  result += '\f'; break;
            case 'v':  result += '\v'; break;
            case 'x':
              {
                if (i + 2 < raw.size() and std::isxdigit(static_cast<unsigned char>(raw[i+1]))
                    and std::isxdigit(static_cast<unsigned char>(raw[i+2])))
                  {
                    const char hex[3] = {raw[i+1], raw[i+2], '\0'};
                    result += static_cast<char>(std::strtol(hex, nullptr, 16));
                    i += 2;
                  }
                else
                  result += raw[i];
                break;
              }
            default:
              result += '\\';
              result += raw[i];
              break;
            }
        }
      return result;
    }
 
    inline char
    decode_escape_char(const std::string & raw)
    {
      if (raw.empty())
        return '\0';
      if (raw[0] != '\\')
        return raw[0];
      if (raw.size() < 2)
        return '\\';
      switch (raw[1])
        {
        case 'n':  return '\n';
        case 't':  return '\t';
        case 'r':  return '\r';
        case '\\': return '\\';
        case '\'': return '\'';
        case '"':  return '"';
        case '0':  return '\0';
        case 'a':  return '\a';
        case 'b':  return '\b';
        case 'f':  return '\f';
        case 'v':  return '\v';
        default:   return raw[1];
        }
    }
 
    inline Compiler_Bytecode_Constant
    classify_constant(const Compiler_IR_Instruction & inst)
    {
      Compiler_Bytecode_Constant constant;
      constant.type_id = inst.type_id;
      constant.text = inst.text;
      constant.bool_value = inst.bool_value;
 
      if (inst.text == "unit")
        {
          constant.kind = Compiler_Bytecode_Constant_Kind::Unit;
          return constant;
        }
 
      if (inst.text == "true" or inst.text == "false")
        {
          constant.kind = Compiler_Bytecode_Constant_Kind::Boolean;
          constant.bool_value = inst.text == "true";
          return constant;
        }
 
      long long integer_value = 0;
      if (parse_integer(inst.text, integer_value))
        {
          constant.kind = Compiler_Bytecode_Constant_Kind::Integer;
          constant.integer_value = integer_value;
          return constant;
        }
 
      if (inst.text.size() >= 2 and inst.text.front() == '"' and inst.text.back() == '"')
        {
          constant.kind = Compiler_Bytecode_Constant_Kind::String;
          const auto inner = inst.text.substr(1, inst.text.size() - 2);
          constant.text = decode_escape_string(inner);
          return constant;
        }
 
      if (inst.text.size() >= 3 and inst.text.front() == '\'' and inst.text.back() == '\'')
        {
          constant.kind = Compiler_Bytecode_Constant_Kind::Character;
          const auto inner = inst.text.substr(1, inst.text.size() - 2);
          constant.char_value = decode_escape_char(inner);
          return constant;
        }
 
      constant.kind = Compiler_Bytecode_Constant_Kind::Raw_Text;
      return constant;
    }
 
    inline bool
    same_constant(const Compiler_Bytecode_Constant & lhs,
                  const Compiler_Bytecode_Constant & rhs) noexcept
    {
      return lhs.kind == rhs.kind
             and lhs.type_id == rhs.type_id
             and lhs.text == rhs.text
             and lhs.integer_value == rhs.integer_value
             and lhs.bool_value == rhs.bool_value
             and lhs.char_value == rhs.char_value;
    }
 
    inline Compiler_Bytecode_Constant_Id
    intern_constant(DynArray<Compiler_Bytecode_Constant> & pool,
                    const Compiler_Bytecode_Constant & constant)
    {
      for (size_t i = 0; i < pool.size(); ++i)
        if (same_constant(pool.access(i), constant))
          return i;
 
      pool.append(constant);
      return pool.size() - 1;
    }
 
    inline bool
    contains_pc(const DynArray<Compiler_Bytecode_Block_Info> & blocks,
                const Compiler_Bytecode_PC pc) noexcept
    {
      for (size_t i = 0; i < blocks.size(); ++i)
        if (blocks.access(i).begin_pc == pc)
          return true;
      return false;
    }
 
    inline std::string
    constant_to_string(const Compiler_Bytecode_Constant & constant)
    {
      switch (constant.kind)
        {
        case Compiler_Bytecode_Constant_Kind::Unit:
          return "Unit";
        case Compiler_Bytecode_Constant_Kind::Boolean:
          return std::string("Boolean(") + (constant.bool_value ? "true" : "false") + ")";
        case Compiler_Bytecode_Constant_Kind::Integer:
          return "Integer(" + std::to_string(constant.integer_value) + ")";
        case Compiler_Bytecode_Constant_Kind::String:
          return "String(" + constant.text + ")";
        case Compiler_Bytecode_Constant_Kind::Character:
          return "Character(" + constant.text + ")";
        case Compiler_Bytecode_Constant_Kind::Raw_Text:
          return "RawText(" + constant.text + ")";
        }
 
      return "Unknown";
    }
  }
 
  class Compiler_Bytecode_Lowering
  {
    Compiler_Bytecode_Context * ctx = nullptr;
 
    [[nodiscard]] Compiler_Bytecode_Function *
    lower_function(const Compiler_IR_Function & source,
                   const bool top_level) const
    {
      auto * function = ctx->make<Compiler_Bytecode_Function>();
      function->id = source.id;
      function->name = source.name;
      function->top_level = top_level;
      function->span = source.span;
      function->type_id = source.type_id;
      function->source_function = &source;
      function->local_slots = source.local_slots;
      function->register_count = source.next_value_id + 1;
 
      DynArray<Compiler_Bytecode_PC> block_pcs;
      for (size_t i = 0; i < source.blocks.size(); ++i)
        block_pcs.append(compiler_bytecode_invalid_id());
 
      for (size_t block_id = 0; block_id < source.blocks.size(); ++block_id)
        {
          const auto & block = source.blocks.access(block_id);
          Compiler_Bytecode_Block_Info info;
          info.id = block_id;
          info.source_block_id = block.id;
          info.label = block.label;
          info.begin_pc = function->code.size();
          block_pcs.access(block_id) = info.begin_pc;
 
          for (size_t inst_index = 0; inst_index < block.instructions.size(); ++inst_index)
            {
              const auto & inst = block.instructions.access(inst_index);
              Compiler_Bytecode_Instruction lowered;
              lowered.pc = function->code.size();
              lowered.destination = inst.result_id;
              lowered.type_id = inst.type_id;
              lowered.span = inst.span;
              lowered.op = inst.op;
 
              switch (inst.kind)
                {
                case Compiler_IR_Instruction_Kind::Constant:
                  lowered.opcode = Compiler_Bytecode_Opcode::Load_Constant;
                  lowered.constant_id =
                    Compiler_Bytecode_Detail::intern_constant(function->constants,
                                                              Compiler_Bytecode_Detail::classify_constant(inst));
                  break;
 
                case Compiler_IR_Instruction_Kind::Load:
                  if (inst.local_slot_id != compiler_ir_invalid_id())
                    {
                      lowered.opcode = Compiler_Bytecode_Opcode::Load_Local;
                      lowered.local_slot_id = inst.local_slot_id;
                    }
                  else
                    {
                      lowered.opcode = Compiler_Bytecode_Opcode::Load_Global;
                      lowered.global_slot_id = inst.global_slot_id;
                    }
                  break;
 
                case Compiler_IR_Instruction_Kind::Store:
                  if (inst.local_slot_id != compiler_ir_invalid_id())
                    {
                      lowered.opcode = Compiler_Bytecode_Opcode::Store_Local;
                      lowered.local_slot_id = inst.local_slot_id;
                    }
                  else
                    {
                      lowered.opcode = Compiler_Bytecode_Opcode::Store_Global;
                      lowered.global_slot_id = inst.global_slot_id;
                    }
                  lowered.destination = 0;
                  lowered.operands = inst.operands;
                  break;
 
                case Compiler_IR_Instruction_Kind::Unary:
                  lowered.opcode = Compiler_Bytecode_Opcode::Unary;
                  lowered.operands = inst.operands;
                  break;
 
                case Compiler_IR_Instruction_Kind::Binary:
                  lowered.opcode = Compiler_Bytecode_Opcode::Binary;
                  lowered.operands = inst.operands;
                  break;
 
                case Compiler_IR_Instruction_Kind::Call:
                  lowered.opcode = Compiler_Bytecode_Opcode::Call;
                  lowered.operands = inst.operands;
                  break;
 
                case Compiler_IR_Instruction_Kind::Function_Ref:
                  lowered.opcode = Compiler_Bytecode_Opcode::Load_Function;
                  lowered.function_id = inst.function_id;
                  break;
                }
 
              function->code.append(std::move(lowered));
            }
 
          Compiler_Bytecode_Instruction terminator;
          terminator.pc = function->code.size();
          terminator.span = block.terminator.span;
 
          switch (block.terminator.kind)
            {
            case Compiler_IR_Terminator_Kind::Jump:
              terminator.opcode = Compiler_Bytecode_Opcode::Jump;
              terminator.target_pc = block.terminator.successors.is_empty()
                ? compiler_bytecode_invalid_id()
                : block.terminator.successors.access(0);
              break;
 
            case Compiler_IR_Terminator_Kind::Branch:
              terminator.opcode = Compiler_Bytecode_Opcode::Branch;
              terminator.operands.append(block.terminator.condition_value);
              terminator.target_pc = block.terminator.successors.size() > 0
                ? block.terminator.successors.access(0)
                : compiler_bytecode_invalid_id();
              terminator.false_target_pc = block.terminator.successors.size() > 1
                ? block.terminator.successors.access(1)
                : compiler_bytecode_invalid_id();
              break;
 
            case Compiler_IR_Terminator_Kind::Return:
              terminator.opcode = Compiler_Bytecode_Opcode::Return;
              terminator.operands.append(block.terminator.return_value);
              break;
 
            case Compiler_IR_Terminator_Kind::Exit:
              terminator.opcode = Compiler_Bytecode_Opcode::Halt;
              break;
 
            case Compiler_IR_Terminator_Kind::Unreachable:
              terminator.opcode = Compiler_Bytecode_Opcode::Trap;
              break;
 
            case Compiler_IR_Terminator_Kind::None:
              terminator.opcode = Compiler_Bytecode_Opcode::Trap;
              break;
            }
 
          function->code.append(std::move(terminator));
          info.end_pc = function->code.size();
          function->blocks.append(std::move(info));
        }
 
      for (size_t i = 0; i < function->code.size(); ++i)
        {
          auto & inst = function->code.access(i);
          if (inst.opcode == Compiler_Bytecode_Opcode::Jump)
            inst.target_pc = inst.target_pc < block_pcs.size()
              ? block_pcs.access(inst.target_pc)
              : compiler_bytecode_invalid_id();
          else if (inst.opcode == Compiler_Bytecode_Opcode::Branch)
            {
              inst.target_pc = inst.target_pc < block_pcs.size()
                ? block_pcs.access(inst.target_pc)
                : compiler_bytecode_invalid_id();
              inst.false_target_pc = inst.false_target_pc < block_pcs.size()
                ? block_pcs.access(inst.false_target_pc)
                : compiler_bytecode_invalid_id();
            }
        }
 
      function->entry_pc = source.entry_block < block_pcs.size()
        ? block_pcs.access(source.entry_block)
        : compiler_bytecode_invalid_id();
      function->exit_pc = source.exit_block < block_pcs.size()
        ? block_pcs.access(source.exit_block)
        : compiler_bytecode_invalid_id();
      return function;
    }
 
  public:
    explicit Compiler_Bytecode_Lowering(Compiler_Bytecode_Context & context) noexcept
      : ctx(&context)
    {}
 
    Compiler_Bytecode_Module *
    lower_module(const Compiler_IR_Module * module) const
    {
      ah_runtime_error_unless(module != nullptr)
        << "Compiler_Bytecode_Lowering::lower_module(): null IR module";
 
      auto * result = ctx->make<Compiler_Bytecode_Module>();
      result->global_slots = module->global_slots;
      for (size_t i = 0; i < module->functions.size(); ++i)
        result->functions.append(lower_function(*module->functions.access(i), false));
      if (module->top_level != nullptr)
        result->top_level = lower_function(*module->top_level, true);
      return result;
    }
  };
 
  inline Compiler_Bytecode_Validation_Report
  validate_bytecode_function(const Compiler_Bytecode_Function & function,
                             const Compiler_Bytecode_Module * module = nullptr)
  {
    Compiler_Bytecode_Validation_Report report;
 
    auto fail = [&report](const std::string & message)
    {
      report.valid = false;
      report.errors.append(message);
    };
 
    if (function.code.is_empty())
      {
        fail("Bytecode function '" + function.name + "' has no instructions");
        return report;
      }
 
    if (function.blocks.is_empty())
      fail("Bytecode function '" + function.name + "' has no block metadata");
    if (function.entry_pc >= function.code.size())
      fail("Bytecode function '" + function.name + "' has invalid entry pc");
    if (function.exit_pc >= function.code.size())
      fail("Bytecode function '" + function.name + "' has invalid exit pc");
 
    if (not report.valid)
      return report;
 
    for (size_t block_id = 0; block_id < function.blocks.size(); ++block_id)
      {
        const auto & block = function.blocks.access(block_id);
        if (block.id != block_id)
          fail("Bytecode function '" + function.name + "' has mismatched block id at "
               + Compiler_Bytecode_Detail::block_name(block_id));
        if (block.begin_pc >= block.end_pc or block.end_pc > function.code.size())
          fail("Bytecode block " + Compiler_Bytecode_Detail::block_name(block_id)
               + " in function '" + function.name + "' has invalid pc range");
      }
 
    if (not Compiler_Bytecode_Detail::contains_pc(function.blocks, function.entry_pc))
      fail("Bytecode function '" + function.name + "' entry pc does not match any block start");
    if (not Compiler_Bytecode_Detail::contains_pc(function.blocks, function.exit_pc))
      fail("Bytecode function '" + function.name + "' exit pc does not match any block start");
 
    for (size_t pc = 0; pc < function.code.size(); ++pc)
      {
        const auto & inst = function.code.access(pc);
        if (inst.pc != pc)
          fail("Bytecode function '" + function.name + "' has mismatched pc at "
               + std::to_string(pc));
 
        const auto check_register = [&fail, &function, pc](const Compiler_Bytecode_Register_Id reg,
                                                           const std::string & what)
        {
          if (reg >= function.register_count)
            fail("Bytecode instruction at pc "
                 + std::to_string(pc) + " in function '" + function.name
                 + "' references invalid register for " + what);
        };
 
        if ((inst.opcode == Compiler_Bytecode_Opcode::Load_Constant
             or inst.opcode == Compiler_Bytecode_Opcode::Load_Local
             or inst.opcode == Compiler_Bytecode_Opcode::Load_Global
             or inst.opcode == Compiler_Bytecode_Opcode::Load_Function
             or inst.opcode == Compiler_Bytecode_Opcode::Unary
             or inst.opcode == Compiler_Bytecode_Opcode::Binary
             or inst.opcode == Compiler_Bytecode_Opcode::Call)
            and inst.destination == 0)
          fail("Bytecode producer instruction at pc " + std::to_string(pc)
               + " in function '" + function.name + "' must define a destination register");
 
        if (inst.destination != 0)
          check_register(inst.destination, "destination");
 
        for (size_t operand_index = 0; operand_index < inst.operands.size(); ++operand_index)
          check_register(inst.operands.access(operand_index),
                         "operand #" + std::to_string(operand_index));
 
        if (inst.opcode == Compiler_Bytecode_Opcode::Load_Constant
            and inst.constant_id >= function.constants.size())
          fail("Bytecode instruction at pc " + std::to_string(pc)
               + " in function '" + function.name + "' references invalid constant id");
 
        if ((inst.opcode == Compiler_Bytecode_Opcode::Load_Local
             or inst.opcode == Compiler_Bytecode_Opcode::Store_Local)
            and inst.local_slot_id >= function.local_slots.size())
          fail("Bytecode instruction at pc " + std::to_string(pc)
               + " in function '" + function.name + "' references invalid local slot");
 
        if ((inst.opcode == Compiler_Bytecode_Opcode::Load_Global
             or inst.opcode == Compiler_Bytecode_Opcode::Store_Global)
            and (module == nullptr or inst.global_slot_id >= module->global_slots.size()))
          fail("Bytecode instruction at pc " + std::to_string(pc)
               + " in function '" + function.name + "' references invalid global slot");
 
        if (inst.opcode == Compiler_Bytecode_Opcode::Load_Function
            and (module == nullptr or inst.function_id >= module->functions.size()))
          fail("Bytecode instruction at pc " + std::to_string(pc)
               + " in function '" + function.name + "' references invalid function id");
 
        if ((inst.opcode == Compiler_Bytecode_Opcode::Jump
             or inst.opcode == Compiler_Bytecode_Opcode::Branch)
            and (inst.target_pc >= function.code.size()
                 or not Compiler_Bytecode_Detail::contains_pc(function.blocks, inst.target_pc)))
          fail("Bytecode control-flow instruction at pc " + std::to_string(pc)
               + " in function '" + function.name + "' has invalid target pc");
 
        if (inst.opcode == Compiler_Bytecode_Opcode::Branch
            and (inst.false_target_pc >= function.code.size()
                 or not Compiler_Bytecode_Detail::contains_pc(function.blocks, inst.false_target_pc)))
          fail("Bytecode branch at pc " + std::to_string(pc)
               + " in function '" + function.name + "' has invalid false target pc");
      }
 
    return report;
  }
 
  inline Compiler_Bytecode_Validation_Report
  validate_bytecode_module(const Compiler_Bytecode_Module & module)
  {
    Compiler_Bytecode_Validation_Report report;
 
    auto merge = [&report](const Compiler_Bytecode_Validation_Report & child)
    {
      if (not child.valid)
        report.valid = false;
      for (size_t i = 0; i < child.errors.size(); ++i)
        report.errors.append(child.errors.access(i));
      for (size_t i = 0; i < child.warnings.size(); ++i)
        report.warnings.append(child.warnings.access(i));
    };
 
    for (size_t i = 0; i < module.functions.size(); ++i)
      merge(validate_bytecode_function(*module.functions.access(i), &module));
    if (module.top_level != nullptr)
      merge(validate_bytecode_function(*module.top_level, &module));
    return report;
  }
 
  inline std::string
  compiler_dump_bytecode_function(const Compiler_Bytecode_Function * function,
                                  const Compiler_Bytecode_Module * module = nullptr,
                                  const Compiler_Type_Context * types = nullptr)
  {
    (void) module;
    std::ostringstream out;
    if (function == nullptr)
      {
        out << "<null-bytecode-function>\n";
        return out.str();
      }
 
    out << "BytecodeFunction(" << function->name << ")";
    if (types != nullptr and function->type_id != 0)
      out << ": " << types->to_string(function->type_id);
    out << '\n';
    out << "  EntryPC: " << function->entry_pc << '\n';
    out << "  ExitPC: " << function->exit_pc << '\n';
    out << "  Registers: " << function->register_count << '\n';
 
    if (not function->local_slots.is_empty())
      {
        out << "  Slots:\n";
        for (size_t i = 0; i < function->local_slots.size(); ++i)
          {
            const auto & slot = function->local_slots.access(i);
            out << "    " << Compiler_Bytecode_Detail::local_slot_name(slot.id)
                << " [" << compiler_ir_slot_kind_name(slot.kind) << "] "
                << slot.name;
            if (types != nullptr and slot.type_id != 0)
              out << ": " << types->to_string(slot.type_id);
            out << '\n';
          }
      }
 
    if (function->constants.is_empty())
      out << "  Constants: <none>\n";
    else
      {
        out << "  Constants:\n";
        for (size_t i = 0; i < function->constants.size(); ++i)
          {
            out << "    " << Compiler_Bytecode_Detail::constant_name(i)
                << " = " << Compiler_Bytecode_Detail::constant_to_string(
                  function->constants.access(i));
            if (types != nullptr and function->constants.access(i).type_id != 0)
              out << " : " << types->to_string(function->constants.access(i).type_id);
            out << '\n';
          }
      }
 
    if (not function->blocks.is_empty())
      {
        out << "  Blocks:\n";
        for (size_t i = 0; i < function->blocks.size(); ++i)
          {
            const auto & block = function->blocks.access(i);
            out << "    " << Compiler_Bytecode_Detail::block_name(block.id)
                << " [src=" << Compiler_IR_Detail::block_name(block.source_block_id)
                << ", " << block.label << "] "
                << "pc=" << block.begin_pc << ".." << block.end_pc << '\n';
          }
      }
 
    out << "  Code:\n";
    for (size_t i = 0; i < function->code.size(); ++i)
      {
        const auto & inst = function->code.access(i);
        out << "    " << inst.pc << ": "
            << compiler_bytecode_opcode_name(inst.opcode);
 
        switch (inst.opcode)
          {
          case Compiler_Bytecode_Opcode::Load_Constant:
            out << " " << Compiler_Bytecode_Detail::register_name(inst.destination)
                << ", " << Compiler_Bytecode_Detail::constant_name(inst.constant_id);
            break;
 
          case Compiler_Bytecode_Opcode::Load_Local:
            out << " " << Compiler_Bytecode_Detail::register_name(inst.destination)
                << ", " << Compiler_Bytecode_Detail::local_slot_name(inst.local_slot_id);
            break;
 
          case Compiler_Bytecode_Opcode::Store_Local:
            out << " " << Compiler_Bytecode_Detail::local_slot_name(inst.local_slot_id);
            if (not inst.operands.is_empty())
              out << ", " << Compiler_Bytecode_Detail::register_name(inst.operands.access(0));
            break;
 
          case Compiler_Bytecode_Opcode::Load_Global:
            out << " " << Compiler_Bytecode_Detail::register_name(inst.destination)
                << ", " << Compiler_Bytecode_Detail::global_slot_name(inst.global_slot_id);
            break;
 
          case Compiler_Bytecode_Opcode::Store_Global:
            out << " " << Compiler_Bytecode_Detail::global_slot_name(inst.global_slot_id);
            if (not inst.operands.is_empty())
              out << ", " << Compiler_Bytecode_Detail::register_name(inst.operands.access(0));
            break;
 
          case Compiler_Bytecode_Opcode::Load_Function:
            out << " " << Compiler_Bytecode_Detail::register_name(inst.destination)
                << ", " << Compiler_Bytecode_Detail::function_name(inst.function_id);
            break;
 
          case Compiler_Bytecode_Opcode::Unary:
            out << " " << Compiler_Bytecode_Detail::register_name(inst.destination)
                << ", " << Compiler_Bytecode_Detail::token_name(inst.op);
            if (not inst.operands.is_empty())
              out << ", " << Compiler_Bytecode_Detail::register_name(inst.operands.access(0));
            break;
 
          case Compiler_Bytecode_Opcode::Binary:
            out << " " << Compiler_Bytecode_Detail::register_name(inst.destination)
                << ", " << Compiler_Bytecode_Detail::token_name(inst.op);
            if (inst.operands.size() > 0)
              out << ", " << Compiler_Bytecode_Detail::register_name(inst.operands.access(0));
            if (inst.operands.size() > 1)
              out << ", " << Compiler_Bytecode_Detail::register_name(inst.operands.access(1));
            break;
 
          case Compiler_Bytecode_Opcode::Call:
            out << " " << Compiler_Bytecode_Detail::register_name(inst.destination);
            for (size_t operand = 0; operand < inst.operands.size(); ++operand)
              out << (operand == 0 ? ", " : ", ")
                  << Compiler_Bytecode_Detail::register_name(inst.operands.access(operand));
            break;
 
          case Compiler_Bytecode_Opcode::Jump:
            out << " " << inst.target_pc;
            break;
 
          case Compiler_Bytecode_Opcode::Branch:
            if (not inst.operands.is_empty())
              out << " " << Compiler_Bytecode_Detail::register_name(inst.operands.access(0));
            out << ", " << inst.target_pc << ", " << inst.false_target_pc;
            break;
 
          case Compiler_Bytecode_Opcode::Return:
            if (not inst.operands.is_empty())
              out << " " << Compiler_Bytecode_Detail::register_name(inst.operands.access(0));
            break;
 
          case Compiler_Bytecode_Opcode::Halt:
          case Compiler_Bytecode_Opcode::Trap:
            break;
          }
 
        if (types != nullptr and inst.type_id != 0)
          out << " : " << types->to_string(inst.type_id);
        out << '\n';
      }
 
    return out.str();
  }
 
  inline std::string
  compiler_dump_bytecode_module(const Compiler_Bytecode_Module * module,
                                const Compiler_Type_Context * types = nullptr)
  {
    std::ostringstream out;
    if (module == nullptr)
      {
        out << "<null-bytecode-module>\n";
        return out.str();
      }
 
    out << "BytecodeModule\n";
    if (not module->global_slots.is_empty())
      {
        out << "  Globals:\n";
        for (size_t i = 0; i < module->global_slots.size(); ++i)
          {
            const auto & slot = module->global_slots.access(i);
            out << "    " << Compiler_Bytecode_Detail::global_slot_name(slot.id)
                << " " << slot.name;
            if (types != nullptr and slot.type_id != 0)
              out << ": " << types->to_string(slot.type_id);
            out << '\n';
          }
      }
 
    for (size_t i = 0; i < module->functions.size(); ++i)
      Compiler_Bytecode_Detail::append_indented_text(out,
                                                     compiler_dump_bytecode_function(
                                                       module->functions.access(i),
                                                       module,
                                                       types),
                                                     2);
    if (module->top_level != nullptr)
      Compiler_Bytecode_Detail::append_indented_text(out,
                                                     compiler_dump_bytecode_function(
                                                       module->top_level,
                                                       module,
                                                       types),
                                                     2);
    return out.str();
  }
}
 
#endif