/* Building tables at run time, in five steps: register, fill, verify, seal, use.
   The kinds arrive as data (as a plugin list would), not as `static const` tables.
   Filling goes defaults -> parent -> own slots, so a kind names only what differs.
   Sealing makes the page that holds the tables read-only (POSIX mprotect).
   Run with --write-after-seal to try to change a slot afterwards. */
#define _DEFAULT_SOURCE        /* MAP_ANONYMOUS: Linux and the BSDs, POSIX 2024 */
#include <stdio.h>
#include <string.h>
#include <sys/mman.h>
#include <unistd.h>

struct stream;
typedef int (*slot)(struct stream *);
enum { WRITE, FLUSH, CLOSE, SLOTS };
static const char *const slot_names[SLOTS] = { "write", "flush", "close" };
struct stream_ops { slot s[SLOTS]; };
struct stream { const struct stream_ops *ops; const char *kind; };

/* behaviours --- each just says who it is */
#define SAY(fn) static int fn(struct stream *st) { (void)st; return 0; }
SAY(stream_flush_nothing) SAY(stream_close) SAY(file_write) SAY(file_flush)
SAY(gzip_write) SAY(gzip_close) SAY(memory_write)
static const struct { slot fn; const char *name; } fn_names[] = {
    { stream_flush_nothing, "stream_flush_nothing" }, { stream_close, "stream_close" },
    { file_write, "file_write" }, { file_flush, "file_flush" },
    { gzip_write, "gzip_write" }, { gzip_close, "gzip_close" },
    { memory_write, "memory_write" },
};
static const char *name_of(slot f)
{
    for (size_t i = 0; i < sizeof fn_names / sizeof fn_names[0]; i++)
        if (fn_names[i].fn == f) return fn_names[i].name;
    return "(empty)";
}

/* 1. register: what a plugin list might say --- name, parent, own slots */
struct kind_desc { const char *name, *parent; bool abstract; slot own[SLOTS]; };
static const struct kind_desc descs[] = {
    { "gzip-file", "file",   false, { [WRITE] = gzip_write, [CLOSE] = gzip_close } },
    { "file",      "stream", false, { [WRITE] = file_write, [FLUSH] = file_flush } },
    { "memory",    "stream", false, { [WRITE] = memory_write } },
    { "broken",    "stream", false, { [CLOSE] = gzip_close } },       /* forgot write */
    { "stream",    nullptr,  true,
      { [FLUSH] = stream_flush_nothing, [CLOSE] = stream_close } },
};
#define KINDS (sizeof descs / sizeof descs[0])

static struct stream_ops *tables;       /* lives in its own page, so it can be sealed */
static bool built[KINDS], published[KINDS];
static size_t page;

static int find(const char *name)
{
    for (size_t i = 0; i < KINDS; i++)
        if (strcmp(descs[i].name, name) == 0) return (int)i;
    return -1;
}

/* 2. fill: the parent first (recursively), then copy it, then this kind's own slots */
static bool fill(int k, int depth)
{
    if (built[k]) return true;
    if (depth > (int)KINDS) return false;               /* a cycle in the parents */
    struct stream_ops t = {};
    if (descs[k].parent) {
        int p = find(descs[k].parent);
        if (p < 0 || !fill(p, depth + 1)) return false;
        t = tables[p];
    }
    for (int s = 0; s < SLOTS; s++)
        if (descs[k].own[s]) t.s[s] = descs[k].own[s];
    tables[k] = t;
    built[k] = true;
    return true;
}

int main(int argc, char **argv)
{
    bool attack = argc > 1 && strcmp(argv[1], "--write-after-seal") == 0;
    long ps = sysconf(_SC_PAGESIZE);
    page = ps > 0 ? (size_t)ps : 4096;
    if (KINDS * sizeof *tables > page) { puts("too many tables for a page"); return 1; }
    tables = mmap(nullptr, page, PROT_READ | PROT_WRITE,
                  MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (tables == MAP_FAILED) { puts("mmap failed"); return 1; }

    for (int k = 0; k < (int)KINDS; k++)
        if (!fill(k, 0)) { printf("cannot build %s\n", descs[k].name); return 1; }
    puts("built (defaults -> parent -> own slots):");
    for (size_t k = 0; k < KINDS; k++) {
        printf("  %-10s", descs[k].name);
        for (int s = 0; s < SLOTS; s++)
            printf(s + 1 < SLOTS ? " %s=%-20s" : " %s=%s",
                   slot_names[s], name_of(tables[k].s[s]));
        puts(descs[k].abstract ? "  (abstract)" : "");
    }

    /* 3. verify: a kind with an empty slot is not published, an abstract one never */
    for (size_t k = 0; k < KINDS; k++) {
        published[k] = !descs[k].abstract;
        for (int s = 0; s < SLOTS && published[k]; s++)
            if (!tables[k].s[s]) {
                printf("verify: %s has no %s --- not published\n",
                       descs[k].name, slot_names[s]);
                published[k] = false;
            }
    }

    /* 4. seal: from here on the tables are only read */
    if (mprotect(tables, page, PROT_READ) != 0) { puts("mprotect failed"); return 1; }
    const struct stream_ops *sealed = tables;
    puts("sealed: the page holding the tables is read-only");

    /* 5. use */
    for (size_t k = 0; k < KINDS; k++) {
        if (!published[k]) continue;
        struct stream st = { &sealed[k], descs[k].name };
        int r = st.ops->s[WRITE](&st) | st.ops->s[FLUSH](&st) | st.ops->s[CLOSE](&st);
        printf("use: a %s stream wrote, flushed and closed%s\n",
               st.kind, r ? " (error)" : "");
    }

    if (attack) {
        puts("now overwriting gzip-file's write slot...");
        fflush(stdout);
        tables[find("gzip-file")].s[WRITE] = memory_write;   /* read-only page */
        puts("the write went through");
    }
    munmap(tables, page);
    return 0;
}

/* Build once, publish once: eight threads ask for the tables at the same moment.
   call_once runs the builder exactly once, and every caller returns only after it
   has finished --- so no thread can see a half-filled table. */
#include <stdatomic.h>
#include <stdio.h>
#include <threads.h>

struct ops { int (*area)(int); int (*perimeter)(int); };
static int sq_area(int s) { return s * s; }
static int sq_perimeter(int s) { return 4 * s; }

static struct ops table;                /* filled at run time, then only read */
static once_flag table_once = ONCE_FLAG_INIT;
static atomic_int builds;

static void build(void)
{
    atomic_fetch_add(&builds, 1);
    table.area = sq_area;
    thrd_sleep(&(struct timespec){ .tv_nsec = 20'000'000 }, nullptr);  /* a slow build */
    table.perimeter = sq_perimeter;
}
static const struct ops *get_table(void)
{
    call_once(&table_once, build);
    return &table;
}

enum { THREADS = 8 };
static const struct ops *seen[THREADS];
static int answer[THREADS];
static int worker(void *arg)
{
    int i = *(int *)arg;
    seen[i] = get_table();
    answer[i] = seen[i]->area(3) + seen[i]->perimeter(3);  /* both slots are there */
    return 0;
}

int main(void)
{
    thrd_t t[THREADS];
    int id[THREADS];
    for (int i = 0; i < THREADS; i++) {
        id[i] = i;
        if (thrd_create(&t[i], worker, &id[i]) != thrd_success) {
            puts("thrd_create failed");
            return 1;
        }
    }
    for (int i = 0; i < THREADS; i++) thrd_join(t[i], nullptr);

    bool same = true, right = true;
    for (int i = 0; i < THREADS; i++) {
        same = same && seen[i] == seen[0];
        right = right && answer[i] == 9 + 12;
    }
    printf("%d threads asked; the builder ran %d time(s)\n",
           THREADS, atomic_load(&builds));
    printf("every thread got the same table: %s\n", same ? "yes" : "no");
    printf("every answer was area 9 + perimeter 12 = 21, both slots filled: %s\n",
           right ? "yes" : "no");
    return 0;
}

/* Fat pointers: a pointer to the data and a pointer to the table, carried together.
   The table lives outside the object, so an interface can be attached to types we
   cannot change --- here the standard library's struct tm and a plain double.
   The object pays nothing; every pointer to it is twice as wide. */
#include <stdio.h>
#include <time.h>

struct printable_ops { void (*print)(const void *self); const char *type; };
struct printable { const void *self; const struct printable_ops *ops; };   /* fat */

static void print_tm(const void *self)
{
    const struct tm *t = self;
    printf("%04d-%02d-%02d", t->tm_year + 1900, t->tm_mon + 1, t->tm_mday);
}
static void print_double(const void *self) { printf("%.3f", *(const double *)self); }

/* the "vptr" way, for comparison: the table pointer is inside the object */
struct point_ops;
struct point { const struct point_ops *ops; double x, y; };
struct point_ops { void (*print)(const struct point *); };
static void print_point(const struct point *p) { printf("(%g, %g)", p->x, p->y); }
static const struct point_ops point_ops = { print_point };
static void print_point_any(const void *self) { print_point(self); }

static const struct printable_ops tm_printable     = { print_tm, "struct tm" };
static const struct printable_ops double_printable = { print_double, "double" };
static const struct printable_ops point_printable  = { print_point_any, "struct point" };

static void print_all(const struct printable *xs, size_t n)
{
    for (size_t i = 0; i < n; i++) {
        printf("  %-13s ", xs[i].ops->type);
        xs[i].ops->print(xs[i].self);
        putchar('\n');
    }
}

int main(void)
{
    struct tm day = { .tm_year = 2026 - 1900, .tm_mon = 10, .tm_mday = 6 };
    double ratio = 1.618;
    struct point p = { &point_ops, 3, 4 };

    struct printable xs[] = {
        { &day, &tm_printable }, { &ratio, &double_printable }, { &p, &point_printable },
    };
    puts("one interface, three types --- two of them never heard of it:");
    print_all(xs, sizeof xs / sizeof xs[0]);

    printf("sizeof(struct tm) %zu, unchanged; sizeof(double) %zu, unchanged\n",
           sizeof day, sizeof ratio);
    printf("sizeof(struct point) %zu --- it carries its own table pointer\n", sizeof p);
    printf("a plain pointer %zu bytes, a fat pointer %zu bytes\n",
           sizeof(void *), sizeof(struct printable));
    return 0;
}

/* One table per (interface, concrete type) pair, built at run time on first use and
   kept in a hash table --- the idea of Go's itab, in C.
   A type only lists its methods by name; it never says which interfaces it satisfies.
   A failed match is cached too, so asking again costs a lookup, not a rebuild. */
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef double (*fn)(const void *self);
struct method { const char *name; fn f; };
struct type  { const char *name; const struct method *methods; size_t n; };
struct iface { const char *name; const char *const *wants; size_t n; };
struct itab  { const struct iface *in; const struct type *ty; bool ok; fn fun[4]; };

/* ---- the cache: open addressing, keyed by the pair of pointers ---- */
enum { SLOTS = 64 };
static struct itab *cache[SLOTS];
static unsigned builds, hits;

static size_t hash(const struct iface *in, const struct type *ty)
{
    uintptr_t h = (uintptr_t)in * 31 ^ (uintptr_t)ty;
    return (size_t)(h ^ h >> 7) % SLOTS;
}
static struct itab *build(const struct iface *in, const struct type *ty)
{
    struct itab *t = calloc(1, sizeof *t);
    if (!t) return nullptr;
    *t = (struct itab){ in, ty, true, {} };
    builds++;
    for (size_t w = 0; w < in->n && w < 4; w++) {          /* match by name, in order */
        fn found = nullptr;
        for (size_t m = 0; m < ty->n; m++)
            if (strcmp(ty->methods[m].name, in->wants[w]) == 0) found = ty->methods[m].f;
        if (!found) { t->ok = false; break; }
        t->fun[w] = found;
    }
    return t;
}
static const struct itab *get_itab(const struct iface *in, const struct type *ty)
{
    size_t i = hash(in, ty);
    for (size_t probes = 0; probes < SLOTS; probes++, i = (i + 1) % SLOTS) {
        if (!cache[i]) return cache[i] = build(in, ty);   /* first time: build, keep */
        if (cache[i]->in == in && cache[i]->ty == ty) { hits++; return cache[i]; }
    }
    return nullptr;                                         /* cache full */
}

/* ---- types that know nothing about interfaces ---- */
struct circle { double r; };
struct label  { const char *text; };
static double circle_area(const void *s)
{ const struct circle *c = s; return 3.0 * c->r * c->r; }
static double circle_perimeter(const void *s)
{ const struct circle *c = s; return 6.0 * c->r; }
static double label_length(const void *s)
{ const struct label *l = s; return (double)strlen(l->text); }

static const struct method circle_m[] = {
    { "area", circle_area }, { "perimeter", circle_perimeter },
};
static const struct method label_m[]  = { { "length", label_length } };
static const struct type circle_t = { "circle", circle_m, 2 };
static const struct type label_t  = { "label", label_m, 1 };

static const char *const shape_wants[] = { "area", "perimeter" };
static const struct iface shape_i = { "Shape", shape_wants, 2 };

/* an interface value: the itab plus the data --- a fat pointer */
struct shape_value { const struct itab *tab; const void *data; };
static bool as_shape(const struct type *ty, const void *data, struct shape_value *out)
{
    const struct itab *t = get_itab(&shape_i, ty);
    if (!t || !t->ok) return false;
    *out = (struct shape_value){ t, data };
    return true;
}

int main(void)
{
    struct circle cs[] = { { 1 }, { 2 }, { 0.5 } };
    struct label lb = { "hello" };
    for (size_t i = 0; i < 3; i++) {
        struct shape_value v;
        if (as_shape(&circle_t, &cs[i], &v))
            printf("circle %.1f as Shape: area %.2f, perimeter %.2f\n",
                   cs[i].r, v.tab->fun[0](v.data), v.tab->fun[1](v.data));
    }
    for (int i = 0; i < 2; i++) {
        struct shape_value v;
        bool ok = as_shape(&label_t, &lb, &v);
        printf("label as Shape: %s\n", ok ? "yes" : "no --- it has no area");
    }
    printf("tables built %u (one per pair, the failure too), cache hits %u\n",
           builds, hits);
    for (size_t i = 0; i < SLOTS; i++) free(cache[i]);
    return 0;
}

/* Dispatch by name (selector) --- the Smalltalk and Objective-C way, in C.
   1. A message name is interned once and becomes an integer selector.
   2. The class's method list is scanned; if the method is not there, the parent's.
   3. What is found goes into a per-class cache; next time the cache answers.
   4. If nothing is found, the "does not understand" handler gets it (forwarding).
   5. Adding a method at run time bumps an epoch, which throws away every cache. */
#include <stdio.h>
#include <string.h>

#define MAX_SELECTORS 32
#define MAX_METHODS   8
#define CACHE_SLOTS   8

struct object;
typedef double (*imp)(struct object *self);

struct method { unsigned sel; imp fn; };
struct cache_slot { unsigned sel; imp fn; unsigned epoch; };
struct class {
    const char *name;
    struct class *parent;
    struct method methods[MAX_METHODS];
    unsigned n_methods;
    struct cache_slot cache[CACHE_SLOTS];
};
struct object { struct class *isa; double size; };

/* ---- interning selectors ---- */
static const char *selector_names[MAX_SELECTORS];
static unsigned n_selectors;
static unsigned intern(const char *name)
{
    for (unsigned i = 0; i < n_selectors; i++)
        if (strcmp(selector_names[i], name) == 0) return i + 1;
    if (n_selectors == MAX_SELECTORS) return 0;
    selector_names[n_selectors++] = name;
    return n_selectors;                       /* 0 is kept for "no selector" */
}

/* ---- lookup ---- */
static unsigned epoch = 1;                    /* goes up whenever methods change */
static unsigned slow_lookups, cache_hits;

static imp lookup_slow(const struct class *c, unsigned sel)
{
    slow_lookups++;
    for (; c; c = c->parent)
        for (unsigned i = 0; i < c->n_methods; i++)
            if (c->methods[i].sel == sel) return c->methods[i].fn;
    return nullptr;
}
static imp lookup(struct class *c, unsigned sel)
{
    struct cache_slot *slot = &c->cache[sel % CACHE_SLOTS];
    if (slot->sel == sel && slot->epoch == epoch) { cache_hits++; return slot->fn; }
    imp fn = lookup_slow(c, sel);
    *slot = (struct cache_slot){ sel, fn, epoch };     /* "not found" is cached too */
    return fn;
}
static bool add_method(struct class *c, const char *name, imp fn)
{
    if (c->n_methods == MAX_METHODS) return false;
    c->methods[c->n_methods++] = (struct method){ intern(name), fn };
    epoch++;                                  /* every class's cache is stale at once */
    return true;
}

/* ---- sending ---- */
static double does_not_understand(struct object *self, unsigned sel)
{
    printf("  %s does not understand '%s'\n", self->isa->name,
           sel ? selector_names[sel - 1] : "(selector table full)");
    return 0;
}
static double send(struct object *self, const char *message)
{
    unsigned sel = intern(message);
    imp fn = sel ? lookup(self->isa, sel) : nullptr;
    return fn ? fn(self) : does_not_understand(self, sel);
}

/* ---- the classes ---- */
static double shape_describe(struct object *self)
{ printf("  a %s of size %g\n", self->isa->name, self->size); return 0; }
static double circle_area(struct object *self) { return 3.0 * self->size * self->size; }
static double square_area(struct object *self) { return self->size * self->size; }
static double shape_perimeter(struct object *self) { return 4.0 * self->size; }

static struct class shape  = { .name = "Shape" };
static struct class circle = { .name = "Circle", .parent = &shape };
static struct class square = { .name = "Square", .parent = &shape };

int main(void)
{
    add_method(&shape, "describe", shape_describe);
    add_method(&circle, "area", circle_area);
    add_method(&square, "area", square_area);

    struct object things[] = { { &circle, 2 }, { &square, 3 }, { &circle, 1 } };
    puts("send 'describe' (inherited) and 'area' (own) to each:");
    for (size_t i = 0; i < sizeof things / sizeof things[0]; i++) {
        send(&things[i], "describe");
        printf("  area = %g\n", send(&things[i], "area"));
    }
    printf("slow lookups %u, cache hits %u\n\n", slow_lookups, cache_hits);

    puts("send 'perimeter', which nobody defines yet:");
    send(&things[0], "perimeter");
    send(&things[0], "perimeter");            /* "not found" comes from the cache too */
    printf("slow lookups %u, cache hits %u\n\n", slow_lookups, cache_hits);

    puts("add 'perimeter' to Shape at run time, then send again:");
    add_method(&shape, "perimeter", shape_perimeter);
    printf("  perimeter = %g\n", send(&things[0], "perimeter"));
    printf("  perimeter = %g\n", send(&things[1], "perimeter"));
    printf("slow lookups %u, cache hits %u\n", slow_lookups, cache_hits);
    return 0;
}