path: root/bxgen.c

#if 0
SRC=${0##*/}
BIN=${SRC%.*}
gcc                                                   \
  -Wno-old-style-declaration                          \
  -Wno-missing-field-initializers -Wno-missing-braces \
  -Wall -Wextra -Werror -pedantic                     \
  -O0 -fsanitize=undefined,address,leak -mshstk       \
  -o $BIN.tmp $SRC &&                                 \
  ./$BIN.tmp $@ && rm $BIN.tmp
exit $?
#endif

//  ================================================================
//
//    bxgen.c
//    Binary executable code generation - compiler backend
//
//  Qualities
//
//  - Single source file (for now)
//  - Simple and flexible API
//  - No external dependencies
//  - No configuration required
//  - No dynamic memory management
//  - Easy cross-compilation
//  - Platform-independent host
//
//  Inspirations
//
//  - Cuik    https://github.com/RealNeGate/Cuik
//  - tinycc  https://repo.or.cz/w/tinycc.git
//  - QBE     https://c9x.me/compile/
//
//  To-Do list
//
//  - ELF + x86_64 executable
//  - x86_64 object file
//  - Linking libraries
//  - Proper error handling
//  - Proper prefixes for identifiers
//  - Effective entity allocation
//  - Hybrid-linked lists for large entities
//  - Implicit procedure prototypes
//  - Implicit exit after ret from entry point
//  - Static single-assignment
//  - Sea of Nodes
//  - Optimization layers
//  - Multithreading
//  - Memory reallocation when necessary
//  - JIT
//  - COFF, PE, OMF, Mach-O
//  - i386, RISC-V, ARM, WebAssembly
//  - Built-in standard library
//
//  Bugs
//
//  - ...
//
//  Done features
//
//  - ELF header
//  - IO static dispatch
//
//  ================================================================
//
//    Compilation options
//
//  ================================================================

//#define DISABLE_IMPLEMENTATION
//#define DISABLE_HELPERS
//#define DISABLE_TESTING

//  ================================================================
//
//    Basic declarations
//
//  ================================================================

typedef signed char        i8;
typedef signed short       i16;
typedef signed int         i32;
typedef signed long long   i64;
typedef unsigned char      u8;
typedef unsigned short     u16;
typedef unsigned int       u32;
typedef unsigned long long u64;
typedef float              f32;
typedef double             f64;
typedef signed char        b8;  // 8-bit boolean
typedef int                b32; // 32-bit boolean
typedef int                s32; // 32-bit status code
typedef char               c8;  // 8-bit character

//  ================================================================
//
//    IR data declarations
//
//  ================================================================

enum {
  //  For indices
  UNDEFINED = -1,

  //  Formats
  //

  FORMAT_ELF  = 1,
  FORMAT_COFF,
  FORMAT_PE,
  FORMAT_OMF,
  FORMAT_MATCH_O,

  //  Architecture
  //

  ARCH_RISC_V = 64,
  ARCH_I386,
  ARCH_X86_64,
  ARCH_ARM,

  //  Sea of Nodes flow type
  //

  FLOW_DATA = 0,
  FLOW_CONTROL,

  //  Semantic node operations
  //

  DATA_I64 = 0,
  CTRL_CALL,
  CTRL_RET,

  //  Calling conventions

  CONV_CDECL = 0,
  CONV_STDCALL,
  CONV_FASTCALL,
  CONV_THISCALL,

  //  Primitive data types
  //

  TYPE_I32 = 0,

  //  Unit types
  //

  UNIT_CODE = 0,
  UNIT_LIBRARY_OBJECT,
  UNIT_LIBRARY_STATIC,
  UNIT_LIBRARY_DYNAMIC,

  //  Entity types
  //

  ENTITY_TAIL = 0,
  ENTITY_NODE,
  ENTITY_PROC,
  ENTITY_UNIT,

  //  Limits
  //
  //    NOTE
  //
  //    All limits can be exceeded using the linked list of entities
  //    (see `Entity::tail`), except for `MAX_ENTITY_COUNT`.
  //

  MAX_LITERAL_SIZE = 400,
  MAX_NAME_SIZE    = 80,
  MAX_PROC_COUNT   = 40,
  MAX_NODE_COUNT   = 60,
  MAX_LINK_COUNT   = 20,
  MAX_ARG_COUNT    = 20,
  MAX_ENTITY_COUNT = 16384,

  //  IO dispatch operations
  //

  IO_OPEN_READ = 0,
  IO_OPEN_WRITE,
  IO_CLOSE,
  IO_SEEK,
  IO_READ,
  IO_WRITE,
  IO_CHMOD_EXE,

  IO_SEEK_CURSOR = 0,
  IO_SEEK_BEGIN,
  IO_SEEK_END,
};

//  A semantic node is an operation with optional data
//  and possible references to other nodes.
//

typedef struct {
  i16 size;
  i16 type;
  i64 node;
} Var;

typedef struct {
  i16 val_count;
  Var vals[MAX_ARG_COUNT];
} Ret;

typedef struct {
  //    NOTE
  //    We may call a local procedure by it's id,
  //    or a global procedure by name.

  i16 convention; // can be implicitly retrieved from the procedure
  i64 target_proc;
  i64 target_name_size;
  c8  target_name[MAX_NAME_SIZE];
  i64 arg_count;
  Var args[MAX_ARG_COUNT];
} Call;

typedef struct {
  i16 op;
  i64 index_in_proc;
  union {
    u8   lit_bytes[MAX_LITERAL_SIZE]; // byte array literal
    i64  lit_int;                     // integer literal
    Ret  ret;
    Call call;
  };
} Node;

//  A procedure is a collection of semantic nodes
//  and has a string name.
//

typedef struct {
  i16 convention;
  i64 name_size;
  c8  name[MAX_NAME_SIZE];
  i64 node_count;
  i64 nodes[MAX_NODE_COUNT];
  i64 ret_index;
  i64 unit;
  i64 index_in_unit;
} Proc;

//  A compilation unit is a collection of procedures.
//

typedef struct {
  i16 type;
  i64 entry_point_index;
  i64 name_size;
  c8  name[MAX_NAME_SIZE];
  i64 proc_count;
  i64 procs[MAX_PROC_COUNT];
  i64 link_count;
  i64 links[MAX_LINK_COUNT];
} Unit;

//  An entity can be any of:
//  - `Node`
//  - `Proc`
//  - `Unit`
//
//  Every entity can be referenced by it's unique index
//  in the entity pool.
//
//  If the entity's data doesn't fit in one entity, tail is
//  an index that leads to the entity with the rest of the
//  data, forming a linked list.
//

typedef struct {
  b8  is_enabled;
  i16 type;
  i64 tail;
  union {
    Node node;
    Proc proc;
    Unit unit;
    c8   tail_chars[1];
    i64  tail_ids[1];
    Var  tail_vars[1];
  };
} Entity;

//  Pool, a collection of all entities.
//
//    NOTE
//    We use one single large memory block for *everything*.
//

typedef struct {
  i64     entity_count;
  i64     capacity;
  Entity *entities;
} Pool;

//  ================================================================
//
//    API declarations
//
//  ================================================================

#ifdef __cplusplus
extern "C" {
#endif

i64  pool_add(Pool *pool, Entity data);
void pool_remove(Pool *pool, i64 entity, i16 type);

i64  node_init(Pool *pool, Node data);
void node_destroy(Pool *pool, i64 node);
i64  node_data_i64(Pool *pool, i64 value);
i64  node_ctrl_call(Pool *pool, i16 convention, i64 target_proc, i64 arg_count, Var *args);
i64  node_ctrl_call_by_name(Pool *pool, i16 convention, i64 name_size, c8 *name, i64 arg_count, Var *args);
i64  node_ctrl_ret(Pool *pool, i64 value_count, Var *values);

i64  proc_init(Pool *pool);
void proc_destroy(Pool *pool, i64 proc);
void proc_set_convention(Pool *pool, i64 proc, i16 convention);
void proc_set_name(Pool *pool, i64 proc, i64 name_size, c8 *name);
void proc_node_add(Pool *pool, i64 proc, i64 node);
void proc_node_remove(Pool *pool, i64 proc, i64 node);

i64  unit_init(Pool *pool, i16 type);
void unit_destroy(Pool *pool, i64 unit);
void unit_proc_add(Pool *pool, i64 unit, i64 proc);
void unit_proc_remove(Pool *pool, i64 unit, i64 proc);
void unit_link_add(Pool *pool, i64 unit, i64 link_unit);
void unit_link_remove(Pool *pool, i64 unit, i64 link_unit);
void unit_set_name(Pool *pool, i64 unit, i64 name_size, c8 *name);
void unit_set_entry_point(Pool *pool, i64 unit, i64 entry_point_proc);
void unit_write(Pool *pool, i64 unit, u16 target, i64 io_id, void *io_user_data);

i64  io_open_read(i64 name_size, c8 *name, void *user_data);
i64  io_open_write(i64 name_size, c8 *name, void *user_data);
void io_close(i64 f, void *user_data);
i64  io_seek(i64 f, i64 offset, u16 origin, void *user_data);
i64  io_read(i64 f, i64 size, void *data, void *user_data);
i64  io_write(i64 f, i64 size, void *data, void *user_data);
void io_chmod_exe(i64 f, void *user_data);

void io_dispatch(i16 op, i64 *id, i64 *size, void *data, void *user_data);

#ifndef DISABLE_HELPERS
i64  n_i64(i64 value);
i64  n_call(i16 convention, i64 target_proc, i64 arg_count, Var *args);
i64  n_call_by_name(i16 convention, c8 *name, i64 arg_count, Var *args);
i64  n_ret(i64 val_count, Var *vals);
i64  p_new(c8 *name);
void p_add(i64 proc, i64 node);
i64  u_new();
void u_add(i64 unit, i64 proc);
void u_entry_point(i64 unit, i64 proc);
void u_elf_x86_64(i64 unit, c8 *output_file_name);
void l_code(i64 unit, i64 link_unit);
void l_object(i64 unit, c8 *object_library);
void l_static(i64 unit, c8 *static_library);
#endif

#ifdef __cplusplus
}
#endif

//  ================================================================
//
//    Main features implementation
//
//  ================================================================

#ifndef DISABLE_IMPLEMENTATION

#ifdef __cplusplus
#error Implementation code should be compiled with a C compiler!
#endif

#include <string.h> // memcpy
#include <assert.h> // assert

//  IR building procs
//

i64 pool_add(Pool *pool, Entity data) {
  assert(pool != NULL && pool->entities != NULL);
  assert(pool->entity_count < pool->capacity);

  i64 id             = pool->entity_count++;
  data.is_enabled    = 1,
  pool->entities[id] = data;

  return id;
}

void pool_remove(Pool *pool, i64 entity, i16 type) {
  assert(pool != NULL && pool->entities != NULL);
  assert(pool->entities[entity].is_enabled);
  assert(pool->entities[entity].type == type);

  pool->entities[entity].is_enabled = 1;
}

i64 node_init(Pool *pool, Node data) {
  data.index_in_proc = UNDEFINED;

  return pool_add(pool, (Entity) {
    .type = ENTITY_NODE,
    .tail = UNDEFINED,
    .node = data,
  });
}

void node_destroy(Pool *pool, i64 node) {
  pool_remove(pool, node, ENTITY_NODE);
}

i64 node_data_i64(Pool *pool, i64 value) {
  return node_init(pool, (Node) {
    .op      = DATA_I64,
    .lit_int = value,
  });
}

i64 node_ctrl_call(Pool *pool, i16 convention, i64 target_proc, i64 arg_count, Var *args) {
  assert(arg_count <= MAX_ARG_COUNT);

  Call call = {
    .convention  = convention,
    .target_proc = target_proc,
    .arg_count   = arg_count,
  };

  if (arg_count > 0)
    memcpy(call.args, args, arg_count * sizeof *args);

  return node_init(pool, (Node) {
    .op   = CTRL_CALL,
    .call = call,
  });
}

i64 node_ctrl_call_by_name(Pool *pool, i16 convention, i64 name_size, c8 *name, i64 arg_count, Var *args) {
  assert(arg_count <= MAX_ARG_COUNT);

  Call call = {
    .convention       = convention,
    .target_name_size = name_size,
    .arg_count        = arg_count,
  };

  if (name_size > 0)
    memcpy(call.target_name, name, name_size);
  if (arg_count > 0)
    memcpy(call.args, args, arg_count * sizeof *args);

  return node_init(pool, (Node) {
    .op   = CTRL_CALL,
    .call = call,
  });
}

i64 node_ctrl_ret(Pool *pool, i64 value_count, Var *values) {
  assert(value_count <= MAX_ARG_COUNT);

  Ret ret = { .val_count = value_count, };

  if (value_count > 0)
    memcpy(ret.vals, values, value_count * sizeof *values);

  return node_init(pool, (Node) {
    .op  = CTRL_RET,
    .ret = ret,
  });
}

i64 proc_init(Pool *pool) {
  return pool_add(pool, (Entity) {
    .type = ENTITY_PROC,
    .tail = UNDEFINED,
    .proc = (Proc) {
      .ret_index     = UNDEFINED,
      .index_in_unit = UNDEFINED,
    },
  });
}

void proc_destroy(Pool *pool, i64 proc) {
  pool_remove(pool, proc, ENTITY_PROC);
}

void proc_set_convention(Pool *pool, i64 proc, i16 convention) {
  assert(pool != NULL && pool->entities != NULL);
  assert(pool->entities[proc].is_enabled);
  assert(pool->entities[proc].type == ENTITY_PROC);

  pool->entities[proc].proc.convention = convention;
}

void proc_set_name(Pool *pool, i64 proc, i64 name_size, c8 *name) {
  assert(pool != NULL && pool->entities != NULL);
  assert(pool->entities[proc].is_enabled);
  assert(pool->entities[proc].type == ENTITY_PROC);

  //  TODO
  //  Implement large entities.

  assert(name_size <= MAX_NAME_SIZE);
  assert(name_size >= 0);

  Proc *p    = &pool->entities[proc].proc;
  p->name_size = name_size;

  if (name_size > 0)
    memcpy(p->name, name, name_size);
}

void proc_node_add(Pool *pool, i64 proc, i64 node) {
  assert(pool != NULL && pool->entities != NULL);
  assert(pool->entities[proc].is_enabled);
  assert(pool->entities[proc].type == ENTITY_PROC);
  assert(pool->entities[node].is_enabled);
  assert(pool->entities[node].type == ENTITY_NODE);

  Proc *p = &pool->entities[proc].proc;
  Node *n = &pool->entities[node].node;

  assert(n->index_in_proc == UNDEFINED);

  //  TODO
  //  Implement large entities.

  i64 index = p->node_count;

  if (n->op == CTRL_RET)
  {
    //  Only one return node is allowed.
    //

    assert(p->ret_index == UNDEFINED);
    p->ret_index = index;
  }

  assert(index < MAX_NODE_COUNT);

  n->index_in_proc = index;
  p->nodes[index]  = node;
  ++p->node_count;
}

void proc_node_remove(Pool *pool, i64 proc, i64 node) {
  assert(pool != NULL && pool->entities != NULL);
  assert(pool->entities[proc].is_enabled);
  assert(pool->entities[proc].type == ENTITY_PROC);
  assert(pool->entities[node].type == ENTITY_NODE);

  Proc *p = &pool->entities[proc].proc;
  Node *n = &pool->entities[node].node;

  //  TODO
  //  Implement large entities.

  assert(n->index_in_proc != UNDEFINED);
  assert(p->nodes[n->index_in_proc] == node);

  if (n->op == CTRL_RET) {
    assert(p->ret_index != UNDEFINED);
    p->ret_index = UNDEFINED;
  }

  p->nodes[n->index_in_proc] = UNDEFINED;
  n->index_in_proc           = UNDEFINED;
}

i64 unit_init(Pool *pool, i16 type) {
  return pool_add(pool, (Entity) {
    .type = ENTITY_UNIT,
    .tail = UNDEFINED,
    .unit = (Unit) {
      .type              = type,
      .entry_point_index = UNDEFINED,
    }
  });
}

void unit_destroy(Pool *pool, i64 unit) {
  pool_remove(pool, unit, ENTITY_UNIT);
}

void unit_proc_add(Pool *pool, i64 unit, i64 proc) {
  assert(pool != NULL && pool->entities != NULL);
  assert(pool->entities[unit].is_enabled);
  assert(pool->entities[unit].type == ENTITY_UNIT);
  assert(pool->entities[proc].is_enabled);
  assert(pool->entities[proc].type == ENTITY_PROC);

  Unit *u = &pool->entities[unit].unit;
  Proc *p = &pool->entities[proc].proc;

  assert(p->index_in_unit == UNDEFINED);

  //  TODO
  //  Implement large entities.

  i64 index = u->proc_count;

  assert(index < MAX_PROC_COUNT);

  p->index_in_unit = index;
  u->procs[index]  = proc;
  ++u->proc_count;
}

void unit_proc_remove(Pool *pool, i64 unit, i64 proc) {
  assert(pool != NULL && pool->entities != NULL);
  assert(pool->entities[unit].is_enabled);
  assert(pool->entities[unit].type == ENTITY_UNIT);
  assert(pool->entities[proc].type == ENTITY_PROC);

  Unit *u = &pool->entities[unit].unit;
  Proc *p = &pool->entities[proc].proc;

  //  TODO
  //  Implement large entities.  

  assert(p->index_in_unit != UNDEFINED);
  assert(u->procs[p->index_in_unit] == proc);

  if (u->entry_point_index == p->index_in_unit)
    u->entry_point_index = UNDEFINED;

  u->procs[p->index_in_unit] = UNDEFINED;
  p->index_in_unit           = UNDEFINED;
}

void unit_link_add(Pool *pool, i64 unit, i64 link_unit) {
  assert(pool != NULL && pool->entities != NULL);
  assert(pool->entities[unit].is_enabled);
  assert(pool->entities[unit].type == ENTITY_UNIT);
  assert(pool->entities[link_unit].is_enabled);
  assert(pool->entities[link_unit].type == ENTITY_UNIT);

  Unit *u = &pool->entities[unit].unit;

  for (i64 i = 0; i < u->link_count; ++i)
    if (u->links[i] == link_unit)
      return;

  assert(u->link_count < MAX_LINK_COUNT);
  u->links[u->link_count++] = link_unit;
}

void unit_link_remove(Pool *pool, i64 unit, i64 link_unit) {
  assert(pool != NULL && pool->entities != NULL);
  assert(pool->entities[unit].is_enabled);
  assert(pool->entities[unit].type == ENTITY_UNIT);
  assert(pool->entities[link_unit].type == ENTITY_UNIT);

  Unit *u = &pool->entities[unit].unit;

  for (i64 i = 0; i < u->link_count; ++i)
    if (u->links[i] == link_unit) {
      u->links[i] = UNDEFINED;
      return;
    }

  assert(0);
}

void unit_set_name(Pool *pool, i64 unit, i64 name_size, c8 *name) {
  assert(pool != NULL && pool->entities != NULL);
  assert(pool->entities[unit].is_enabled);
  assert(pool->entities[unit].type == ENTITY_UNIT);

  //  TODO
  //  Implement large entities.

  assert(name_size <= MAX_NAME_SIZE);
  assert(name_size >= 0);

  Unit *u    = &pool->entities[unit].unit;
  u->name_size = name_size;

  if (name_size > 0)
    memcpy(u->name, name, name_size);
}

void unit_set_entry_point(Pool *pool, i64 unit, i64 entry_point_proc) {
  assert(pool != NULL && pool->entities != NULL);
  assert(pool->entities[unit].is_enabled);
  assert(pool->entities[unit].type == ENTITY_UNIT);

  Unit *u = &pool->entities[unit].unit;

  if (entry_point_proc == UNDEFINED) {
    u->entry_point_index = UNDEFINED;
    return;
  }

  assert(pool->entities[entry_point_proc].is_enabled);
  assert(pool->entities[entry_point_proc].type == ENTITY_PROC);

  Proc *p = &pool->entities[entry_point_proc].proc;

  assert(p->index_in_unit != UNDEFINED);
  assert(u->procs[p->index_in_unit] == entry_point_proc);

  pool->entities[unit].unit.entry_point_index = p->index_in_unit;
}

//  Code generation proc
//

#include <stdio.h>  // TEMP
#include <stdlib.h> // TEMP

void unit_write(Pool *pool, i64 unit, u16 target, i64 io_out, void *io_user_data) {
  //  Docs
  //
  //  AR  https://man.freebsd.org/cgi/man.cgi?query=ar&sektion=5
  //  ELF https://man7.org/linux/man-pages/man5/elf.5.html
  //

  
  assert(pool != NULL && pool->entities != NULL);
  assert(pool->entities[unit].is_enabled);
  assert(pool->entities[unit].unit.entry_point_index != UNDEFINED);
  assert(target == (FORMAT_ELF | ARCH_X86_64));

  //  Read dependencies
  //
  {
    Unit *u = &pool->entities[unit].unit;

    for (i64 i = 0; i < u->link_count; ++i) {
      if (u->links[i] == UNDEFINED)
        continue;

      i64     index = u->links[i];
      Unit *l     = &pool->entities[index].unit;

      assert(pool->entities[index].is_enabled);
      assert(l->type == UNIT_LIBRARY_STATIC);
      assert(l->name_size > 0 && l->name_size <= MAX_NAME_SIZE);

      i64 f = io_open_read(l->name_size, l->name, io_user_data);

      c8 buf0_[MAX_NAME_SIZE + 1] = { 0 };
      memcpy(buf0_, l->name, l->name_size);
      printf("\nReading `%s` library...\n\n", buf0_);

      i64 n = 0;

      //  Read AR
      //

      u8 magic[8];

      n = io_read(f, sizeof magic, magic, io_user_data); if (n == 0) continue;

      assert(magic[0] == '!');
      assert(magic[1] == '<');
      assert(magic[2] == 'a');
      assert(magic[3] == 'r');
      assert(magic[4] == 'c');
      assert(magic[5] == 'h');
      assert(magic[6] == '>');
      assert(magic[7] == '\n');

      u32 static offsets[10000] = { 0 };
      i64        file_count     = 1;

      for (i64 k = 0;;) {
        c8 id[17]         = { 0 };
        c8 timestamp[13]  = { 0 };
        c8 owner[7]       = { 0 };
        c8 group[7]       = { 0 };
        c8 mode[9]        = { 0 };
        c8 size[11]       = { 0 };
        c8 end[2]         = { 0 };

        n = io_read(f, (sizeof id)        - 1, id,        io_user_data); if (n == 0) break;
        n = io_read(f, (sizeof timestamp) - 1, timestamp, io_user_data); if (n == 0) break;
        n = io_read(f, (sizeof owner)     - 1, owner,     io_user_data); if (n == 0) break;
        n = io_read(f, (sizeof group)     - 1, group,     io_user_data); if (n == 0) break;
        n = io_read(f, (sizeof mode)      - 1, mode,      io_user_data); if (n == 0) break;
        n = io_read(f, (sizeof size)      - 1, size,      io_user_data); if (n == 0) break;
        n = io_read(f,  sizeof end,            end,       io_user_data); if (n == 0) break;

        assert(end[0] == '\x60');
        assert(end[1] == '\x0a');

        if (strcmp(id, "/               ") == 0) {
          //  Symbol table
          //

          u32 count_be;
          n = io_read(f, 4, &count_be, io_user_data); if (n == 0) break;

          file_count =
            (( count_be        & 0xffu) << 24) |
            (((count_be >>  8) & 0xffu) << 16) |
            (((count_be >> 16) & 0xffu) <<  8) |
             ((count_be >> 24) & 0xffu);

          printf("Symbol table - %lld symbols.\n\n", file_count);
          assert(file_count <= (i64) (sizeof offsets / sizeof *offsets));

          for (u32 j = 0; j < file_count; ++j) {
            u32 offset_be;
            n = io_read(f, 4, &offset_be, io_user_data); if (n == 0) break;

            offsets[j] =
              (( offset_be        & 0xffu) << 24) |
              (((offset_be >>  8) & 0xffu) << 16) |
              (((offset_be >> 16) & 0xffu) <<  8) |
               ((offset_be >> 24) & 0xffu);
          }
          if (n == 0) break;

          i64 byte_count = 0;

          for (u32 j = 0; j < file_count; ++j) {
            for (;;) {
              c8 c;
              n = io_read(f, 1, &c, io_user_data); if (n == 0) break;
              ++byte_count;
              if (c == '\0')
                break;
              printf("%c", c);
            }
            if (n == 0) break;
            printf(" ");
          }
          if (n == 0) break;

          printf("\n");

          if ((byte_count & 1) == 1) {
            //  align
            n = io_seek(f, 1, IO_SEEK_CURSOR, io_user_data); if (n == 0) break;
          }
        } else if (strcmp(id, "//              ") == 0) {
          //  String table
          //
          //  Skip file
          //

          i64 byte_count = atoi(size);
          if ((byte_count & 1) == 1)
            ++byte_count; // align

          n = io_seek(f, byte_count, IO_SEEK_CURSOR, io_user_data); if (n == 0) break;
        } else {
          if (strstr(id, "/") != NULL)
            *strstr(id, "/") = '\0';
          if (strstr(size, " ") != NULL)
            *strstr(size, " ") = '\0';
          printf("%08x: %-16s - %5s bytes\n", offsets[k], id, size);

          //  Skip file
          //

          i64 byte_count = atoi(size);
          if ((byte_count & 1) == 1)
            ++byte_count; // align

          n = io_seek(f, byte_count, IO_SEEK_CURSOR, io_user_data); if (n == 0) break;

          if (++k == file_count)
            break;
        }
      }

      io_close(f, io_user_data);
    }
  }

  #define WRITE(x, n)     io_write( io_out, n,                              x,                    io_user_data )
  #define WRITE_V(...)    io_write( io_out, sizeof((u8[]) {__VA_ARGS__}),  (u8[])  {__VA_ARGS__}, io_user_data )
  #define WRITE_DUP(x, n) io_write( io_out, n,                             (u8[n]) {         0 }, io_user_data )
  #define WRITE_2(x)      io_write( io_out, 2,                            &(u16)   {         x }, io_user_data )
  #define WRITE_4(x)      io_write( io_out, 4,                            &(u32)   {         x }, io_user_data )
  #define WRITE_8(x)      io_write( io_out, 8,                            &(u64)   {         x }, io_user_data )

  u16 ehs   = 64;
  u16 shs   = 0;
  u16 phs   = 56;
  u64 align = 8;

  u8 code[16] = {
    0xb8,             // mov rax
    0x3c, 0, 0, 0,    // 60            // exit
    0x48, 0x31, 0xff, // xor rdx, rdx  // rdx = 0
    0x0f, 0x05,       // syscall
  };

  u64 code_offset  = ehs + phs;
  u64 code_size    = sizeof code;
  u64 entry_offset = 0;

  u64 base_address = 0x400000; // x86_64 base address
  u64 code_address = base_address + code_offset;
  u64 entry        = code_address + entry_offset;

  assert((code_offset % align) == 0);
  assert((code_size % align) == 0);

  //  ELF header
  //

  WRITE_V( 0x7f, 'E', 'L', 'F' ); // magic

  WRITE_V( 2 ); // elf64
  WRITE_V( 1 ); // 2's complement, little endian
  WRITE_V( 1 ); // current version
  WRITE_V( 0 ); // ABI = SysV
  WRITE_V( 0 ); // ABI version

  WRITE_DUP(0, 7); // padding

  WRITE_2(      2 ); // executable
  WRITE_2(     62 ); // x86_64
  WRITE_4(      1 ); // current version
  WRITE_8( entry  ); // entry point address
  WRITE_8( ehs    ); // program header offset
  WRITE_8(      0 ); // section header offset
  WRITE_4(      0 ); // flags
  WRITE_2( ehs    ); // ELF header size
  WRITE_2( phs    ); // program header size
  WRITE_2(      1 ); // program header count
  WRITE_2( shs    ); // section header size
  WRITE_2(      0 ); // section header count
  WRITE_2(      0 ); // string table section header index

  //  Program header
  //

  WRITE_4(            1 ); // type   (PT_LOAD)
  WRITE_4(            5 ); // flags  (PF_X | PF_R)
  WRITE_8( code_offset  ); // offset
  WRITE_8( code_address ); // vaddr
  WRITE_8( code_address ); // paddr
  WRITE_8( code_size    ); // filesz
  WRITE_8( code_size    ); // memsz
  WRITE_8(            8 ); // align

  //  Code
  //

  for (i64 i = code_offset - ehs - phs; i > 0; --i)
    WRITE_V( 0 );

  WRITE( code, code_size );

  #undef WRITE_V
  #undef WRITE_DUP
  #undef WRITE_32
  #undef WRITE_64

  #undef WRITE
}

i64 io_open_read(i64 name_size, c8 *name, void *user_data) {
  i64 f;
  io_dispatch(IO_OPEN_READ, &f, &name_size, name, user_data);
  return f;
}

i64 io_open_write(i64 name_size, c8 *name, void *user_data) {
  i64 f;
  io_dispatch(IO_OPEN_WRITE, &f, &name_size, name, user_data);
  return f;
}

void io_close(i64 f, void *user_data) {
  io_dispatch(IO_CLOSE, &f, NULL, NULL, user_data);
}

i64 io_seek(i64 f, i64 offset, u16 origin, void *user_data) {
  io_dispatch(IO_SEEK, &f, &offset, &origin, user_data);
  return offset;
}

i64 io_read(i64 f, i64 size, void *data, void *user_data) {
  io_dispatch(IO_READ, &f, &size, data, user_data);
  return size;
}

i64 io_write(i64 f, i64 size, void *data, void *user_data) {
  io_dispatch(IO_WRITE, &f, &size, data, user_data);
  return size;
}

void io_chmod_exe(i64 f, void *user_data) {
  io_dispatch(IO_CHMOD_EXE, &f, NULL, NULL, user_data);
}

//  ================================================================
//
//    Helpers implementation
//
//  ================================================================

#ifndef DISABLE_HELPERS

#include <stdio.h>

#ifdef __unix__
#include <sys/types.h>
#include <sys/stat.h>
#endif

//  IO dispatch procedure
//

void io_dispatch(i16 op, i64 *id, i64 *size, void *data, void *user_data) {
  assert(id != NULL);

  (void) user_data;

  FILE **f                  = (FILE **) id;
  c8     buf[MAX_NAME_SIZE] = { 0 };

  switch (op) {
    case IO_OPEN_READ:
    case IO_OPEN_WRITE:
      assert(size != NULL);
      assert(*size > 0 && *size < MAX_NAME_SIZE);
      assert(data != NULL);

      memcpy(buf, data, *size);
      *f = fopen(buf, op == IO_OPEN_READ ? "rb" : "wb");
      assert(*f != NULL);
      break;

    case IO_CLOSE:
      assert(*f != NULL);
      assert(size == NULL);
      assert(data == NULL);

      fclose(*f);
      break;

    case IO_SEEK: {
      assert(*f != NULL);
      assert(size != NULL);
      assert(data != NULL);

      u16 *origin = (u16 *) data;
      assert(*origin == IO_SEEK_CURSOR || *origin == IO_SEEK_BEGIN || *origin == IO_SEEK_END);
      i32 s = fseek(*f, *size, *origin == IO_SEEK_CURSOR ? SEEK_CUR :
                               *origin == IO_SEEK_BEGIN  ? SEEK_SET :
                                                           SEEK_END);
      assert(s == 0);
    } break;

    case IO_READ:
      assert(*f != NULL);
      assert(size != NULL);
      assert(data != NULL);
      assert(*size > 0);

      *size = fread(data, 1, *size, *f);
      break;

    case IO_WRITE:
      assert(*f != NULL);
      assert(size != NULL);
      assert(data != NULL);
      assert(*size > 0);

      *size = fwrite(data, 1, *size, *f);
      break;

    case IO_CHMOD_EXE:
      assert(*f != NULL);
      assert(size == NULL);

#ifdef __unix__
      fchmod(fileno(*f), 0775);
#endif
      break;

    default:
      assert(0);
  }
}

//  Global state
//

static Pool g_pool = {
  //  Statically allocate a large memory block.
  //
  //    TODO
  //    Reallocate the memory block when necessary.
  //
  .capacity = MAX_ENTITY_COUNT,
  .entities = (Entity[MAX_ENTITY_COUNT]) { 0 },
};

//  Handy procedures
//

i64 n_i64(i64 value) {
  return node_data_i64(&g_pool, value);
}

i64 n_call(i16 convention, i64 target_proc, i64 arg_count, Var *args) {
  return node_ctrl_call(&g_pool, convention, target_proc, arg_count, args);
}

i64 n_call_by_name(i16 convention, c8 *name, i64 arg_count, Var *args) {
  return node_ctrl_call_by_name(&g_pool, convention, strlen(name), name, arg_count, args);
}

i64 n_ret(i64 val_count, Var *vals) {
  return node_ctrl_ret(&g_pool, val_count, vals);
}

i64 p_new(c8 *name) {
  i64 p = proc_init(&g_pool);
  proc_set_name(&g_pool, p, strlen(name), name);
  return p;
}

void p_add(i64 proc, i64 node) {
  proc_node_add(&g_pool, proc, node);
}

i64 u_new() {
  return unit_init(&g_pool, UNIT_CODE);
}

void u_add(i64 unit, i64 proc) {
  unit_proc_add(&g_pool, unit, proc);
}

void u_entry_point(i64 unit, i64 proc) {
  unit_set_entry_point(&g_pool, unit, proc);
}

void u_elf_x86_64(i64 unit, c8 *output_file_name) {
  printf("Writing ELF x86_64 executable...\n");

  i64 out = io_open_write(strlen(output_file_name), output_file_name, NULL);

  unit_write(&g_pool, unit, FORMAT_ELF | ARCH_X86_64, out, NULL);

  io_chmod_exe(out, NULL);
  io_close(out, NULL);
}

void l_code(i64 unit, i64 link_unit) {
  unit_link_add(&g_pool, unit, link_unit);
}

void l_object(i64 unit, c8 *object_library) {
  i64 l = unit_init(&g_pool, UNIT_LIBRARY_OBJECT);
  unit_set_name(&g_pool, l, strlen(object_library), object_library);
  unit_link_add(&g_pool, unit, l);
}

void l_static(i64 unit, c8 *static_library) {
  i64 l = unit_init(&g_pool, UNIT_LIBRARY_STATIC);
  unit_set_name(&g_pool, l, strlen(static_library), static_library);
  unit_link_add(&g_pool, unit, l);
}

#endif

//  ================================================================
//
//    Example
//
//  ================================================================

#if !defined(DISABLE_HELPERS) && !defined(DISABLE_TESTING)

int main(int argc, char **argv) {
  (void) argc;
  (void) argv;

  printf("node   - %d bytes\n", (i32) sizeof(Node));
  printf("proc   - %d bytes\n", (i32) sizeof(Proc));
  printf("unit   - %d bytes\n", (i32) sizeof(Unit));
  printf("entity - %d bytes\n\n", (i32) sizeof(Entity));

  i64 main = p_new("main");
  i64 n0 = n_i64(42);
  p_add(main, n0);
  p_add(main, n_ret(1, (Var[]) { {.size = 4, .type = TYPE_I32, .node = n0, } }));

  i64 u = u_new();
  u_add(u, main);
  u_entry_point(u, main);
  l_static(u, "/lib/x86_64-linux-gnu/libc.a");
  u_elf_x86_64(u, "test_foo");

  printf("\nBye!\n");
  return 0;
} 

#endif

#endif