/* build.c - build tool
 *
 * Copyright 2023 Google LLC
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     https://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 * License for the specific language governing permissions and limitations
 * under the License.
 *
 *
 * This is a build tool that uses an implicit build graph by making a LOT of
 * assumptions about your project. If those assumptions aren't true, it has very
 * little flexibility, so unless you structure projects exactly the way I do it
 * probably won't work for you. Sorry!
 *
 * Specifically, it requires that:
 * 1. All test-only code has a basename starting with "t-".
 * 2. All headers are under inc/.
 * 3. All library source files are under src/.
 * 4. All source files should be linked into every binary.
 * 5. All command source files are under cmd/, either:
 *    5a. The source for command foo is cmd/foo.c, or
 *    5b. The source for command foo is every source file in cmd/foo/.
 * 6. Your test runner is a command named "test", and exactly that command
 *    should have all test sources compiled into it.
 * 7. All data files are under etc/.
 * 8. All production data files should be packed into a single archive, named
 *    "prod.arc".
 * 9. All test data files should be packed into a single archive, named
 *    "test.arc".
 * 10. All built objects, binaries, and archives end up in bld/.
 *
 * You can *technically* use it for non-C projects, by setting cc, ld, cflags,
 * and ldflags in the buildfile, as long as whatever those tools are support
 * cc-like -I, -c, and -o options.
 *
 * The buildfile is entirely optional, but if present, it can contain these
 * types of lines:
 *   cc /path/to/cc
 *   ld /path/to/ld
 *   cflags list of cflags
 *   ldflags list of ldflags
 * Every target implicitly depends on the buildfile, if present, so if you
 * change it everything will get rebuilt. If there's no buildfile, this program
 * defaults to using no cflags and no ldflags, with /usr/bin/cc as both cc and
 * ld.
 */

#include <assert.h>
#include <dirent.h>
#include <err.h>
#include <limits.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <sys/wait.h>
#include <time.h>
#include <unistd.h>

/*
 * This tool operates in terms of nodes and edges, like most build tools, but
 * it works backwards from make: it first figures out what initial nodes exist
 * (source files in the tree), then deduces what nodes should be built as a
 * result. There are a series of rules which are applied in order to deduce the
 * set of nodes, which ultimately end up producing final outputs: binaries and
 * archives of data/config/etc.
 *
 * Functionally, the central data structure is a graph, which is built of nodes
 * and edges:
 */

typedef struct Node Node;
typedef enum NodeType NodeType;
typedef struct Edge Edge;
typedef struct Edges Edges;

/* An edge stores both of its ends: */
struct Edge {
	Node *from;
	Node *to;
};

struct Edges {
	Edge *edges;
	size_t num;
	size_t cap;
};

void edges_init(Edges *edges);
void edges_add(Edges *edges, Node *from, Node *to);

/* And a node stores a bunch of build-specific state, and then a list of
 * outgoing edges. Incoming edges aren't stored explicitly anywhere because we
 * don't need them to do builds. */
enum NodeType {
	NT_SOURCE,
	NT_HEADER,
	NT_ETC,
	NT_OBJECT,
	NT_BINARY,
	NT_ARCHIVE,
	NT_CONFIG,
	NT_SYNTHETIC,
};

enum {
	NF_TEST = (1 << 0),
	NF_CMD = (1 << 1),
	NF_DONE = (1 << 2),
	NF_FRESH = (1 << 3),
};

const unsigned int NF_COPYMASK = NF_TEST | NF_CMD;

struct Node {
	/* build-specific state */
	NodeType type;
	char *name;
	unsigned int flags;
	time_t mtime;
	size_t size;

	/* graph state */
	Edges outs;
};

Node *node_make(NodeType type, const char *name);
void node_addout(Node *n, Node *o);
int node_fresh(const Node *n);
int node_ready(const Node *n);

/* Lastly, we have the build graph as a whole: */
typedef struct {
	Node **nodes;
	size_t num;
	size_t cap;
} Graph;

void graph_init(Graph *g);
void graph_add(Graph *g, Node *n);
int graph_has_any(Graph *g, NodeType nt);
Node *graph_nodenamed(Graph *g, const char *name);
size_t graph_findready(Graph *g, Node **ns, size_t nns);
void graph_print(Graph *g, FILE *f);

/* The general approach here is:
 * 1. Initialize the graph with nodes for every file underneath the input
 *    directories.
 * 2. Synthesize object targets for every source file, with edges to every
 *    header file.
 * 3. Synthesize binary targets for every (group of) object targets whose
 *    sources are in the command directory.
 * 4. Synthesize archive targets for every (group of) source targets from
 *    the etc directory.
 * 5. Synthesize an "all" target that depends on every cmd target and
 *    every archive target.
 */

void add_file(Graph *g, const char *path, NodeType t);
void add_files(Graph *g, const char *root, NodeType t);
void syn_objects(Graph *g);
void syn_binaries(Graph *g);
void syn_archives(Graph *g);
void syn_all(Graph *g);

void
graph_infer(Graph *g) {
	graph_init(g);

	add_file(g, "buildfile", NT_CONFIG);

	add_files(g, "cmd", NT_SOURCE);
	add_files(g, "etc", NT_ETC);
	add_files(g, "inc", NT_HEADER);
	add_files(g, "src", NT_SOURCE);

	syn_objects(g);
	syn_binaries(g);
	syn_archives(g);
	syn_all(g);
}

/* Once we have the dependency graph, annotated with mtimes of files on disk,
 * we can build all the object files, then build all the binary and archive
 * files. We need some build configuration to make that work: */

#define N_ARGS 64
#define N_ARGS_BIG 4096

typedef struct {
	char *cc;
	char *ld;
	char *cflags[N_ARGS];
	char *ldflags[N_ARGS];

	char **env;
	bool noisy;
	bool test;
} Buildconf;

void buildconf_init(Buildconf *bc, int argc, char **argv, char **envp);

#define PASS_NODES 64

int subproc(Buildconf *bc, char **argv);
int build_some(Buildconf *bc, Node **nodes, size_t num);

int
graph_build(Graph *g, Buildconf *bc) {
	Node *nodes[PASS_NODES];

	mkdir("bld", 0755);
	mkdir("bld/cmd", 0755);
	mkdir("bld/obj", 0755);

	while (graph_findready(g, nodes, PASS_NODES))
		if (build_some(bc, nodes, PASS_NODES))
			return 1;
	return 0;
}

int
run_tests(Graph *g, Buildconf *bc) {
	char *av[] = { "bld/cmd/test", NULL };

	if (graph_nodenamed(g, av[0]))
		return subproc(bc, av);
	else
		return 0;
}

int
main(int argc, char *argv[], char *envp[]) {
	Graph g;
	graph_infer(&g);
	/* graph_print(&g, stdout); */
	Buildconf bc;
	buildconf_init(&bc, argc, argv, envp);

	int br = graph_build(&g, &bc);
	if (br) {
		fprintf(stderr, "build failed\n");
		return br;
	}

	int tr = run_tests(&g, &bc);
	if (tr) {
		fprintf(stderr, "tests failed\n");
		return tr;
	}

	return 0;
}

/* Less interesting data structure manipulation and such down here: */

void
edges_init(Edges *es) {
	es->cap = 16;
	es->num = 0;
	es->edges = calloc(es->cap, sizeof *es->edges);
}

void
edges_add(Edges *es, Node *from, Node *to) {
	if (es->num == es->cap) {
		es->cap *= 2;
		es->edges = realloc(es->edges, es->cap * sizeof *es->edges);
	}
	es->edges[es->num].from = from;
	es->edges[es->num].to = to;
	es->num++;
}

int
is_test_name(const char *name) {
	const char *p = strrchr(name, '/');
	const char *b = p ? p + 1 : name;
	/* Note the special case hack for cmd/test.* here - that causes the
	 * source file for the test runner to get marked as NF_TEST, which
	 * propagates to the eventual cmd/test */
	return !strncmp(b, "t-", 2) || !strncmp(name, "cmd/test.", 9);
}

int
is_cmd_name(const char *name) {
	return !strncmp(name, "cmd/", 4);
}

time_t
mtimeof(const char *name) {
	struct stat st;
	if (!stat(name, &st))
		return st.st_mtime;
	return 0;
}

time_t
now() {
	return time(NULL);
}

bool
is_input_type(NodeType type) {
	switch (type) {
		case NT_SOURCE:
		case NT_HEADER:
		case NT_ETC:
		case NT_CONFIG:
			return true;
		case NT_OBJECT:
		case NT_BINARY:
		case NT_ARCHIVE:
		case NT_SYNTHETIC:
			return false;
	}
}

Node *
node_make(NodeType type, const char *name) {
	Node *n = malloc(sizeof *n);
	struct stat st;
	n->type = type;
	n->name = strdup(name);
	n->flags = 0;
	if (!stat(name, &st)) {
		n->mtime = st.st_mtime;
		n->size = st.st_size;
	} else {
		n->mtime = n->size = 0;
	}
	if (is_test_name(name))
		n->flags |= NF_TEST;
	if (is_cmd_name(name))
		n->flags |= NF_CMD;
	if (is_input_type(type))
		n->flags |= NF_DONE | NF_FRESH;
	edges_init(&n->outs);
	return n;
}

void
node_addout(Node *n, Node *o) {
	edges_add(&n->outs, n, o);
}

int
node_fresh(const Node *n) {
	for (size_t i = 0; i < n->outs.num; i++) {
		Node *o = n->outs.edges[i].to;
		if (o->mtime > n->mtime)
			return 0;
	}
	return 1;
}

int
node_ready(const Node *n) {
	if (n->flags & (NF_DONE | NF_FRESH))
		return 0;
	for (size_t i = 0; i < n->outs.num; i++) {
		if (!(n->outs.edges[i].to->flags & (NF_DONE | NF_FRESH)))
			return 0;
	}
	return 1;
}

void
graph_init(Graph *g) {
	g->cap = 16;
	g->num = 0;
	g->nodes = calloc(g->cap, sizeof *g->nodes);
}

void
graph_add(Graph *g, Node *n) {
	if (g->num == g->cap) {
		g->cap *= 2;
		g->nodes = realloc(g->nodes, g->cap * sizeof *g->nodes);
	}
	g->nodes[g->num++] = n;
}

int
graph_has_any(Graph *g, NodeType nt) {
	for (size_t i = 0; i < g->num; i++)
		if (g->nodes[i]->type == nt)
			return 1;
	return 0;
}

Node *
graph_nodenamed(Graph *g, const char *name) {
	for (size_t i = 0; i < g->num; i++)
		if (!strcmp(g->nodes[i]->name, name))
			return g->nodes[i];
	return NULL;
}

size_t
graph_findready(Graph *g, Node **ts, size_t nts) {
	size_t ti = 0;
	memset(ts, 0, nts * sizeof(*ts));

	for (size_t i = 0; i < g->num; i++) {
		Node *n = g->nodes[i];
		if (node_fresh(n))
			n->flags |= NF_FRESH;
		else
			n->flags &= ~NF_FRESH;
	}

	for (size_t i = 0; i < g->num; i++) {
		Node *n = g->nodes[i];
		if (node_ready(n))
			ts[ti++] = n;
	}

	return ti;
}

void
add_file(Graph *g, const char *path, NodeType type) {
	graph_add(g, node_make(type, path));
}

void
add_files(Graph *g, const char *root, NodeType type) {
	DIR *d = opendir(root);
	if (!d)
		return;
	struct dirent *de;
	while ((de = readdir(d))) {
		char path[PATH_MAX];
		if (de->d_name[0] == '.')
			continue;

		snprintf(path, sizeof(path), "%s/%s", root, de->d_name);
		if (de->d_type == DT_DIR)
			add_files(g, path, type);
		else if (de->d_type == DT_REG)
			add_file(g, path, type);
	}
	closedir(d);
}

void
extension_to_o(char *buf) {
	char *p = strrchr(buf, '.');
	if (p)
		p[1] = 'o';
}

void
slashes_to_dashes(char *buf) {
	char *p = strrchr(buf, '/');
	while (p) {
		*p = '-';
		p = strrchr(buf, '/');
	}
}

const char *
objname(Node *n) {
	static char buf[NAME_MAX];
	char pbuf[NAME_MAX - 16];

	assert(n->type == NT_SOURCE);

	strncpy(pbuf, n->name, sizeof(pbuf));
	extension_to_o(pbuf);
	slashes_to_dashes(pbuf);

	snprintf(buf, sizeof(buf), "bld/obj/%s", pbuf);

	return buf;
}

void
depend_all(Graph *g, Node *n, NodeType t, unsigned int noflags) {
	for (size_t i = 0; i < g->num; i++) {
		Node *e = g->nodes[i];
		if (e->type != t)
			continue;
		if (!(n->flags & NF_TEST) && (e->flags & NF_TEST))
			continue;
		if (e->flags & noflags)
			continue;
		node_addout(n, e);
	}
}

void
syn_object(Graph *g, Node *s) {
	Node *o = node_make(NT_OBJECT, objname(s));
	o->flags |= s->flags & NF_COPYMASK;
	node_addout(o, s);
	depend_all(g, o, NT_HEADER, 0);
	depend_all(g, o, NT_CONFIG, 0);
	graph_add(g, o);
}

void
syn_objects(Graph *g) {
	size_t num = g->num;
	for (size_t i = 0; i < num; i++) {
		Node *n = g->nodes[i];
		if (n->type == NT_SOURCE)
			syn_object(g, n);
	}
}

char *
ctnameof(Node *n, const char *pre) {
	static char buf[PATH_MAX];
	char *k, *e;

	assert(strstr(n->name, pre) == n->name);
	k = n->name + strlen(pre);

	snprintf(buf, sizeof(buf), "bld/cmd/%s", k);
	e = strchr(buf, '-');
	if (!e)
		e = strchr(buf, '.');
	assert(e);
	*e = 0;

	return buf;
}

void
syn_binary(Graph *g, Node *n) {
	char *ctname = ctnameof(n, "bld/obj/cmd-");
	Node *c;

	assert(ctname);
	c = graph_nodenamed(g, ctname);
	if (c) {
		node_addout(c, n);
	} else {
		c = node_make(NT_BINARY, ctname);
		c->flags = n->flags & NF_COPYMASK;
		node_addout(c, n);
		depend_all(g, c, NT_OBJECT, NF_CMD);
		graph_add(g, c);
	}
}

void
syn_binaries(Graph *g) {
	size_t num = g->num;
	for (size_t i = 0; i < num; i++) {
		Node *n = g->nodes[i];
		if (n->type == NT_OBJECT && n->flags & NF_CMD)
			syn_binary(g, n);
	}
}

void
syn_archives(Graph *g) {
	if (!graph_has_any(g, NT_ETC))
		return;

	Node *np = node_make(NT_ARCHIVE, "bld/prod.arc");
	depend_all(g, np, NT_ETC, NF_TEST);
	graph_add(g, np);

	Node *nt = node_make(NT_ARCHIVE, "bld/test.arc");
	nt->flags |= NF_TEST;
	depend_all(g, nt, NT_ETC, 0);
	graph_add(g, nt);
}

void
syn_all(Graph *g) {
	Node *a = node_make(NT_SYNTHETIC, "(all)");
	depend_all(g, a, NT_BINARY, 0);
	depend_all(g, a, NT_ARCHIVE, 0);
	graph_add(g, a);
}

void
graph_print(Graph *g, FILE *f) {
	for (size_t i = 0; i < g->num; i++) {
		Node *n = g->nodes[i];
		fprintf(f, "%d %s (%zu out) %08x %lu\n", n->type, n->name,
		        n->outs.num, n->flags, n->mtime);
		for (size_t en = 0; en < n->outs.num; en++) {
			Node *o = n->outs.edges[en].to;
			fprintf(f, "    -> %d %s\n", o->type, o->name);
		}
	}
}

int
subproc(Buildconf *bc, char **argv) {
	if (bc->noisy) {
		for (size_t i = 0; argv[i]; i++)
			printf("%s ", argv[i]);
		printf("\n");
	}

	pid_t p = fork();
	int status;
	if (p < 0) {
		err(1, "fork()");
	} else if (p > 0 && wait(&status)) {
		return status;
	} else {
		if (execve(argv[0], argv, bc->env))
			err(2, "exec()");
	}
	return -1;
}

size_t
push_flags(char **argv, size_t i, size_t n, char **fl) {
	for (size_t j = 0; fl[j] && i + j < n; j++)
		argv[i++] = fl[j];
	return i;
}

size_t
push_outs(char **argv, size_t i, size_t n, Node *t, NodeType nt) {
	for (size_t j = 0; j < t->outs.num && i < n; j++) {
		Node *o = t->outs.edges[j].to;
		if (o->type == nt)
			argv[i++] = o->name;
	}
	return i;
}

int
compile(Buildconf *bc, Node *t) {
	char *argv[N_ARGS_BIG];
	size_t i;
	argv[0] = bc->cc;
	i = push_flags(argv, 1, N_ARGS_BIG, bc->cflags);
	argv[i++] = t->name;
	i = push_outs(argv, i, N_ARGS_BIG, t, NT_SOURCE);
	argv[i] = 0;

	return subproc(bc, argv);
}

int
linkbin(Buildconf *bc, Node *t) {
	char *argv[N_ARGS_BIG];
	size_t i;
	argv[0] = bc->ld;
	i = push_flags(argv, 1, N_ARGS_BIG, bc->ldflags);
	argv[i++] = t->name;
	i = push_outs(argv, i, N_ARGS_BIG, t, NT_OBJECT);
	argv[i] = 0;

	return subproc(bc, argv);
}

bool is_little_endian() {
	static const uint16_t d = 1;
	static const uint8_t *p = (uint8_t *)&d;
	return *p == 1;
}

uint16_t tobe16(uint16_t t) {
	if (is_little_endian())
		return ((t >> 8) & 0xff) | ((t << 8) & 0xff00);
	else
		return t;
}

uint32_t tobe32(uint32_t t) {
	if (is_little_endian()) {
		return ((t >> 24) & 0xff) |
		       ((t >> 8) & 0xff00) |
		       ((t << 8) & 0xff0000) |
		       ((t << 24) & 0xff000000);
	} else {
		return t;
	}
}

#define ARC_FHDRLEN 8
#define ARC_EHDRLEN 64

void
arc_writefileheader(FILE *f, uint32_t nents) {
	uint32_t mag = tobe32(('A' << 24) | ('R' << 16) | ('C' << 8));
	uint16_t flags = 0;
	uint16_t ne = tobe16(nents);
	fwrite(&mag, sizeof(mag), 1, f);
	fwrite(&flags, sizeof(flags), 1, f);
	fwrite(&ne, sizeof(ne), 1, f);
}

void
arc_writeentryheader(FILE *f, Node *t, uint32_t o) {
	char nb[54];
	uint16_t flags = 0;
	uint32_t len = tobe32(t->size), off = tobe32(o);
	char *p = strchr(t->name, '/');
	if (strlen(p) >= sizeof(nb))
		warnx("arc: name '%s' too long (max %zu)", p, sizeof(nb));
	assert(p);
	memset(nb, 0, sizeof(nb));
	strncpy(nb, p + 1, sizeof(nb));
	fwrite(&flags, sizeof(flags), 1, f);
	fwrite(nb, sizeof(nb), 1, f);
	fwrite(&off, sizeof(off), 1, f);
	fwrite(&len, sizeof(len), 1, f);
}

void
arc_writeentrybody(FILE *f, Node *t) {
	FILE *q = fopen(t->name, "r");
	char buf[4096];
	size_t s;
	if (!q)
		err(1, "fopen(%s)", t->name);
	while ((s = fread(buf, 1, sizeof(buf), q)))
		fwrite(buf, s, 1, f);
	fclose(q);
}

int
archive(Buildconf *bc, Node *t) {
	FILE *f = fopen(t->name, "w");
	uint32_t hdrsz = ARC_FHDRLEN + ARC_EHDRLEN * t->outs.num;
	uint32_t off = hdrsz;

	if (bc->noisy)
		printf("arc %s\n", t->name);

	if (!f)
		err(1, "fopen(%s)", t->name);

	arc_writefileheader(f, t->outs.num);

	for (size_t i = 0; i < t->outs.num; i++) {
		Node *o = t->outs.edges[i].to;
		arc_writeentryheader(f, o, off);
		off += o->size;
	}

	for (size_t i = 0; i < t->outs.num; i++) {
		Node *o = t->outs.edges[i].to;
		arc_writeentrybody(f, o);
	}

	fclose(f);
	return 0;
}

int
build_one(Buildconf *bc, Node *t) {
	switch (t->type) {
		case NT_SOURCE:
		case NT_HEADER:
		case NT_ETC:
		case NT_CONFIG:
			assert(0);
			return 0;
		case NT_SYNTHETIC:
			return 0;
		case NT_OBJECT:
			return compile(bc, t);
		case NT_BINARY:
			return linkbin(bc, t);
		case NT_ARCHIVE:
			return archive(bc, t);
	}
	return 1;
}

int
build_some(Buildconf *bc, Node **ts, size_t nts) {
	for (size_t i = 0; i < nts && ts[i]; i++) {
		assert(!(ts[i]->flags & NF_DONE));
		if (build_one(bc, ts[i]))
			return 1;
		ts[i]->mtime = now();
		ts[i]->flags |= NF_DONE;
	}
	return 0;
}

void
flag_push(char **flags, size_t n, const char *f) {
	size_t i;
	for (i = 0; flags[i] && i < n; i++)
		if (!flags[i])
			break;
	if (i < n)
		flags[i] = strdup(f);
	else
		errx(1, "flag overflow: '%s'\n", f);
}

void
flag_push_many(char **flags, size_t n, const char *f) {
	char c[4096];
	char *p;
	strncpy(c, f, sizeof(c));
	p = strtok(c, " ");
	while (p) {
		flag_push(flags, n, p);
		p = strtok(NULL, " ");
	}
}

void
buildconf_loadfile(Buildconf *bc, const char *fn) {
	FILE *f = fopen(fn, "r");
	char line[512];
	if (!f)
		return;
	while (fgets(line, sizeof(line), f)) {
		char *k, *v;
		if (strchr(line, '\n'))
			*strchr(line, '\n') = 0;
		if (!line[0] || line[0] == '#')
			continue;
		k = strtok(line, " ");
		v = strtok(NULL, "");
		if (!strcmp(k, "cc"))
			bc->cc = strdup(v);
		else if (!strcmp(k, "ld"))
			bc->ld = strdup(v);
		else if (!strcmp(k, "cflags"))
			flag_push_many(bc->cflags, N_ARGS, v);
		else if (!strcmp(k, "ldflags"))
			flag_push_many(bc->ldflags, N_ARGS, v);
		else
			warnx("buildfile: what is '%s'", k);
	}
	fclose(f);
}

void
buildconf_init(Buildconf *bc, int argc, char **argv, char **envp) {
	bc->cc = NULL;
	bc->ld = NULL;
	memset(bc->cflags, 0, sizeof(bc->cflags));
	memset(bc->ldflags, 0, sizeof(bc->ldflags));
	bc->env = envp;
	bc->noisy = false;

	for (int i = 1; i < argc; i++) {
		if (!strcmp(argv[i], "-v"))
			bc->noisy = true;
	}

	buildconf_loadfile(bc, "buildfile");
	if (!bc->cc)
		bc->cc = "/usr/bin/cc";
	if (!bc->ld)
		bc->ld = "/usr/bin/cc";

	flag_push(bc->cflags, N_ARGS, "-Iinc");
	flag_push(bc->cflags, N_ARGS, "-c");
	flag_push(bc->cflags, N_ARGS, "-o");

	flag_push(bc->ldflags, N_ARGS, "-o");
}