/*
 * This file is part of musl-mod: modified version of Musl libc library.
 * musl-mod in general and this file specifically are available under
 * MIT license. See COPYRIGHT file.
 *
 * Limited make to build musl. Implements just enough to handle Makefile.
 */

#include "common.h"

enum {
	path_max_len = 4096,
	buf_size = 1024 * 1024,
	buf_static_size = 512,
	hash_table_size = 16 * 1024,
	pat_rules_limit = 16,
	find_body_max_depth = 2,
	file_stack_size = 8
};

const char *debug_prx = ">>> ";

struct pos {
	char *fname;
	int line;
};

struct line {
	struct str str;
	struct pos pos;
};

struct buf {
	char *start;
	char *end;
	char *cur;
};

struct strbuf {
	struct str *buf;
	int len;
	int size;
};

struct cmdbuf {
	struct line *buf;
	int len;
	int size;
};

struct rule_body {
	struct strbuf prereqs;
	int normal_prereq_count;
	struct pos pos;

	struct cmdbuf *recipes;
};

struct full_rule {
	struct str *target;
	struct rule_body *rest;
};

struct rule_details {
	struct rule_body *body;
	struct strbuf targets;
	int patrule;
	struct pos *pos;
};

enum {
	vs_makefile,
	vs_cmdargs
};

struct vt_cell {
	struct str vname;
	struct str value;
	char scope;
};

struct vtable {
	struct vt_cell *buf;
	int cells_occupied;
};

struct rule_cell {
	struct str *target;
	struct rule_body *body;
};

struct rtable {
	struct rule_cell *buf;
	int cells_occupied;
};

struct file {
	char *name;
	char *buf;
	int line;
};

struct file_stack {
	struct file buf[file_stack_size];
	int idx;
};

struct world {
	struct file_stack fstack;
	struct str target;
	char **envp;

	int debug_mode;

	struct full_rule pat_rules[pat_rules_limit];
	int pat_rule_num;

	struct vtable vtable;
	struct rtable rtable;
};

struct eval_aux {
	int level;
	struct pos *pos;
	struct full_rule *rule;

	struct buf *mainbuf;
	struct buf *auxbuf;
	struct world *world;
};

static void errorp(struct pos *pos, char *str, ...)
{
	va_list vl;

	eprintf("%s:%d: ", pos->fname, pos->line);

	va_start(vl, str);
	evprintf(str, vl);

	print_strz(&stderr, "\n");
	va_end(vl);
	exit(1);
}

static void strdup(struct str *dest, struct str *src, int with_zero)
{
	int slen = src->end - src->start;
	int len = slen + (with_zero ? 1 : 0);
	dest->start = malloc(len);
	dest->end = dest->start + slen;

	memcpy(dest->start, src->start, slen);
	if (with_zero)
		dest->start[slen] = 0;
}

#define HASHTABLE_INIT(type) \
static void type ## _init(struct type *t) \
{ \
	t->buf = malloc(hash_table_size * sizeof(*t->buf)); \
	t->cells_occupied = 0; \
	memset(t->buf, 0, hash_table_size * sizeof(*t->buf)); \
}

HASHTABLE_INIT(vtable)
HASHTABLE_INIT(rtable)

/* FNV-1a */
static unsigned int calc_hash(struct str *str)
{
	char *tmp;
	unsigned int h = 2166136261;
	for (tmp = str->start; tmp != str->end; ++tmp) {
		h = h ^ *tmp;
		h *= 16777619;
	}
	return h;
}

static struct rule_cell *rtable_getcell(struct rtable *t, struct str *key)
{
	unsigned hash = calc_hash(key);
	int i = hash & (hash_table_size - 1);
	for (;;) {
		if (t->buf[i].target == NULL)
			break;
		else if (streq(key, t->buf[i].target))
			break;
		i = (i + 1) & (hash_table_size - 1);
	}
	return t->buf + i;
}

static struct vt_cell *vtable_getcell(struct vtable *t, struct str *key)
{
	unsigned hash = calc_hash(key);
	int i = hash & (hash_table_size - 1);
	for (;;) {
		if (t->buf[i].vname.start == NULL)
			break;
		else if (streq(key, &t->buf[i].vname))
			break;
		i = (i + 1) & (hash_table_size - 1);
	}
	return t->buf + i;
}

static void vtable_update(struct vtable *vt, struct str *key,
		int alloc_name, struct str *value, char scope)
{
	struct vt_cell *cell = vtable_getcell(vt, key);
	if (cell->vname.start == NULL) {
		++vt->cells_occupied;
		if ((double)vt->cells_occupied / hash_table_size >= 0.7)
			error("vtable: threshold reached");

		if (alloc_name)
			strdup(&cell->vname, key, 0);
		else
			cell->vname = *key;
	}
	cell->value = *value;
	cell->scope = scope;
}

static struct str *vtable_find(struct vtable *vt, struct str *key)
{
	struct vt_cell *tmp = vtable_getcell(vt, key);
	if (tmp->vname.start == NULL)
		return NULL;
	return &tmp->value;
}

static void rtable_add(struct rtable *rt, struct str *target,
	int alloc_name, struct rule_body *rule)
{
	struct rule_cell *cell = rtable_getcell(rt, target);
	if (cell->target != NULL)
		error("%S: rule redefinition", target);
	if ((double)rt->cells_occupied / hash_table_size >= 0.7)
		error("rtable: threshold reached");
	if (alloc_name) {
		cell->target = malloc(sizeof(*cell->target));
		strdup(cell->target, target, 0);
	} else {
		cell->target = target;
	}
	cell->body = rule;
	++rt->cells_occupied;
}

static int rtable_find(struct rtable *rt, struct str *key,
		struct rule_body **val)
{
	struct rule_cell *cell = rtable_getcell(rt, key);
	if (cell->target == NULL)
		return 0;
	*val = cell->body;
	return 1;
}

static char *strchr(char *s, char c)
{
	for (; *s; ++s) {
		if (*s == c)
			return s;
	}
	return NULL;
}

static char *mmap_file(char *fname)
{
	int fd = open(fname, O_RDONLY, 0);
	struct stat st;
	char *tmp;

	if (fd == -1)
		goto syserr;
	if (fstat(fd, &st) == -1)
		goto syserr;

	if (st.size == 0) {
		tmp = NULL;
		goto end;
	}

	tmp = mmap(NULL, st.size + 1, PROT_READ|PROT_WRITE,
		MAP_PRIVATE, fd, 0);
	if (tmp == (void*)-1)
		goto syserr;

end:
	if (close(fd) == -1)
		goto syserr;
	return tmp;
syserr:
	syscall_error(fname);
	return NULL; /* unreachable */
}

static int readline(struct file_stack *stack, struct line *line)
{
	char *tmp;
	char *marker = NULL;
	struct file *file;

	if (stack->idx == 0)
		return 0;
	file = stack->buf + stack->idx - 1;
	if (file->buf == NULL) {
		file->buf = mmap_file(file->name);
		if (file->buf == NULL) {
			--stack->idx;
			return readline(stack, line);
		}
	}

	tmp = file->buf;

	line->pos = (struct pos) { file->name, file->line };

	for (; *tmp && *tmp != '\n'; ++tmp) {
		if (*tmp == '#' && marker == NULL)
			marker = tmp;
		else if (tmp[0] == '\\' && tmp[1] == '\n') {
			tmp[0] = tmp[1] = ' ';
			++tmp;
			++file->line;
		}
	}

	if (*tmp == 0) {
		if (tmp == file->buf) {
			--stack->idx;
			return readline(stack, line);
		} else {
			error("last line missing '\\n'");
		}
	}

	*tmp = 0;
	line->str.start = file->buf;
	line->str.end = marker ? marker : tmp;

	file->buf = tmp + 1;
	++file->line;

	return 1;
}

/* Does not cross file end. We do not have to check if idx == 0, because
 * idx is always >0, if readline did not return "end of input".
 */
static int nextline_starts_with_tab(struct file_stack *fstack)
{
	return *fstack->buf[fstack->idx-1].buf == '\t';
}

#define buf_static_init(buf, local_buf, size) \
do { \
	buf.start = local_buf; \
	buf.end = buf.start + size; \
	buf.cur = buf.start; \
} while (0)

static void buf_init(struct buf *buf)
{
	buf->start = mem_alloc(buf_size);
	buf->end = buf->start + buf_size;
	buf->cur = buf->start;
}

static void __buf_putchar(struct buf *buf, char c, int inc)
{
	if (buf->cur == buf->end)
		error("buf_putchar: buffer resizing is not supported");
	if (c == '\t')
		c = ' ';
	if (c == ' ' && buf->cur > buf->start && buf->cur[-1] == ' ')
		return;
	*buf->cur = c;
	if (inc)
		++buf->cur;
}

static void buf_putchar(struct buf *buf, char c)
{
	__buf_putchar(buf, c, 1);
}

static void buf_put_silent_zero(struct buf *buf)
{
	__buf_putchar(buf, 0, 0);
}

static void buf_puts(struct buf *buf, struct str *str)
{
	char *tmp;
	for (tmp = str->start; tmp != str->end; ++tmp)
		buf_putchar(buf, *tmp);
}

static void buf_putsz(struct buf *buf, char *s)
{
	for (; *s; ++s)
		buf_putchar(buf, *s);
}

static int strempty(struct str *str)
{
	return str->start == str->end;
}

static int strlen(struct str *str)
{
	return str->end - str->start;
}

static char *find_cparent(struct str *str, struct pos *pos)
{
	char *tmp;
	int level = 0;
	for (tmp = str->start + 1; tmp != str->end; ++tmp) {
		if (*tmp == '(')
			++level;
		if (*tmp == ')') {
			if (level == 0)
				return tmp;
			else
				--level;
		}
	}
	errorp(pos, "missing ')'");
	return NULL; /* unreachable */
}

enum {
	id_variable,
	id_subref,

	id_prereqs,
	id_first_prereq,
	id_target,

	id_func_class_start,
	id_func_wildcard,
	id_func_subst,
	id_func_patsubst,
	id_func_filter,
	id_func_filter_out,

	id_func_basename,
	id_func_dir,

	id_func_shell,
	id_func_addprefix,
	id_func_addsuffix,
	id_func_sort,
	id_func_class_end
};

struct eprofile {
	char type;
	struct str *body;
	struct pos *pos;

	struct str from;
	struct str to;
};

static int is_space(char c)
{
	return c == ' ' || c == '\t';
}

static int valid_var_char(char c)
{
	return (c >= 'a' && c <= 'z') ||
		(c >= 'A' && c <= 'Z') ||
		( c >= '0' && c <= '9') ||
		c == '_' || c == '/' ||
		c == '-' || c == '.';
}

static char *word_end(struct str *str)
{
	char *tmp;
	for (tmp = str->start; tmp != str->end; ++tmp) {
		if (is_space(*tmp))
			return tmp;
		if (!valid_var_char(*tmp))
			return *tmp == ':' ? tmp : NULL;
	}
	return tmp;
}

#define ENTRY(fname) { CSTR(#fname), id_func_ ## fname }

static struct { struct str fname; char type; } func_table[] = {
	ENTRY(wildcard),
	ENTRY(subst),
	ENTRY(patsubst),
	ENTRY(filter),
	{ CSTR("filter-out"), id_func_filter_out },
	ENTRY(basename),
	ENTRY(dir),
	ENTRY(sort),
	ENTRY(shell),
	ENTRY(addprefix),
	ENTRY(addsuffix)
};
#undef ENTRY

static int is_special_var(struct eprofile *prof, struct str *word)
{
	if (streq(word, &CSTR("^"))) {
		prof->type = id_prereqs;
		return 1;
	} else if (streq(word, &CSTR("<"))) {
		prof->type = id_first_prereq;
		return 1;
	} else if (streq(word, &CSTR("@"))) {
		prof->type = id_target;
		return 1;
	}
	return 0;
}

static void check_var_form(struct str *word, struct str *all,
		struct pos *pos)
{
	if (word->end == all->end)
		return;
	errorp(pos, "(%S): variable name must be a single word", all);
}

static void parse_subref(struct eprofile *prof, struct str *vname,
		struct str *all)
{
	char *tmp;
	prof->type = id_subref;

	all->start = vname->end + 1;
	prof->from.start = all->start;
	for (tmp = all->start; tmp != all->end && *tmp != '='; ++tmp)
		;
	if (tmp == all->end)
		errorp(prof->pos, "%s: no '=' is subref expr", vname);
	prof->from.end = tmp;
	prof->to.start = tmp + 1;
	prof->to.end = all->end;

	*all = *vname;
	prof->body = all;
}

static void parse_profile(struct eprofile *prof, struct str *str,
		struct full_rule *rule)
{
	int i;
	char *wend;
	struct str first_word;

	if (rule != NULL && is_special_var(prof, str))
		return;

	wend = word_end(str);
	if (wend == NULL) {
		errorp(prof->pos,
			"invalid symbol during first word parsing");
	}
	first_word = (struct str) { str->start, wend };

	if (wend != str->end && *wend == ':') {
		parse_subref(prof, &first_word, str);
		return;
	}

	for (i = 0; i < sizeof(func_table) / sizeof(func_table[0]); ++i) {
		if (streq(&first_word, &func_table[i].fname)) {
			prof->type = func_table[i].type;
			str->start = first_word.end;
			prof->body = str;
			return;
		}
	}
	prof->type = id_variable;
	check_var_form(&first_word, str, prof->pos);
	prof->body = str;
}

static void __eval(struct eval_aux *aux, struct str *str);

static void swap_buffers(struct eval_aux *aux)
{
	struct buf *tmp = aux->mainbuf;
	aux->mainbuf = aux->auxbuf;
	aux->auxbuf = tmp;
}

static void eval_wrapper(struct eval_aux *aux, struct str *str,
		int swap, int zero_terminate)
{
	struct str tmp = *str;
	++aux->level;
	if (swap)
		swap_buffers(aux);
	__eval(aux, &tmp);
	if (zero_terminate)
		buf_put_silent_zero(aux->mainbuf);
	if (swap)
		swap_buffers(aux);
	--aux->level;
}

static int adjust_vname(struct buf *buf, struct full_rule *rule,
		struct str *vname)
{
	if (rule == NULL)
		return 0;
	buf_puts(buf, rule->target);
	buf_putchar(buf, '#');
	buf_puts(buf, vname);
	return 1;
}

static void expand_variable(struct eval_aux *aux, struct eprofile *prof)
{
	char localbuf[buf_static_size];
	struct buf buf;
	struct str *varval = NULL;

	buf_static_init(buf, localbuf, buf_static_size);
	if (adjust_vname(&buf, aux->rule, prof->body)) {
		struct str name = (struct str) { buf.start, buf.cur };
		varval = vtable_find(&aux->world->vtable, &name);
	}

	if (varval == NULL)
		varval = vtable_find(&aux->world->vtable, prof->body);

	if (varval == NULL)
		return;
	eval_wrapper(aux, varval, 0, 0);
}

static void expand_first_prereq(struct eval_aux *aux,
		struct eprofile *prof)
{
	if (aux->rule->rest->prereqs.len == 0)
		return;
	buf_puts(aux->mainbuf, &aux->rule->rest->prereqs.buf[0]);
}

static void expand_prereqs(struct eval_aux *aux,
		struct eprofile *prof)
{
	int i;
	struct strbuf *prereqs = &aux->rule->rest->prereqs;
	for (i = 0; i < prereqs->len; ++i) {
		buf_puts(aux->mainbuf, &prereqs->buf[i]);
		if (i + 1 != prereqs->len)
			buf_putchar(aux->mainbuf, ' ');
	}
}

static void trim_front(struct str *str);
static void trim_back(struct str *str);
static void trim(struct str *str);

static int extract_word(struct str *str, struct str *word)
{
	char *tmp;

	trim_front(str);
	if (strempty(str))
		return 0;

	tmp = str->start;
	word->start = tmp;
	for (; tmp != str->end && !is_space(*tmp); ++tmp)
		;
	word->end = tmp;

	str->start = tmp;
	return 1;
}

struct matched {
	int front_remains;
	int have_wildcard;
	struct str wildcard;
};

static char *contains_char(struct str *str, char c);

static int matches_wildcard(struct matched *m, struct str *pat,
		struct str *str, char *wildcard)
{
	int ret;
	int diff = wildcard - pat->start;
	ret = memeq(str->start, pat->start, diff);
	if (ret == 0)
		return 0;
	if (m)
		m->wildcard.start = str->start + diff;
	diff = pat->end - (wildcard + 1);
	ret = memeq(str->end - diff, pat->end - diff, diff);
	if (ret == 0)
		return 0;
	if (m) {
		m->wildcard.end = str->end - diff;
		m->have_wildcard = 1;
	}
	return 1;
}

static int match_str(struct str *pat, struct str *str,
		struct matched *m)
{
	char *tmp;

	if (m) {
		m->front_remains = 0;
		m->have_wildcard = 0;
	}

	tmp = contains_char(pat, '%');
	if (tmp != NULL) {
		if(!matches_wildcard(m, pat, str, tmp))
			return 0;
	} else {
		int ret;
		int diff = strlen(str) - strlen(pat);
		if (diff < 0)
			return 0;
		ret = memeq(str->start + diff, pat->start, strlen(pat));
		if (ret == 0)
			return 0;
		if (m)
			m->front_remains = diff;
	}
	return 1;
}

static int pmatches(struct eprofile *prof, struct str *value,
		struct matched *m)
{
	return match_str(&prof->from, value, m);
}

static void modify(struct eval_aux *aux, struct eprofile *prof,
		struct str *value, struct matched *m)
{
	int i;
	char *tmp;
	struct str *template = &prof->to;
	for (i = 0; i < m->front_remains; ++i)
		buf_putchar(aux->mainbuf, value->start[i]);
	for (tmp = template->start; tmp != template->end; ++tmp) {
		if (*tmp == '%' && m->have_wildcard)
			buf_puts(aux->mainbuf, &m->wildcard);
		else
			buf_putchar(aux->mainbuf, *tmp);
	}
}

static void subref(struct eval_aux *aux, struct eprofile *prof,
		struct str *value)
{
	int first = 1;
	for (;; first = 0) {
		struct str word;
		struct matched matched;

		if (!extract_word(value, &word))
			break;

		if (!first)
			buf_putchar(aux->mainbuf, ' ');

		if (pmatches(prof, &word, &matched))
			modify(aux, prof, &word, &matched);
		else
			buf_puts(aux->mainbuf, &word);
	}
}

static void expand_subref(struct eval_aux *aux, struct eprofile *prof)
{
	char *savedpos = aux->auxbuf->cur;
	char *tmp;
	struct str value;
	prof->type = id_variable;

	swap_buffers(aux);
	expand_variable(aux, prof);
	swap_buffers(aux);
	value = (struct str) { savedpos, aux->auxbuf->cur };

	tmp = aux->auxbuf->cur;
	eval_wrapper(aux, &prof->from, 1, 0);
	prof->from = (struct str) { tmp, aux->auxbuf->cur };

	tmp = aux->auxbuf->cur;
	eval_wrapper(aux, &prof->to, 1, 0);
	prof->to = (struct str) { tmp, aux->auxbuf->cur };

	subref(aux, prof, &value);

	aux->auxbuf->cur = savedpos;
}

static void expand_target(struct eval_aux *aux)
{
	eval_wrapper(aux, aux->rule->target, 0, 0);
}

static int extract_farg(struct str *src, struct str *arg)
{
	int level = 0;
	char *tmp;

	arg->start = src->start;
	for (tmp = src->start; tmp != src->end; ++tmp) {
		if (*tmp == '(')
			++level;
		else if (*tmp == ')')
			--level;
		else if (*tmp == ',' && level == 0)
			break;

	}
	arg->end = tmp;
	if (tmp == src->end)
		return 0;
	src->start = tmp + 1;
	return 1;
}

static void basename_word(struct str *res, struct str *word)
{
	char *tmp = word->end - 1;
	char *dot = NULL;
	for (; tmp >= word->start; --tmp) {
		if (*tmp == '.' && dot == NULL) {
			dot = tmp;
			break;
		}
		if (*tmp == '/')
			break;
	}
	*res = (struct str) {
		word->start,
		dot ? dot : word->end
	};
}

static void dir_word(struct str *res, struct str *word)
{
	char *tmp = word->end - 1;
	char *slash = NULL;

	for (; tmp >= word->start; --tmp) {
		if (*tmp == '/') {
			slash = tmp;
			break;
		}
	}
	if (slash == NULL)
		*res = CSTR("./");
	else
		*res = (struct str) { word->start, slash + 1 };
}

static void extract_args(struct str *args, struct str *str, int argnum,
		char *func, struct pos *pos)
{
	int i;
	for (i = 0;; ++i) {
		int ret = extract_farg(str, args + i);
		if (i == argnum - 1) {
			if (ret == 1)
				goto argcount_err;
			else {
				trim(args + i);
				return;
			}
		}
		if (ret == 0)
			goto argcount_err;
		trim(args + i);
	}
argcount_err:
	errorp(pos, "%s expects %d argument%s", func, argnum,
			argnum > 1 ? "s" : "");
}

enum {
	mode_basename,
	mode_dir,
};

static void expand_basename_or_dir(struct eval_aux *aux, int mode,
		struct eprofile *prof)
{
	struct str arg;
	int first = 1;

	char *func = mode == mode_basename ? "basename" : "dir";
	extract_args(&arg, prof->body, 1, func, aux->pos);

	for (;; first = 0) {
		struct str word, res;

		if(!extract_word(&arg, &word))
			break;

		if (mode == mode_basename)
			basename_word(&res, &word);
		else
			dir_word(&res, &word);
		if (!first)
			buf_putchar(aux->mainbuf, ' ');
		buf_puts(aux->mainbuf, &res);
	}
}

static int arg_is_single_word(struct str *str)
{
	struct str word;

	if (!extract_word(str, &word))
		return 0;
	trim_front(str);

	if (!strempty(str))
		return 0;
	*str = word;
	return 1;
}

enum {
	mode_prefix,
	mode_suffix
};

static void expand_add(struct eval_aux *aux, int mode,
		struct eprofile *prof)
{
	struct str args[2];
	int first = 1;

	char *func = mode == mode_prefix ? "addprefix" : "addsuffix";
	extract_args(args, prof->body, 2, func, aux->pos);

	if (!arg_is_single_word(args))
		errorp(aux->pos, "%s: accepts a single prefix", func);

	for (;; first = 0) {
		struct str word;

		if (!extract_word(args + 1, &word))
			break;

		if (!first)
			buf_putchar(aux->mainbuf, ' ');
		if (mode == mode_prefix) {
			buf_puts(aux->mainbuf, args);
			buf_puts(aux->mainbuf, &word);
		} else {
			buf_puts(aux->mainbuf, &word);
			buf_puts(aux->mainbuf, args);
		}
	}
	return;
}

enum {
	mode_filter,
	mode_filter_out
};

static int passes_filter(struct str *str, struct strbuf *pats, int mode)
{
	int ret_when_matches = mode == mode_filter ? 1 : 0;
	int i;
	for (i = 0; i < pats->len; ++i) {
		if (match_str(pats->buf + i, str, NULL))
			return ret_when_matches;
	}
	return !ret_when_matches;
}

static void strbuf_init(struct strbuf *buf);
static void strbuf_push(struct strbuf *buf, struct str *str);

static void collect_words(struct strbuf *buf, struct str *words)
{
	strbuf_init(buf);

	for (;;) {
		struct str word;
		int ret = extract_word(words, &word);
		if (ret == 0)
			break;
		strbuf_push(buf, &word);
	}
}

static void filter_words(struct str *words, struct strbuf *pats,
		struct eval_aux *aux, int mode)
{
	int first = 1;
	for (;;) {
		struct str word;
		int ret = extract_word(words, &word);
		if (ret == 0)
			break;
		if (!passes_filter(&word, pats, mode))
			continue;
		if (!first)
			buf_putchar(aux->mainbuf, ' ');
		buf_puts(aux->mainbuf, &word);
		first = 0;
	}
}

static void expand_filter(struct eval_aux *aux, int mode,
		struct eprofile *prof)
{
	struct str args[2];
	struct strbuf pats;

	char *func = mode == mode_filter ? "filter" : "filter-out";
	extract_args(args, prof->body, 2, func, aux->pos);

	heap_offset_save();
	collect_words(&pats, args);
	filter_words(args + 1, &pats, aux, mode);
	heap_offset_restore();
}

static void merge(struct str *to, struct str *from, int n)
{
	int mid = n/2;
	int i, j, k;

	for (k = 0, i = 0, j = mid; i < mid && j < n; ++k) {
		if (strge(from + j, from + i)) {
			to[k] = from[i];
			++i;
		} else {
			to[k] = from[j];
			++j;
		}
	}
	if (i < mid) {
		for (; i < mid; ++i, ++k)
			to[k] = from[i];
	} else {
		for (; j < n; ++j, ++k)
			to[k] = from[j];
	}
}

static void mergesort(struct str *array, struct str *tmp,
	int n)
{
	if (n < 2)
		return;
	mergesort(tmp, array, n/2);
	mergesort(tmp + n/2, array + n/2, n - n/2);
	merge(array, tmp, n);
}

static void sort(struct strbuf *words)
{
	struct str *tmp = malloc(sizeof(*tmp) * words->len);
	int i;
	for (i = 0; i < words->len; ++i)
		tmp[i] = words->buf[i];

	mergesort(words->buf, tmp, words->len);
}

static void uniq(struct strbuf *words)
{
	int i, j;
	struct str *array = words->buf;
	for (i = 0, j = 0; i < words->len; ++i) {
		if (j > 0 && streq(&array[i], &array[j-1]))
			continue;
		array[j] = array[i];
		++j;
	}
	words->len = j;
}

static void expand_sort(struct eval_aux *aux, struct eprofile *prof)
{
	struct strbuf words;
	struct str arg;
	int i;

	heap_offset_save();
	extract_args(&arg, prof->body, 1, "sort", aux->pos);
	collect_words(&words, &arg);

	sort(&words);
	uniq(&words);

	for (i = 0; i < words.len; ++i) {
		if (i > 0)
			buf_putchar(aux->mainbuf, ' ');
		buf_puts(aux->mainbuf, &words.buf[i]);
	}

	heap_offset_restore();
}

static void save_shell_stdout(int fd, struct buf *buf)
{
	char tmpbuf[buf_static_size];
	struct str tmp = { buf->cur };
	int skip_spaces = 1;
	for (;;) {
		int i;
		int ret = read(fd, tmpbuf, buf_static_size);
		if (ret == -1)
			syscall_error("shell output read");
		if (ret == 0)
			break;
		for (i = 0; i < ret; ++i) {
			char c = tmpbuf[i];
			if (tmpbuf[i] == '\n')
				c = ' ';

			if (is_space(c)) {
				if (skip_spaces)
					continue;
			} else
				skip_spaces = 1;
			buf_putchar(buf, c);
		}
	}
	tmp.end = buf->cur;
	trim_back(&tmp);
	buf->cur = tmp.end;
	close(fd);
}
static void check_status(int status, char *prx);

static void expand_shell(struct eval_aux *aux, struct eprofile *prof)
{
	struct str arg;
	extract_args(&arg, prof->body, 1, "shell", aux->pos);
	int pipefds[2];
	int status, pid;

	trim_front(&arg);
	if (pipe(pipefds) == -1)
		syscall_error("pipe");
	pid = fork();
	if (pid == -1)
		syscall_error("fork");
	if (pid == 0) {
		char *argv[] = { "/bin/sh", "-c", arg.start, NULL };
		if (dup2(pipefds[1], 1) == -1)
			syscall_error("dup2");
		close(pipefds[1]);
		close(pipefds[0]);
		execve(argv[0], argv, aux->world->envp);
		exit(255);
	}
	close(pipefds[1]);
	save_shell_stdout(pipefds[0], aux->mainbuf);
	wait4(pid, &status, 0, NULL);
	check_status(status, "shell: ");
}

static void subst(struct buf *buf, struct str *from, struct str *to,
		struct str *word)
{
	int i = 0;
	int fromlen = strlen(from);
	int n = strlen(word);
	while (i <= n - fromlen) {
		if (memeq(word->start + i, from->start, fromlen)) {
			buf_puts(buf, to);
			i += fromlen;
		} else {
			buf_putchar(buf, word->start[i]);
			++i;
		}
	}
	for (; i < n; ++i)
		buf_putchar(buf, word->start[i]);
}

static void expand_subst(struct eval_aux *aux, struct eprofile *prof)
{
	struct str args[3];
	int first = 1;

	extract_args(args, prof->body, 3, "subst", aux->pos);

	if (!arg_is_single_word(args))
		goto single_word_err;
	if (!arg_is_single_word(args + 1))
		goto single_word_err;

	for (;; first = 0) {
		struct str word;
		int ret = extract_word(args + 2, &word);
		if (ret == 0)
			break;
		if (!first)
			buf_putchar(aux->mainbuf, ' ');
		subst(aux->mainbuf, args, args + 1, &word);
	}
	return;
single_word_err:
	errorp(aux->pos, "subst: from/to must to single words");
}

static int matches(struct str *pat, struct str *str,
		struct str *wildcard);

static void patsubst(struct buf *buf, struct str *from,
		struct str *to, struct str *words)
{
	int first = 1;
	for (;; first = 0) {
		struct str word, wildcard;

		if (extract_word(words, &word) == 0)
			break;
		if (!first)
			buf_putchar(buf, ' ');
		if (matches(from, &word, &wildcard)) {
			char *tmp;
			for (tmp = to->start; tmp != to->end; ++tmp) {
				if (*tmp == '%')
					buf_puts(buf, &wildcard);
				else
					buf_putchar(buf, *tmp);
			}
		} else {
			buf_puts(buf, &word);
		}
	}
}

static void expand_patsubst(struct eval_aux *aux, struct eprofile *prof)
{
	struct str args[3];
	extract_args(args, prof->body, 3, "patsubst", aux->pos);

	if (!arg_is_single_word(args))
		goto single_word_err;
	if (!arg_is_single_word(args + 1))
		goto single_word_err;
	if (!contains_char(args, '%'))
		goto no_wildcard_err;
	if (!contains_char(args + 1, '%'))
		goto no_wildcard_err;

	patsubst(aux->mainbuf, args, args + 1, args + 2);
	return;

single_word_err:
	errorp(aux->pos, "patsubst: from/to must be single words");
no_wildcard_err:
	errorp(aux->pos, "patsubst: from/to must contain '%'");
}

enum {
	max_limbs = 64
};

struct pathbuf {
	struct str limbuf[max_limbs];
	int limbs;

	char buf[path_max_len];
	char *cur;

	int add_space;
	struct pos *pos;

	struct buf *dest;
};

static void __pbuf_putchar(struct pathbuf *pbuf, char c, int inc)
{
	if (pbuf->cur == pbuf->buf + path_max_len)
		error("pathbuf: no more space");
	*pbuf->cur = c;
	if (inc)
		++pbuf->cur;
}

static void pbuf_putchar(struct pathbuf *pbuf, char c)
{
	__pbuf_putchar(pbuf, c, 1);
}

static void pbuf_put_silent_zero(struct pathbuf *pbuf)
{
	__pbuf_putchar(pbuf, 0, 0);
}

static void add_slash(struct pathbuf *pbuf)
{
	if (pbuf->cur - pbuf->buf > 1 || pbuf->cur[-1] == '.')
		pbuf_putchar(pbuf, '/');
}

static void pbuf_putlimb(struct pathbuf *pbuf, struct str *limb)
{
	char *tmp;
	add_slash(pbuf);
	for (tmp = limb->start; tmp != limb->end; ++tmp)
		pbuf_putchar(pbuf, *tmp);
}

static void pbuf_putlimbz(struct pathbuf *pbuf, char *limb)
{
	add_slash(pbuf);
	for (; *limb; ++limb)
		pbuf_putchar(pbuf, *limb);
}

static void skip_slashes(struct str *path)
{
	char *tmp = path->start;
	for (; tmp != path->end && *tmp == '/'; ++tmp)
		;
	path->start = tmp;
}

static void init_beginning(struct pathbuf *pbuf, struct str *path)
{
	if (path->start[0] == '/') {
		skip_slashes(path);
		pbuf_putchar(pbuf, '/');
	} else {
		pbuf_putchar(pbuf, '.');
	}
}

static struct str *get_word(struct pathbuf *pbuf)
{
	if (pbuf->limbs == max_limbs)
		error("pathbuf: too deep nesting");
	return pbuf->limbuf + pbuf->limbs;
}

static int eat_limb(struct pathbuf *pbuf, struct str *path)
{
	struct str *dest;
	char *tmp;
	if (strempty(path))
		return 0;
	dest = get_word(pbuf);
	dest->start = path->start;
	for (tmp = path->start; tmp != path->end && *tmp != '/'; ++tmp)
		;
	dest->end = tmp;
	path->start = tmp;
	skip_slashes(path);
	++pbuf->limbs;
	return 1;
}

static void parse_path(struct pathbuf *pbuf, struct str *path)
{
	init_beginning(pbuf, path);
	while (eat_limb(pbuf, path))
		;
}

static int is_pattern(struct str *str)
{
	char *tmp = str->start;
	for (; tmp != str->end; ++tmp) {
		if (*tmp == '*' || *tmp == '?')
			return 1;
	}
	return 0;
}

static int is_special(char *dent)
{
	return dent[0] == '.' &&
		(dent[1] == 0 || (dent[1] == '.' && dent[2] == 0));
}

static int __match(char *pat, char *str, struct pos *pos)
{
	for (; *pat; ++pat) {
		if (*pat == '*') {
			char *sc;
			for (sc = str; ; ++sc) {
				if (__match(pat + 1, sc, pos))
					return 1;
				if (*sc == 0)
					return 0;
			}
		} else if (*pat == '?') {
			if (*str)
				++str;
			else
				return 0;
		} else if (*pat == '[') {
			int ret = 0;
			for (++pat; *pat && *pat != ']'; ++pat) {
				if (*pat == *str)
					ret = 1;
			}
			if (*pat == 0)
				errorp(pos, "wildcard missing ']'");
			if (ret == 0)
				return 0;
			++str;
		} else {
			if (*pat != *str)
				return 0;
			++str;
		}
	}
	return *str == 0;
}

static int match_pattern(struct str *pat, char *s, struct pos *pos)
{
	char c = *pat->end;
	int ret;

	*pat->end = 0;

	ret = __match(pat->start, s, pos);

	*pat->end = c;
	return ret;
}

static void follow_path(struct pathbuf *pbuf, int start);

static void iterate(struct pathbuf *pbuf, int idx)
{
	struct dir dir;

	heap_offset_save();

	pbuf_put_silent_zero(pbuf);
	if (opendir(&dir, pbuf->buf) == 0)
		goto end;

	char *cur = pbuf->cur;
	for (;;) {
		struct dirent *dent = readdir(&dir);
		pbuf->cur = cur;

		if (dent == NULL)
			break;
		if (is_special(dent->name))
			continue;

		int res = match_pattern(pbuf->limbuf + idx, dent->name,
				pbuf->pos);
		if (res) {
			pbuf_putlimbz(pbuf, dent->name);
			follow_path(pbuf, idx + 1);
		}
	}
	closedir(&dir);
end:
	heap_offset_restore();
}

static void commit(struct buf *dest, char *path)
{
	char *tmp = path[0] == '/' ? path : path + 2;
	buf_putsz(dest, tmp);
}

static int exists(char *path);

static void follow_path(struct pathbuf *pbuf, int start)
{
	int i;
	for (i = start; i < pbuf->limbs; ++i) {
		if (is_pattern(pbuf->limbuf + i)) {
			iterate(pbuf, i);
			return;
		} else {
			pbuf_putlimb(pbuf, pbuf->limbuf + i);
		}
	}
	pbuf_put_silent_zero(pbuf);
	if (exists(pbuf->buf)) {
		if (pbuf->add_space)
			buf_putchar(pbuf->dest, ' ');
		commit(pbuf->dest, pbuf->buf);
		pbuf->add_space = 1;
	}
}

static int wexpand(struct buf *buf, struct str *path, int add_space,
		struct pos *pos)
{
	static struct pathbuf pbuf;
	pbuf.limbs = 0;
	pbuf.cur = pbuf.buf;
	pbuf.add_space = add_space;
	pbuf.dest = buf;
	pbuf.pos = pos;

	parse_path(&pbuf, path);
	follow_path(&pbuf, 0);
	return pbuf.add_space;
}

static void expand_wildcard(struct eval_aux *aux, struct eprofile *prof)
{
	struct str arg;
	int first = 1;

	extract_args(&arg, prof->body, 1, "wildcard", aux->pos);
	for (;;) {
		struct str word;
		if (extract_word(&arg, &word) == 0)
			break;
		int ret = wexpand(aux->mainbuf, &word, !first,
			aux->pos);
		if (ret && first)
			first = 0;
	}
}

static void expand_func(struct eval_aux *aux, struct eprofile *prof)
{
	char *savedpos = aux->auxbuf->cur;
	eval_wrapper(aux, prof->body, 1, 1);
	prof->body = &(struct str) { savedpos, aux->auxbuf->cur };

	switch(prof->type) {
	case id_func_basename:
		expand_basename_or_dir(aux, mode_basename, prof);
		break;
	case id_func_dir:
		expand_basename_or_dir(aux, mode_dir, prof);
		break;
	case id_func_addprefix:
		expand_add(aux, mode_prefix, prof);
		break;
	case id_func_addsuffix:
		expand_add(aux, mode_suffix, prof);
		break;
	case id_func_filter:
		expand_filter(aux, mode_filter, prof);
		break;
	case id_func_filter_out:
		expand_filter(aux, mode_filter_out, prof);
		break;
	case id_func_sort:
		expand_sort(aux, prof);
		break;
	case id_func_shell:
		expand_shell(aux, prof);
		break;
	case id_func_subst:
		expand_subst(aux, prof);
		break;
	case id_func_patsubst:
		expand_patsubst(aux, prof);
		break;
	case id_func_wildcard:
		expand_wildcard(aux, prof);
		break;
	default:
		error("func id=%d not implemented yet", prof->type);
	}
	aux->auxbuf->cur = savedpos;
}

static void __expand(struct eval_aux *aux, struct eprofile *prof)
{
	switch(prof->type) {
	case id_variable:
		expand_variable(aux, prof);
		break;
	case id_subref:
		expand_subref(aux, prof);
		break;
	case id_target:
		expand_target(aux);
		break;
	case id_first_prereq:
		expand_first_prereq(aux, prof);
		break;
	case id_prereqs:
		expand_prereqs(aux, prof);
		break;
	default:
		expand_func(aux, prof);
		break;
	}
}

static void expand(struct eval_aux *aux, struct str *str)
{
	struct eprofile profile;
	struct str estr;

	if (strempty(str))
		errorp(aux->pos, "stray '$'");

	if (*str->start == '(') {
		char *end = find_cparent(str, aux->pos);

		++str->start;
		estr = (struct str) { str->start, end };
		str->start = end + 1;
	} else {
		estr = (struct str) { str->start, str->start + 1 };
		++str->start;
	}
	profile.pos = aux->pos;
	parse_profile(&profile, &estr, aux->rule);
	__expand(aux, &profile);
}

static int stop_sym(char c)
{
	return c == '=' || c == '+' || c == ':';
}

static void __eval(struct eval_aux *aux, struct str *str)
{
	while (str->start != str->end) {
		if (stop_sym(*str->start) && aux->level == 0 &&
				aux->rule == NULL)
		{
			return;
		} else if (*str->start == '$') {
			++str->start;
			expand(aux, str);
		} else {
			buf_putchar(aux->mainbuf, *str->start);
			++str->start;
		}
	}
}

static struct buf *evict_buf(struct buf *buf)
{
	static struct buf tmp;
	tmp = *buf;
	tmp.end = tmp.cur;
	buf->start = buf->cur;
	return &tmp;
}

static struct buf *eval(struct world *world, struct line *line,
		struct full_rule *rule)
{
	static char localbuf2[buf_size];
	static struct buf buffers[2] = {
		{ NULL, NULL, NULL },
		{ NULL, NULL, NULL }
	};
	struct eval_aux aux;

	if (buffers[0].start == NULL)
		buf_init(buffers);
	else
		buffers[0].cur = buffers[0].start;
	buf_static_init(buffers[1], localbuf2, buf_size);

	aux = (struct eval_aux) {
		0,
		&line->pos,
		rule,
		buffers, buffers + 1,
		world
	};
	__eval(&aux, &line->str);
	buf_putchar(buffers, ' ');

	return rule == NULL ? evict_buf(buffers) : buffers;
}

static void trim_front(struct str *str)
{
	for (; str->start != str->end; ++str->start) {
		if (!is_space(*str->start))
			break;
	}
}

static void trim_back(struct str *str)
{
	for (; str->start != str->end; --str->end) {
		if (!is_space(str->end[-1]))
			break;
	}
}

static void trim(struct str *str)
{
	trim_front(str);
	trim_back(str);
}

static int valid_var_name(struct str *vname)
{
	char *tmp;
	for (tmp = vname->start; tmp != vname->end; ++tmp) {
		if (!valid_var_char(*tmp))
			return 0;
	}
	return 1;
}

static void str_combine(struct str *res, struct str *s1, struct str *s2)
{
	int len1, len2, nlen;

	if (s1 == NULL) {
		*res = *s2;
		return;
	}
	len1 = strlen(s1);
	len2 = strlen(s2);
	nlen = len1 + len2 + 1;

	res->start = malloc(nlen);
	res->end = res->start + nlen;

	memcpy(res->start, s1->start, len1);
	res->start[len1] = ' ';
	memcpy(res->start + len1 + 1, s2->start, len2);
}

enum {
	svmode_set,
	svmode_append
};

static void make_full_vname(struct buf *dest, struct str *prx,
		struct str *vname)
{
	dest->cur = dest->start;
	buf_puts(dest, prx);
	buf_putchar(dest, '#');
	buf_puts(dest, vname);
}

struct variable {
	struct str name;
	struct strbuf *goals;
	struct str *value;
	char scope;

	struct pos *pos;
	struct vtable *vt;
};

static int check_policy(struct variable *var, struct str *name)
{
	struct vt_cell *cell = vtable_getcell(var->vt, name);

	return !(cell->scope == vs_cmdargs && var->scope == vs_makefile);
}

static void set_single_var(struct variable *var, struct str *goal, int mode)
{
	static char localbuf[buf_static_size];
	struct buf buf;
	struct str fullname;
	/* TODO: Why do we need to alloc for goal specific assignments */
	int alloc = goal ? 1 : 0;

	buf_static_init(buf, localbuf, buf_static_size);

	if (goal != NULL) {
		make_full_vname(&buf, goal, &var->name);
		fullname = (struct str) { buf.start, buf.cur };
	} else {
		fullname = var->name;
	}

	if (mode == svmode_set) {
		if (check_policy(var, &fullname) == 0)
			return;
		/* Double work, but I do not think we should even bother */
		vtable_update(var->vt, &fullname, alloc, var->value, var->scope);
	} else {
		struct str newval;
		struct str *oldval = vtable_find(var->vt, &fullname);
		if (oldval == NULL)
			oldval = vtable_find(var->vt, &var->name);
		str_combine(&newval, oldval, var->value);
		vtable_update(var->vt, &fullname, alloc, &newval, var->scope);
	}
}

static void setvar(struct variable *var, int mode)
{
	trim(var->value);

	if (var->goals != NULL) {
		int i;
		for (i = 0; i < var->goals->len; ++i)
			set_single_var(var, &var->goals->buf[i], mode);
	} else {
		set_single_var(var, NULL, mode);
	}
}

static int is_followed(struct line *line, char c)
{
	return strlen(&line->str) >= 2 && line->str.start[1] == c;
}

static void follows(struct line *line, char c)
{
	if (is_followed(line, c))
		return;
	errorp(&line->pos, "expected %c after %c", c, line->str.start[0]);
}

static void parse_assignment(struct world *world, struct strbuf *goals,
		struct buf *buf, struct line *line, char scope)
{
	struct variable var = {
		{ buf->start, buf->cur },
		goals,
		&line->str,
		scope,

		&line->pos,
		&world->vtable
	};

	trim(&var.name);
	if (!valid_var_name(&var.name)) {
		errorp(&line->pos, "[%S]: invalid variable name",
			&var.name);
	}
	if (var.value->start[0] == '+') {
		follows(line, '=');
		var.value->start += 2;
		setvar(&var, svmode_append);
	} else {
		++var.value->start;
		setvar(&var, svmode_set);
	}
}

#define SBUF_INIT(type) \
static void type ## _init(struct type *buf) \
{ \
	buf->size = 1; \
	buf->len = 0; \
	buf->buf = malloc(sizeof(*buf->buf) * buf->size); \
}

SBUF_INIT(strbuf)
SBUF_INIT(cmdbuf)

static void strbuf_push(struct strbuf *buf, struct str *str)
{
	if (buf->len == buf->size) {
		buf->size *= 2;
		realloc(buf->buf, sizeof(*buf->buf) * buf->size);
	}
	buf->buf[buf->len] = *str;
	++buf->len;
}

static void cmdbuf_push(struct cmdbuf *buf, struct str *str,
	struct pos *pos)
{
	if (buf->len == buf->size) {
		buf->size *= 2;
		realloc(buf->buf, sizeof(*buf->buf) * buf->size);
	}
	buf->buf[buf->len].str = *str;
	buf->buf[buf->len].pos = *pos;
	++buf->len;
}

static int valid_target_char(char c)
{
	return valid_var_char(c) || c == '%';
}

static void save_word(struct strbuf *buf, struct str *str,
	struct pos *pos)
{
	struct str word;
	word.start = str->start;

	/* No check for empty string here, because str is part of eval
	 * result. It won't be overwritten in this case. And at the end
	 * of eval we add ' ' for this function.
	 */
	for (;; ++str->start) {
		if (is_space(*str->start) || *str->start == ':')
			break;
		if (!valid_target_char(*str->start))
			goto err;
	}
	word.end = str->start;
	*str->start = 0;
	++str->start;

	strbuf_push(buf, &word);
	return;
err:
	errorp(pos, "%c: invalid target/prereq name symbol", *str->start);
}

static void parse_targets(struct strbuf *targets, struct buf *buf,
	struct pos *pos)
{
	struct str str = { buf->start, buf->cur };
	strbuf_init(targets);

	for (;;) {
		trim_front(&str);
		if (strempty(&str))
			break;
		save_word(targets, &str, pos);
	}
	if (targets->len == 0)
		errorp(pos, "zero targets before ':'");
}

static void parse_prereqs(struct rule_body *rule, struct buf *buf,
	struct pos *pos)
{
	struct str str = { buf->start, buf->cur };
	strbuf_init(&rule->prereqs);
	int i = 0;
	int normal = -1;

	for (;;) {
		trim_front(&str);
		if (strempty(&str))
			break;
		if (*str.start == '|' && normal == -1) {
			normal = i;
			++str.start;
			trim_front(&str);
		}
		save_word(&rule->prereqs, &str, pos);
		++i;
	}
	rule->normal_prereq_count = normal == -1 ? i : normal;
}

static struct cmdbuf *parse_recipes(struct file_stack *fstack)
{
	struct cmdbuf *tmp = malloc(sizeof(*tmp));
	cmdbuf_init(tmp);

	while (nextline_starts_with_tab(fstack)) {
		struct line line;
		readline(fstack, &line);

		trim(&line.str);
		cmdbuf_push(tmp, &line.str, &line.pos);
	}
	return tmp;
}

static void save_first_target(struct world *world,
		struct rule_details *rule)
{
	if (!strempty(&world->target) || rule->patrule ||
		streq(&rule->targets.buf[0], &CSTR(".PRECIOUS")))
	{
		return;
	}
	world->target = *rule->targets.buf;
}

static char *contains_char(struct str *str, char c)
{
	char *tmp;
	for (tmp = str->start; tmp != str->end; ++tmp) {
		if (*tmp == c)
			return tmp;
	}
	return NULL;
}

static int is_patrule(struct strbuf *targets, struct pos *pos)
{
	if (contains_char(&targets->buf[0], '%') == NULL)
		return 0;
	if (targets->len == 1)
		return 1;
	errorp(pos, "multiple targets not supported in patturn rules");
	return -1; /* unreachable */
}

static void add_patrule(struct world *world, struct rule_details *rule)
{
	if (world->pat_rule_num == pat_rules_limit)
		errorp(rule->pos, "pattern rules limit reached");
	world->pat_rules[world->pat_rule_num] = (struct full_rule) {
		&rule->targets.buf[0],
		rule->body
	};
	++world->pat_rule_num;
}

static void handle_normal(struct world *world, struct rule_details *rule,
		struct buf *buf)
{
	int i;
	parse_prereqs(rule->body, buf, rule->pos);
	rule->body->recipes = parse_recipes(&world->fstack);

	if (rule->patrule) {
		add_patrule(world, rule);
		return;
	}

	for (i = 0; i < rule->targets.len; ++i) {
		if (streq(&rule->targets.buf[i], &CSTR(".PRECIOUS")))
			continue;
		rtable_add(&world->rtable, &rule->targets.buf[i], 0,
			rule->body);
	}
}

char *target_spec_in_patrules =
	"target-specific var in pattern rules are not supported";

static void handle_target_spec(struct world *world, struct buf *buf,
		struct line *line, struct rule_details *rule)
{
	if (rule->patrule)
		errorp(&line->pos, target_spec_in_patrules);
	if (*line->str.start == ':')
		errorp(&line->pos, "expected target-specific var");

	parse_assignment(world, &rule->targets, buf, line, vs_makefile);
}

static void parse_rule(struct world *world, struct buf *buf,
		struct line *line)
{
	struct rule_details rule;

	++line->str.start;
	rule.body = malloc(sizeof(*rule.body));
	rule.pos = &line->pos;

	parse_targets(&rule.targets, buf, &line->pos);
	rule.patrule = is_patrule(&rule.targets, &line->pos);

	buf = eval(world, line, NULL);
	if (strempty(&line->str))
		handle_normal(world, &rule, buf);
	else
		handle_target_spec(world, buf, line, &rule);

	save_first_target(world, &rule);
}

static void fstack_add(struct file_stack *stack, char *file,
	struct pos *pos)
{
	if (stack->idx == file_stack_size) {
		struct pos tpos = (struct pos) { "cmdarg", 0 };
		errorp(pos ? pos : &tpos, "include nesting is too deep");
	}
	stack->buf[stack->idx] = (struct file) { file, NULL, 1 };
	++stack->idx;
}

static int is_include_directive(struct str *line)
{
	struct str linec;
	if (line->end - line->start < 8)
		return 0;
	linec = (struct str) { line->start, line->start + 8 };
	return streq(&CSTR("include "), &linec);
}

static void handle_include(struct world *world, struct line *line)
{
	line->str.start += 8;
	*line->str.end = 0;
	fstack_add(&world->fstack, line->str.start, &line->pos);
}

static int parse_toplev(struct world *world)
{
	struct line line;
	struct buf *buf;

	if (!readline(&world->fstack, &line))
		return 0;
	buf = eval(world, &line, NULL);

	if (strempty(&line.str)) {
		struct line tmp = { { buf->start, buf->cur }, line.pos };
		trim(&tmp.str);
		if (is_include_directive(&tmp.str)) {
			handle_include(world, &tmp);
			return 1;
		}
		if (!strempty(&tmp.str))
			errorp(&tmp.pos, "missing separator");
	} else if (*line.str.start == ':') {
		parse_rule(world, buf, &line);
	} else {
		parse_assignment(world, NULL, buf, &line, vs_makefile);
	}
	return 1;
}

static void parse(struct world *world)
{
	while (parse_toplev(world))
		;
}

static int is_assignment(char *arg, char **equal_sign)
{
	char *tmp = strchr(arg, '=');
	if (tmp == NULL) {
		*equal_sign = NULL;
		return 0;
	}
	*equal_sign = tmp;
	return 1;
}

static void parse_cmdarg_assignment(struct world *world, char *arg,
	char *equal_sign)
{
	struct buf buf = { arg, equal_sign, equal_sign };
	char *end = equal_sign + strzlen(equal_sign);
	struct line line = { { equal_sign, end }, { "cmdarg", 0 } };

	parse_assignment(world, NULL, &buf, &line, vs_cmdargs);
}

static void world_init(struct world *world, char **envp)
{
	world->fstack.idx = 0;
	world->envp = envp;
	world->pat_rule_num = 0;

	vtable_init(&world->vtable);
	rtable_init(&world->rtable);

	for (; *envp; ++envp) {
		char *equal_sign;
		is_assignment(*envp, &equal_sign);
		parse_cmdarg_assignment(world, *envp, equal_sign);
	}
}

static int timegt(struct time *t1, struct time *t2)
{
	if (t1->sec > t2->sec)
		return 1;
	if (t1->sec == t2->sec)
		return t1->usec > t2->usec;
	return 0;
}

static void check_status(int status, char *prx)
{
	if (WIFEXITED(status)) {
		int ret = WEXITSTATUS(status);
		if (ret != 0) {
			error("%s: program exited with %d status",
					prx, ret);
		}
	} else if(WIFSIGNALED(status)) {
		error("%s: program received a signal %d",
				WTERMSIG(status), prx);
	} else {
		error("%s: unknown program status", prx);
	}
}

static void exec_recipe(struct world *world, struct full_rule *rule,
		int i)
{
	char *argv[] = { "/bin/sh", "-c", NULL, NULL };
	int ret;
	int status;
	struct line line = rule->rest->recipes->buf[i];

	struct buf *buf = eval(world, &line, rule);
	buf_put_silent_zero(buf);

	argv[2] = buf->start;
	flush(&stderr);
	ret = fork();

	if (ret == -1)
		syscall_error("fork");
	if (ret == 0) {
		struct str cmd = { buf->start, buf->cur };
		trim(&cmd);
		printf("%S\n", &cmd);
		execve("/bin/sh", argv, world->envp);

		perror("execve");
		flush(&stderr);
		exit(1);
	}
	wait4(ret, &status, 0, 0);
	check_status(status, "");
}

static void exec_recipes(struct world *world, struct full_rule *rule)
{
	int i;
	for (i = 0; i < rule->rest->recipes->len; ++i)
		exec_recipe(world, rule, i);
}

static int exists(char *path)
{
	return access(path, F_OK) == 0;
}

static int matches(struct str *pat, struct str *str,
		struct str *wildcard)
{
	char *tmp = pat->start;
	char *stmp = str->start;
	int rem;
	for (;*tmp != '%'; ++tmp, ++stmp) {
		if (*tmp != *stmp)
			return 0;
	}
	++tmp;

	rem = pat->end - tmp;
	if (rem > str->end - stmp)
		return 0;
	wildcard->start = stmp;
	wildcard->end = str->end - rem;
	return memeq(tmp, wildcard->end, rem);
}

static void heapbuf_init(struct buf *buf)
{
	buf->start = malloc(1);
	buf->cur = buf->start;
	buf->end = buf->start + 1;
}

static void heapbuf_putchar(struct buf *buf, char c)
{
	if (buf->cur == buf->end) {
		++buf->end;
		realloc(buf->start, buf->end - buf->start);
	}
	*buf->cur = c;
	++buf->cur;
}

static void heapbuf_puts(struct buf *buf, struct str *str)
{
	char *tmp;
	for (tmp = str->start; tmp != str->end; ++tmp)
		heapbuf_putchar(buf, *tmp);
}

static void subst_pat(struct str *dest, struct str *pat,
		struct str *wildcard)
{
	struct buf buf;
	char *tmp;
	heapbuf_init(&buf);
	for (tmp = pat->start; tmp != pat->end; ++tmp) {
		if (*tmp != '%')
			heapbuf_putchar(&buf, *tmp);
		else
			heapbuf_puts(&buf, wildcard);
	}
	dest->start = buf.start;
	dest->end = buf.cur;
	heapbuf_putchar(&buf, 0);
}

static struct rule_body *construct_prereqs(struct full_rule *patrule,
	struct str *wildcard)
{
	struct rule_body *newbody = malloc(sizeof(*newbody));
	struct strbuf *prereqs = &newbody->prereqs;
	int i;

	newbody->normal_prereq_count = patrule->rest->normal_prereq_count;
	newbody->recipes = patrule->rest->recipes;

	prereqs->len = patrule->rest->prereqs.len;
	prereqs->buf = malloc(sizeof(*prereqs->buf) * prereqs->len);
	for (i = 0; i < prereqs->len; ++i) {
		subst_pat(&prereqs->buf[i], &patrule->rest->prereqs.buf[i],
			wildcard);
	}
	return newbody;
}

static void ccarena_grow(struct arena *a, int size)
{
	error("ccarena: no more space");
}

void prereqdup(struct arena *a, struct str *dest, struct str *src)
{
	int len = strlen(src);
	dest->start = amalloc(a, len + 1);
	dest->end = dest->start + len;
	memcpy(dest->start, src->start, len);
	*dest->end = 0;
}

static struct rule_body *create_copy(struct rule_body *rule_body)
{
	static struct arena ccarena;
	struct rule_body *tmp;
	struct strbuf *prereqs;
	int i;
	if (ccarena.start == NULL) {
		ccarena.start = ccarena.cur = mem_alloc(buf_size);
		ccarena.end = ccarena.start + buf_size;
		ccarena.grow = ccarena_grow;
	}
	tmp = amalloc(&ccarena, sizeof(*tmp));
	tmp->normal_prereq_count = rule_body->normal_prereq_count;
	tmp->recipes = rule_body->recipes;
	prereqs = &tmp->prereqs;
	prereqs->len = rule_body->prereqs.len;
	prereqs->buf =
		amalloc(&ccarena, sizeof(*prereqs->buf) * prereqs->len);

	for (i = 0; i < prereqs->len; ++i) {
		prereqdup(&ccarena, &prereqs->buf[i],
			&rule_body->prereqs.buf[i]);
	}
	/*printf(">>> Cur: %d\n", ccarena.cur - ccarena.start);*/
	return tmp;
}

static struct rule_body *find_body(struct world *world, struct str *target,
	int depth);

static struct rule_body *suitable_patrule(struct world *world, int idx,
	struct str *target, int depth)
{
	struct rule_body *tmp = NULL;
	struct rule_body *tmp_copy;
	struct str wildcard;
	int i;

	heap_offset_save();

	if (!matches(world->pat_rules[idx].target, target, &wildcard))
		goto failure;

	tmp = construct_prereqs(world->pat_rules + idx, &wildcard);

	for (i = 0; i < tmp->prereqs.len; ++i) {
		struct str *prereq = &tmp->prereqs.buf[i];
		struct rule_body *pbody;
		if (exists(prereq->start))
			continue;
		pbody = find_body(world, prereq, depth);
		if (pbody == NULL)
			goto failure;
	}
	tmp_copy = create_copy(tmp);
	/*printf(">>> Saving: %S\n", target);*/
	rtable_add(&world->rtable, target, 1, tmp_copy);
	heap_offset_remove();
	return tmp_copy;
failure:
	heap_offset_restore();
	return NULL;
}

static struct rule_body *find_body(struct world *world,
	struct str *target, int depth)
{
	int i;
	struct rule_body *tmp = NULL;
	/*printf("FB: %S\n", target);*/
	if (rtable_find(&world->rtable, target, &tmp) == 1)
		return tmp;

	if (depth >= find_body_max_depth)
		return NULL;

	for (i = 0; i < world->pat_rule_num; ++i) {
		tmp = suitable_patrule(world, i, target, depth + 1);
		if (tmp != NULL)
			break;
	}
	if (tmp == NULL)
		rtable_add(&world->rtable, target, 1, NULL);
	return tmp;
}

struct target_info {
	struct time mtime;
	int exists;
};

static int get_mtime(struct str *str, struct time *time)
{
	int ret;
	struct stat st;

	ret = stat(str->start, &st);
	/*printf("Time: %s %d\n", str->start, ret);*/
	if (ret == -1) {
		if (errno == ENOENT) {
			return 0;
		}
		syscall_error(str->start);
	}
	*time = st.mtime;
	return 1;
}

static void tinfo_get(struct target_info *info, struct str *str)
{
	info->exists = get_mtime(str, &info->mtime);
}

static int exec_target(struct world *world, struct str *target,
	struct target_info *info);

struct pstatus {
	struct time time;
	struct str *prereq;
};

static int exec_prereqs(struct world *world, struct full_rule *rule,
	struct pstatus *pstatus, struct target_info *info)
{
	int i;
	int flag = 0;
	struct target_info pinfo;

	*pstatus = (struct pstatus) { { 0, 0 }, NULL };

	for (i = 0; i < rule->rest->prereqs.len; ++i) {
		int ret, is_oo;
		struct str *prereq = &rule->rest->prereqs.buf[i];
		tinfo_get(&pinfo, prereq);
		ret = exec_target(world, prereq, &pinfo);
		is_oo = i >= rule->rest->normal_prereq_count;
		if (ret) {
			if (flag == 0)
				pstatus->prereq = prereq;
			flag = 1;
		}
		if (flag == 0 && !is_oo && timegt(&pinfo.mtime, &pstatus->time)) {
			pstatus->time = pinfo.mtime;
			pstatus->prereq = prereq;
		}
	}
	return flag;
}

static void print_reason(int debug, struct str *target, int flag,
	struct target_info *info, struct pstatus *ptime)
{

	if (debug == 0)
		return;
	if (!info->exists) {
		printf("%s%S did not exist\n", debug_prx, target);
	} else if (flag) {
		printf("%s%S(%U.%U) by %S\n", debug_prx, target,
				info->mtime.sec, info->mtime.usec,
				ptime->prereq);
	} else {
		printf("%s%S(%U.%U) <- %S(%U.%U)\n", debug_prx, target,
				info->mtime.sec, info->mtime.usec,
				ptime->prereq, ptime->time.sec,
				ptime->time.usec);
	}
}

static void print_new_time(int debug, struct str *target)
{
	struct time time;
	if (debug == 0)
		return;
	if (get_mtime(target, &time)) {
		printf("%sUpdated time %S: %U.%U\n", debug_prx, target,
			time.sec, time.usec);
	} else {
		printf("%s%S was not created\n", debug_prx, target);
	}
}

static int exec_target(struct world *world, struct str *target,
	struct target_info *info)
{
	struct rule_body *prule = find_body(world, target, 0);
	struct full_rule rule = { target, prule };
	int flag = 0;
	struct pstatus pstatus;
	int prereq_later;

	/*printf("EXEC: %S\n", target);*/
	if (prule == NULL) {
		if (info->exists) {
			return 0;
		} else {
			error("%S: don't know what to do with the target",
				target);
		}
	}
	flag = exec_prereqs(world, &rule, &pstatus, info);

	prereq_later = timegt(&pstatus.time, &info->mtime);
	if (flag || !info->exists || prereq_later) {
		print_reason(world->debug_mode, target, flag, info,
			&pstatus);
		exec_recipes(world, &rule);
		print_new_time(world->debug_mode, target);
		return 1;
	}
	return 0;
}

static void exec(struct world *world)
{
	struct target_info info;
	if (strempty(&world->target)) {
		printf("nothing to be done\n");
		hexit(0);
	}
	tinfo_get(&info, &world->target);
	exec_target(world, &world->target, &info);
}

static void parse_cmdargs(struct world *world, char **argv)
{
	char *makefile = "Makefile";
	char *target = NULL;
	char *equal_sign;

	++argv;
	for (; argv[0]; ++argv) {
		if (argv[0][0] == '-') {
			if (argv[0][1] == 'f' && argv[0][2] == 0) {
				if (argv[1] == NULL)
					error("-f: missing file name");
				makefile = argv[1];
				++argv;
			} else if (argv[0][1] == 'C' && argv[0][2] == 0) {
				if (argv[1] == NULL)
					error("-C: missing dir");
				if (chdir(argv[1]) == -1)
					syscall_error(argv[1]);
				++argv;
			} else if (argv[0][1] == 'd' && argv[0][2] == 0) {
				world->debug_mode = 1;
			} else {
				error("%s: unknown flag", argv[0]);
			}
		} else if (is_assignment(argv[0], &equal_sign)) {
			parse_cmdarg_assignment(world, argv[0],
				equal_sign);
		} else {
			if (target)
				error("%s: target already provided");
			target = argv[0];
		}
	}
	world->target = target ? STR(target) : CSTR("");
	fstack_add(&world->fstack, makefile, NULL);
}

static void print_program_time(int debug)
{
	struct rusage rusage;
	if (!debug)
		return;
	if (getrusage(RUSAGE_SELF, &rusage) == -1)
		syscall_error("rusage");
	printf("%s: user time: %U.%3U, sys time: %U.%3U\n", progname,
			rusage.utime.sec, rusage.utime.msec / 1000,
			rusage.stime.sec, rusage.stime.msec / 1000);
}

int main(int argc, char **argv, char **envp)
{
	struct world world;

	world_init(&world, envp);
	parse_cmdargs(&world, argv);

	parse(&world);

	exec(&world);
	print_program_time(world.debug_mode);
	return 0;
}