readme.md

Example:

$ cc -std=c11 -g miniast.c -o miniast && ./miniast
AST: (28 B of memory)
(mul
  (add
    (int 1)
    (int 2))
  (sub
    (int 8)
    (int 4)))
result: (int 12)
$

miniast.c

// cc -std=c11 miniast.c -o miniast && ./miniast
#include "xcommon.h"
ASSUME_NONNULL_BEGIN

typedef enum AKind {
  AKindInt, // 123
  AKindAdd, // +
  AKindSub, // -
  AKindMul, // *
} AKind;

typedef u16 AOffs;

#define AALIGN alignof(AOffs)

typedef struct AInt {
  u8  kind;
  u8  valClass;
  u16 val; // literal value when valClass == AIntValClass_i16
} AInt;

enum AIntValClass {
  AIntValClass_i16  = 0,
  AIntValClass_i32  = 1,
  AIntValClass_i64  = 2,
  AIntValClass_i128 = 3,
};

typedef struct ABinOp {
  u8    kind;
  u8    _unused;
  AOffs op1;
  //   op2 is always offset 0
} ABinOp;


u8 __attribute__((aligned(AALIGN))) astack_base[1024*1024];
void* astack_top = (void*)astack_base + sizeof(astack_base);


void* AStackAllocBytes(usize nbyte) {
  assert((uintptr)astack_top - nbyte >= (uintptr)astack_base); // else out of memory
  astack_top -= ALIGN2(nbyte, AALIGN);
  return astack_top;
}

#define AStackAlloc(STRUCT_TYPE, KIND) ({ \
  STRUCT_TYPE* n__##__LINE__ = AStackAllocBytes(sizeof(STRUCT_TYPE)); \
  n__##__LINE__->kind = KIND; \
  n__##__LINE__; \
})

usize AStackUsage() {
  return (usize)(((uintptr)astack_base + sizeof(astack_base)) - (uintptr)astack_top);
}

const char* StrOfAKind(AKind kind) {
  switch (kind) {
    case AKindInt: return "int";
    case AKindAdd: return "add";
    case AKindSub: return "sub";
    case AKindMul: return "mul";
  }
  static char tmpbuf[16];
  sprintf(tmpbuf, "?(%u)", kind);
  return tmpbuf;
}

AKind AKindOf(const void* node) { return *(u8*)node; }

// AOffsOfChild returns the offset to child from parent
AOffs AOffsOfChild(const void* parent, usize parent_nbyte, const void* child) {
  assert((uintptr)parent % AALIGN == 0);
  assert(parent_nbyte % AALIGN == 0);
  assert((uintptr)child % AALIGN == 0);
  // astack_base[ ... {parent} {child2} {child1} ]astack_top
  //                         |~~~~~~~~~~|
  //   result is the distance in multiples of AALIGN from child1 to end of parent
  uintptr parent_end = (uintptr)parent + parent_nbyte;
  assert((uintptr)child - parent_end <= U16_MAX); // check for overflow & order
  return ((uintptr)child - parent_end) / AALIGN;
}

const void* ChildOfAOffs(const void* parent, usize parent_nbyte, AOffs child_offs) {
  assert((uintptr)parent % AALIGN == 0);
  assert(parent_nbyte % AALIGN == 0);
  return (parent + parent_nbyte) + ((uintptr)child_offs * AALIGN);
}

#define CHILD(parentp, child_offs) \
  ChildOfAOffs((parentp), sizeof(*(parentp)), child_offs)

AInt* PushAInt16(u16 val) {
  AInt* n = AStackAlloc(AInt, AKindInt);
  n->valClass = AIntValClass_i16;
  n->val = val; assert(val <= U16_MAX);
  return n;
}

ABinOp* PushABinOp(u8 kind, const void* op1, const void* op2) {
  ABinOp* n = AStackAlloc(ABinOp, kind);
  n->op1 = AOffsOfChild(n, sizeof(ABinOp), op1);
  assert(AOffsOfChild(n, sizeof(ABinOp), op2) == 0); // op2 is implicit (adjacent to n)
  return n;
}

void printstr(const char* cstr) { fwrite(cstr, strlen(cstr), 1, stdout); }

void _APrint(const void* n, int maxdepth, int depth) {
  if (depth) printf("\n%*.s", depth*2, "");
  printf("(%s ", StrOfAKind(AKindOf(n)));
  switch (AKindOf(n)) {
    case AKindInt: printf("%u", ((AInt*)n)->val); goto end;
    case AKindAdd:
    case AKindSub:
    case AKindMul: {
      if (depth >= maxdepth) break;
      const ABinOp* binop = n;
      _APrint(CHILD(binop, binop->op1), maxdepth, depth+1);
      putc(' ', stdout);
      _APrint(CHILD(binop, 0), maxdepth, depth+1);
      goto end;
    }
  }
  printstr("…");
end:
  fwrite(")\n", 2 - (int)(depth > 0), 1, stdout);
}

void APrint(const void* n, int maxdepth) {
  return _APrint(n, maxdepth < 0 ? I32_MAX : maxdepth, 0);
}

void* nullable AEval(void* SB, void* SP, const void* n);

u64 AEvalToI64(void* SB, void* SP, const void* n) {
  if (AKindOf(n) == AKindInt) return (u64)((AInt*)n)->val;
  AInt* res = AEval(SB, SP, n);
  assert(AKindOf(res) == AKindInt);
  return (u64)res->val;
}

void* nullable AEval(void* SB, void* SP, const void* n) {
  assert((uintptr)SP % AALIGN == 0);
  //printf("eval [SP %p] ", SP); APrint(n, 1);
  switch (AKindOf(n)) {
    case AKindInt: {
      AInt* res = SP - sizeof(AInt); assert((uintptr)res >= (uintptr)SB);
      memcpy(res, n, sizeof(AInt));
      return res;
    }
    case AKindAdd:
    case AKindSub:
    case AKindMul: {
      const ABinOp* binop = n;
      u64 x, y;
      x = AEvalToI64(SB, SP - sizeof(AInt), CHILD(binop, binop->op1));
      y = AEvalToI64(SB, SP, CHILD(binop, 0));
      if      (AKindOf(n) == AKindAdd) x = x + y;
      else if (AKindOf(n) == AKindSub) x = x - y;
      else if (AKindOf(n) == AKindMul) x = x * y;
      assert(x <= (1<<14)-1); // TODO: valClass
      AInt* res = SP - sizeof(AInt); assert((uintptr)res >= (uintptr)SB);
      res->kind = AKindInt;
      res->val = (u16)x;
      //printf("  res "); APrint(res, -1);
      return res;
    }
  }
  return NULL;
}


int main(int argc, char* argv[]) {
  /*
  ┌───────────────┐         mul
  │ 1 + 2 * 6 - 3 │ ⟶     ╱     ╲
  └───────────────┘     add      sub
                      int int  int int
                       1   2    6   3

  memory representation:
  ┌──────┬───────────────────────┐
  │ u32: │           0           │
  │ u16: │     0     ╷     1     │
  │  u8: │  0  ╷  1  │  2  ╷  3  │
  ├──────┼─────┼─────┼─────┴─────┤
  │      ~     ~     ~           ~
  │ FFE7 │ mul │     │    12     │  12 = operand 1 offset (FFF7)
  ├──────┼─────┼─────┼───────────┤
  │ FFEB │ sub │     │     4     │  4 = operand 1 offset (FFF3)
  │ FFEF │ int │  0  │     3     │  0 = small, 3 = value
  │ FFF3 │ int │  0  │     6     │  0 = small, 6 = value
  ├──────┼─────┼─────┼───────────┤
  │ FFF7 │ add │     │     4     │  4 = operand 1 offset (FFFF)
  │ FFFB │ int │  0  │     2     │  0 = small, 2 = value
  │ FFFF │ int │  0  │     1     │  0 = small, 1 = value
  └──────┴─────┴─────┴───────────┘

  */

  AInt* i_1 = PushAInt16(1);
  AInt* i_2 = PushAInt16(2);
  ABinOp* add = PushABinOp(AKindAdd, i_1, i_2);

  AInt* i_8 = PushAInt16(8);
  AInt* i_4 = PushAInt16(4);
  ABinOp* sub = PushABinOp(AKindSub, i_8, i_4);

  ABinOp* mul = PushABinOp(AKindMul, add, sub);

  printf("AST: (%zu B of memory)\n", AStackUsage());
  APrint(mul, -1);

  u8 __attribute__((aligned(AALIGN))) stack[1024];
  void* res = AEval(stack, stack+sizeof(stack), mul);
  printf("result: "); APrint(res, -1);

  return 0;
}

ASSUME_NONNULL_END

xcommon.h

#pragma once
#define _GNU_SOURCE
#define _POSIX_C_SOURCE 200809L
#include <stdint.h>
#include <stddef.h>
#include <stdbool.h>
#include <stdarg.h>
#include <limits.h>
#include <assert.h>
#include <stdio.h>
#include <errno.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include <fcntl.h>

typedef int8_t    i8;
typedef uint8_t   u8;
typedef int16_t   i16;
typedef uint16_t  u16;
typedef int32_t   i32;
typedef uint32_t  u32;
typedef int64_t   i64;
typedef uint64_t  u64;
typedef size_t    usize;
typedef ssize_t   isize;
typedef intptr_t  intptr;
typedef uintptr_t uintptr;
typedef _Float16  f16;
typedef float     f32;
typedef double    f64;

#define I8_MAX    0x7f
#define I16_MAX   0x7fff
#define I32_MAX   0x7fffffff
#define I64_MAX   0x7fffffffffffffffll
#define ISIZE_MAX __LONG_MAX__

#define I8_MIN    (-0x80)
#define I16_MIN   (-0x8000)
#define I32_MIN   (-0x80000000)
#define I64_MIN   (-0x8000000000000000ll)
#define ISIZE_MIN (-__LONG_MAX__ -1L)

#define U8_MAX    0xff
#define U16_MAX   0xffff
#define U32_MAX   0xffffffff
#define U64_MAX   0xffffffffffffffffllu
#ifdef __SIZE_MAX__
  #define USIZE_MAX __SIZE_MAX__
#else
  #define USIZE_MAX (__LONG_MAX__ *2UL+1UL)
#endif
#ifndef UINTPTR_MAX
  #ifdef __UINTPTR_MAX__
    #define UINTPTR_MAX __UINTPTR_MAX__
  #else
    #define UINTPTR_MAX USIZE_MAX
  #endif
#endif

#ifndef __has_feature
  #define __has_feature(...) 0
#endif

#ifndef nullable
  #if __has_feature(nullability)
    #define nullable _Nullable
  #else
    #define nullable
  #endif
#endif

#if defined(__clang__) && __has_feature(nullability)
  #define ASSUME_NONNULL_BEGIN                                                  \
    _Pragma("clang diagnostic push")                                              \
    _Pragma("clang diagnostic ignored \"-Wnullability-completeness\"")            \
    _Pragma("clang diagnostic ignored \"-Wnullability-inferred-on-nested-type\"") \
    _Pragma("clang assume_nonnull begin")
  #define ASSUME_NONNULL_END      \
    _Pragma("clang diagnostic pop") \
    _Pragma("clang assume_nonnull end")
#else
  #define ASSUME_NONNULL_BEGIN
  #define ASSUME_NONNULL_END
#endif

#ifndef alignof
  // named "_Alignof" in C11 until C23, in C23 it is available as "alignof"
  #define alignof _Alignof
#endif

// T ALIGN2<T>(T n, T w) rounds up n to closest boundary w (w must be a power of two)
#define ALIGN2(n,w) ({ \
  __typeof__(n) w__ = (w); \
  assert((w__ & (w__ - 1)) == 0); /* alignment w is not a power of two */ \
  ((n) + (w__ - 1)) & ~(w__ - 1); \
})