Musl make

5 files changed, 2833 insertions, 82 deletions

diff --git a/tools/TODO b/tools/TODO
new file mode 100644
index 0000000..6f21b0c
--- /dev/null
+++ b/tools/TODO
@@ -0,0 +1,4 @@
+* Remove coping: str2 for vtable search, str_n for variable values
+* Cache variable values
+* Cache rule execution status (file status)
+* use execvp whenever possible
diff --git a/tools/common.c b/tools/common.c
index 00f7d3c..8156bec 100644
--- a/tools/common.c
+++ b/tools/common.c
@@ -50,6 +50,16 @@ int open(char *fname, int flags, int mode)
 				flags|o_largefile, mode));
 }
 
+int chdir(char *path)
+{
+	return sysret(__syscall1(__NR_chdir, (long)path));
+}
+
+int getdents64(int fd, char *buf, int size)
+{
+	return sysret(__syscall3(__NR_getdents64, fd, (long)buf, size));
+}
+
 int stat(char *fname, struct stat *st)
 {
 	return sysret(__syscall2(__NR_stat, (long)fname, (long)st));
@@ -60,6 +70,21 @@ int fstat(int fd, struct stat *st)
 	return sysret(__syscall2(__NR_fstat, (long)fd, (long)st));
 }
 
+int access(char *path, int mode)
+{
+	return sysret(__syscall2(__NR_access, (long)path, mode));
+}
+
+int dup2(int oldfd, int newfd)
+{
+	return sysret(__syscall2(__NR_dup2, oldfd, newfd));
+}
+
+int pipe(int *fds)
+{
+	return sysret(__syscall1(__NR_pipe, (long)fds));
+}
+
 int close(int fd)
 {
 	return sysret(__syscall1(__NR_close, fd));
@@ -69,7 +94,7 @@ void *mmap(char *addr, unsigned long length, int prot, int flags, int fd,
 		unsigned long offset)
 {
 	return (void*)sysret(__syscall6(__NR_mmap, (long)addr, length,
-				prot, flags, fd, offset));
+			prot, flags, fd, offset));
 }
 
 int munmap(char *addr, int length)
@@ -79,11 +104,72 @@ int munmap(char *addr, int length)
 
 #define MREMAP_MAYMOVE 1
 
-int mremap(void *old_addr, unsigned long old_size, unsigned long new_size,
+void *mremap(void *old_addr, unsigned long old_size, unsigned long new_size,
 		int flags, void *new_addr)
 {
-	return sysret(__syscall5(__NR_mremap, (long)old_addr, old_size,
-				new_size, flags, (long)new_addr));
+	return (void *)sysret(__syscall5(__NR_mremap, (long)old_addr,
+			old_size, new_size, flags, (long)new_addr));
+}
+
+int fork()
+{
+	return sysret(__syscall0(__NR_fork));
+}
+
+int wait4(int pid, int *wstatus, int options, void *rusage)
+{
+	return sysret(__syscall6(__NR_wait4, pid, (long)wstatus, options,
+		(long)rusage, 0, 0));
+}
+
+int execve(char *path, char **argv, char **envp)
+{
+	return sysret(__syscall3(__NR_execve, (long)path, (long)argv,
+		(long)envp));
+}
+
+int getrusage(int who, struct rusage *rusage)
+{
+	return sysret(__syscall2(__NR_getrusage, who, (long)rusage));
+}
+
+enum {
+	dirbuf_size = 16 * 1024
+};
+
+int opendir(struct dir *dir, char *path)
+{
+	dir->fd = open(path, O_RDONLY|O_DIRECTORY, 0);
+	if (dir->fd == -1)
+		return 0;
+
+	dir->buf = malloc(dirbuf_size);
+	dir->cur = dir->buf;
+	dir->end = dir->cur;
+	dir->path = path;
+	return 1;
+}
+
+void closedir(struct dir *dir)
+{
+	close(dir->fd);
+}
+
+struct dirent *readdir(struct dir *dir)
+{
+	struct dirent *tmp;
+	if (dir->cur == dir->end) {
+		int r = getdents64(dir->fd, dir->buf, dirbuf_size);
+		if (r == -1)
+			syscall_error(dir->path);
+		if (r == 0)
+			return NULL;
+		dir->cur = dir->buf;
+		dir->end = dir->buf + r;
+	}
+	tmp = (struct dirent *)dir->cur;
+	dir->cur += tmp->dsize;
+	return tmp;
 }
 
 int strzlen(char *s)
@@ -94,6 +180,14 @@ int strzlen(char *s)
 	return s - sc;
 }
 
+struct str *debug2str(char *s)
+{
+	static struct str str;
+	str.start = s;
+	str.end = str.start + strzlen(s);
+	return &str;
+}
+
 int strzeq(char *s1, char *s2)
 {
 	for (; *s1 && *s1 == *s2; ++s1, ++s2)
@@ -104,15 +198,32 @@ int strzeq(char *s1, char *s2)
 int streq(struct str *s1, struct str *s2)
 {
 	int i;
+	char * restrict tmp1, * restrict tmp2;
 	if (s1->end - s1->start != s2->end - s2->start)
 		return 0;
+
+	tmp1 = s1->start;
+	tmp2 = s2->start;
 	for (i = 0; s1->start + i < s1->end; ++i) {
-		if (s1->start[i] != s2->start[i])
+		if (tmp1[i] != tmp2[i])
 			return 0;
 	}
 	return 1;
 }
 
+int strge(struct str *s1, struct str *s2)
+{
+	char *tmp1 =s1->start, *tmp2 = s2->start;
+	for (;; ++tmp1, ++tmp2) {
+		if (tmp1 == s1->end)
+			return tmp2 == s2->end;
+		if (tmp2 == s2->end)
+			return 1;
+		if (*tmp1 != *tmp2)
+			return *tmp1 > *tmp2;
+	}
+}
+
 void memmove(char *dest, char *src, int len)
 {
 	int i;
@@ -125,11 +236,11 @@ void memmove(char *dest, char *src, int len)
 	}
 }
 
-void memcpy(void *dest, void *src, int len)
+void memcpy(void * restrict dest, void * restrict src, int len)
 {
-	int i;
 	char *d = dest;
 	char *s = src;
+	int i;
 	for (i = 0; i < len; ++i)
 		d[i] = s[i];
 }
@@ -141,6 +252,18 @@ void memset(void *dest, char c, int len)
 		*tmp = c;
 }
 
+int memeq(void *m1, void *m2, int len)
+{
+	char *s1 = m1;
+	char *s2 = m2;
+	int i;
+	for (i = 0; i < len; ++i) {
+		if (s1[i] != s2[i])
+			return 0;
+	}
+	return 1;
+}
+
 #define E(e, s) [e] = s,
 
 char *estrings[256] = {
@@ -156,12 +279,6 @@ void perror(char *s)
 	eprintf("%s: %s\n", s, estrings[idx]);
 }
 
-void syscall_error(char *fname)
-{
-	perror(fname);
-	hexit(1);
-}
-
 enum {
 	buflen = 32 * 1024
 };
@@ -175,9 +292,12 @@ struct iobuf {
 struct iobuf stdout = { 1 };
 struct iobuf stderr = { 2 };
 
-static void flush(struct iobuf *buf)
+void flush(struct iobuf *buf)
 {
-	int ret = write(buf->fd, buf->buf, buf->len);
+	int ret;
+	if (buf->len == 0)
+		return;
+	ret = write(buf->fd, buf->buf, buf->len);
 	if (ret != buf->len) {
 		write(2, _S("some stdout/stderr error\n"));
 		exit(3);
@@ -185,6 +305,12 @@ static void flush(struct iobuf *buf)
 	buf->len = 0;
 }
 
+void syscall_error(char *fname)
+{
+	perror(fname);
+	hexit(1);
+}
+
 static void putchar(struct iobuf *buf, char c)
 {
 	if (buf->len == buflen)
@@ -204,7 +330,7 @@ void hexit(int code)
 }
 
 static void print_int(struct iobuf *buf, int nsigned, int byte4,
-		unsigned long n)
+		unsigned long n, int size)
 {
 	char tmpbuf[64];
 	char *p = tmpbuf;
@@ -238,6 +364,10 @@ static void print_int(struct iobuf *buf, int nsigned, int byte4,
 		*p = k % 10 + '0';
 		++p;
 	}
+	if (p - tmpbuf < size) {
+		for (; p < tmpbuf + size; ++p)
+			*p = '0';
+	}
 	for (--p;; --p) {
 		putchar(buf, *p);
 		if (p == tmpbuf)
@@ -258,30 +388,38 @@ void print_str(struct iobuf *buf, struct str *s)
 		putchar(buf, *tmp);
 }
 
-static void format(struct iobuf *buf, char c, va_list vl)
+static void format(struct iobuf *buf, char c, int size, va_list vl)
 {
 	switch(c) {
 		unsigned long arg;
 	case '%':
+		if (size != -1)
+			goto size_err;
 		putchar(buf, '%');
 		break;
 	case 'd':
 	case 'u':
 		arg = va_arg(vl, unsigned int);
-		print_int(buf, c == 'd', 1, arg);
+		print_int(buf, c == 'd', 1, arg, size);
 		break;
 	case 'D':
 	case 'U':
 		arg = va_arg(vl, unsigned long);
-		print_int(buf, c == 'D', 0, arg);
+		print_int(buf, c == 'D', 0, arg, size);
 		break;
 	case 's':
+		if (size != -1)
+			goto size_err;
 		print_strz(buf, va_arg(vl, char*));
 		break;
 	case 'S':
+		if (size != -1)
+			goto size_err;
 		print_str(buf, va_arg(vl, struct str *));
 		break;
 	case 'c':
+		if (size != -1)
+			goto size_err;
 		arg = va_arg(vl, int);
 		putchar(buf, arg);
 		break;
@@ -289,23 +427,35 @@ static void format(struct iobuf *buf, char c, va_list vl)
 		write(2, _S("printf: unexpected format option \n"));
 		hexit(2);
 	}
+	return;
+size_err:
+	write(2, _S("printf: %c: size not applicable\n"));
+	hexit(2);
 }
 
 static void __printf(struct iobuf *buf, char *s, va_list vl)
 {
 	for (; *s; ++s) {
 		if (*s == '%') {
-			if (s[1] == 0) {
-				write(2, _S("printf: nothing comes after '%'"));
-				hexit(2);
+			int size = -1;
+			if (s[1] == 0)
+				goto zero_err;
+			if (s[1] >= '0' && s[1] <= '9') {
+				size = s[1] - '0';
+				++s;
 			}
-			format(buf, s[1], vl);
+			if (s[1] == 0)
+				goto zero_err;
+			format(buf, s[1], size, vl);
 			++s;
 		} else  {
 			putchar(buf, *s);
 		}
 	}
 	return;
+zero_err:
+	write(2, _S("printf: nothing specifier after '%'"));
+	hexit(2);
 }
 
 void printf(char *fmt, ...)
@@ -318,8 +468,6 @@ void printf(char *fmt, ...)
 
 void evprintf(char *fmt, va_list vl)
 {
-	print_strz(&stderr, progname);
-	print_strz(&stderr, ": ");
 	__printf(&stderr, fmt, vl);
 }
 
@@ -331,38 +479,56 @@ void eprintf(char *fmt, ...)
 	va_end(vl);
 }
 
-/* Memory management */
+void error(char *fmt, ...)
+{
+	va_list vl;
+	va_start(vl, fmt);
 
-struct mem_buffer {
-	char *cur, *end;
-	char *saved;
-};
+	print_strz(&stderr, progname);
+	print_strz(&stderr, ": ");
+	evprintf(fmt, vl);
+
+	va_end(vl);
+	print_strz(&stderr, "\n");
+	hexit(1);
+}
+
+/* Memory management */
 
-static struct mem_buffer mem_buf;
+struct heap heap;
 
-static void mem_buffer_init()
+void heap_offset_save()
 {
-	mem_buf.cur = mem_buf.end = brk(NULL);
-	mem_buf.saved = NULL;
+	if (heap.snum == heap_saves_max)
+		error("heap: offset stack is full");
+	heap.saved[heap.snum] = heap.a.cur;
+	++heap.snum;
 }
 
-void save_heap_offset()
+void heap_offset_remove()
 {
-	if (mem_buf.saved != NULL) {
-		eprintf("mem_buffer: offset already saved\n");
-		hexit(2);
+	if (heap.snum == 0) {
+		error("heap: offset stack is empty");
 	}
-	mem_buf.saved = mem_buf.cur;
+	--heap.snum;
 }
 
-void restore_heap_offset()
+void heap_offset_restore()
 {
-	if (mem_buf.saved == NULL) {
-		eprintf("mem_buffer: no offset was saved\n");
-		hexit(2);
-	}
-	mem_buf.cur = mem_buf.saved;
-	mem_buf.saved = NULL;
+	if (heap.snum == 0)
+		error("mem_buffer: no offset was saved\n");
+	heap.a.cur = heap.saved[heap.snum - 1];
+	--heap.snum;
+	heap.last_alloc = NULL;
+}
+
+void *mem_alloc(int size)
+{
+	void *tmp = mmap(NULL, size, PROT_READ|PROT_WRITE,
+		MAP_PRIVATE|MAP_ANON, -1, 0);
+	if (tmp == (void*)-1)
+		syscall_error("mmap");
+	return tmp;
 }
 
 static int get_alignment(int n)
@@ -378,7 +544,7 @@ static int get_alignment(int n)
 	return 1;
 }
 
-static void mem_buf_grow(int size)
+static void heap_grow(struct arena *a, int size)
 {
 	char *tmp;
 	if (size < 128*1024) {
@@ -388,31 +554,58 @@ static void mem_buf_grow(int size)
 		size &= -4096;
 	}
 	/*printf("Growing (%d)\n", size);*/
-	tmp = brk(mem_buf.end + size);
-	if (tmp == mem_buf.end) {
-		eprintf("mem_buf: unable to allocate memory\n");
-		hexit(1);
-	}
-	mem_buf.end = tmp;
+	tmp = brk(a->end + size);
+	if (tmp == a->end)
+		error("heap: unable to grow");
+	a->end = tmp;
+}
+
+static void heap_init()
+{
+	heap.a.start = heap.a.cur = heap.a.end = brk(NULL);
+	heap.a.grow = heap_grow;
+
+	heap.snum = 0;
+	heap.last_alloc = NULL;
 }
 
 #define ALIGN(v, align) \
 	(void*)(((unsigned long)(v) + (align) - 1ul) & -(align))
 
-void *malloc(int size)
+void *amalloc(struct arena *a, int size)
 {
 	int align = get_alignment(size);
-	char *tmp = ALIGN(mem_buf.cur, align);
-	int diff = tmp + size - mem_buf.end;
+	char *tmp = ALIGN(a->cur, align);
+	int diff = tmp + size - a->end;
 
 	if (diff > 0)
-		mem_buf_grow(diff);
+		a->grow(a, diff);
+
+	a->cur = tmp + size;
+
+	return tmp;
+}
 
-	mem_buf.cur = tmp + size;
+void *malloc(int size)
+{
+	void *tmp = amalloc(&heap.a, size);
+	heap.last_alloc = tmp;
 	return tmp;
 }
 
-int main(int argc, char **argv, char **envp);
+void realloc(void *p, int newsize)
+{
+	int diff;
+	if (heap.last_alloc != p)
+		error("realloc: not a previously allocated region");
+	diff = heap.last_alloc + newsize - heap.a.end;
+	if (diff > 0)
+		heap.a.grow(&heap.a, diff);
+
+	heap.a.cur = heap.last_alloc + newsize;
+}
+
+extern int main(int argc, char **argv, char **envp);
 
 void _start_c(unsigned long *p)
 {
@@ -421,7 +614,7 @@ void _start_c(unsigned long *p)
 	char **envp = argv + argc + 1;
 
 	progname = argv[0];
-	mem_buffer_init();
+	heap_init();
 
 	hexit(main(argc, argv, envp));
 }
diff --git a/tools/common.h b/tools/common.h
index 43e2dda..4ca27bd 100644
--- a/tools/common.h
+++ b/tools/common.h
@@ -5,24 +5,34 @@
 
 #include <stdarg.h>
 
+extern int main(int argc, char **argv, char **envp);
+
 #define NULL ((void *)0)
-#define _S(s) s, (sizeof(s) - 1)
-#define CSTR(s) ((struct str) { s, s + sizeof(s) - 1 })
-#define STR(s) ((struct str) { s, s + strzlen(s) })
+#define _S(s) (s), (sizeof(s) - 1)
+#define CSTR(s) ((struct str) { (s), (s) + sizeof(s) - 1 })
+#define STR(s) ((struct str) { (s), (s) + strzlen(s) })
+
+struct str *debug2str(char *s);
 
 struct str {
 	char *start;
 	char *end;
 };
 
+enum {
+	heap_saves_max = 16
+};
+
 extern int errno;
 extern char *progname;
 
 void exit(int code);
+int chdir(char *path);
 int read(int fd, char *buf, int len);
 int write(int fd, char *buf, int len);
 
 #define O_RDONLY        0
+#define O_DIRECTORY	0200000
 
 int open(char *fname, int flags, int mode);
 
@@ -60,6 +70,34 @@ struct stat {
 int stat(char *fname, struct stat *st);
 int fstat(int fd, struct stat *st);
 
+struct dir {
+	int fd;
+
+	char *buf;
+	char *cur;
+	char *end;
+
+	char *path;
+};
+
+struct dirent {
+	unsigned long inode;
+	unsigned long offset;
+	unsigned short dsize;
+	unsigned char type;
+	char name[1];
+};
+
+int opendir(struct dir *dir, char *path);
+struct dirent *readdir(struct dir *dir);
+void closedir(struct dir *dir);
+
+#define F_OK 0
+
+int access(char *path, int mode);
+
+int dup2(int oldfd, int newfd);
+int pipe(int *fds);
 int close(int fd);
 
 #define MAP_PRIVATE    0x02
@@ -76,8 +114,46 @@ int munmap(char *addr, int length);
 
 #define MREMAP_MAYMOVE 1
 
-int mremap(void *old_addr, unsigned long old_size, unsigned long new_size,
-		int flags, void *new_addr);
+void *mremap(void *old_addr, unsigned long old_size,
+		unsigned long new_size, int flags, void *new_addr);
+
+int fork();
+
+#define WIFEXITED(s) (!WTERMSIG(s))
+#define WEXITSTATUS(s) (((s) >> 8) & 0xff)
+#define WIFSIGNALED(s) (((s) & 0xffff) -1 < 0xff)
+#define WTERMSIG(s) ((s) & 0x7f)
+
+int wait4(int pid, int *wstatus, int options, void *rusage);
+int execve(char *path, char **argv, char **envp);
+
+struct timeval {
+	unsigned long long sec;
+	unsigned long long msec;
+};
+
+struct rusage {
+	struct timeval utime;
+	struct timeval stime;
+	long	maxrss;
+	long	ixrss;
+	long	idrss;
+	long	isrss;
+	long	minflt;
+	long	majflt;
+	long	nswap;
+	long	inblock;
+	long	oublock;
+	long	msgsnd;
+	long	msgrcv;
+	long	nsignals;
+	long	nvcsw;
+	long	nivcsw;
+};
+
+#define RUSAGE_SELF 0
+
+int getrusage(int who, struct rusage *rusage);
 
 void hexit(int code);
 
@@ -90,19 +166,52 @@ void print_str(struct iobuf *buf, struct str *s);
 void printf(char *fmt, ...);
 void eprintf(char *fmt, ...);
 void evprintf(char *fmt, va_list vl);
+void error(char *fmt, ...);
+
+struct arena;
+
+typedef void arena_grow_func(struct arena *a, int size);
+
+struct arena {
+	char *start;
+	char *cur;
+	char *end;
 
-void save_heap_offset();
-void restore_heap_offset();
+	arena_grow_func *grow;
+};
+
+struct heap {
+	struct arena a;
+
+	char *saved[heap_saves_max];
+	int snum;
+
+	char *last_alloc;
+};
+
+extern struct heap heap;
+
+void heap_offset_save();
+void heap_offset_remove();
+void heap_offset_restore();
+
+void *mem_alloc(int size);
+void *amalloc(struct arena *a, int size);
 void *malloc(int size);
+void realloc(void *p, int newsize);
 
 int strzlen(char *s);
 int strzeq(char *s1, char *s2);
 
 int streq(struct str *s1, struct str *s2);
+int strge(struct str *s1, struct str *s2);
+void flush(struct iobuf *buf);
 void perror(char *s);
 void syscall_error(char *fname);
 
 void memmove(char *dest, char *src, int len);
-void memcpy(void *dest, void *src, int len);
+void memcpy(void *restrict dest, void *restrict src, int len);
 void memset(void *dest, char c, int len);
+int memeq(void *m1, void *m2, int len);
+
 #endif
diff --git a/tools/make.c b/tools/make.c
new file mode 100644
index 0000000..0b1f704
--- /dev/null
+++ b/tools/make.c
@@ -0,0 +1,2455 @@
+#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
+};
+
+const char *debug_prx = ">>> ";
+
+struct conf {
+	char *target;
+	char *makefile;
+	int debug_mode;
+};
+
+struct line {
+	int linenum;
+	struct str str;
+};
+
+struct buf {
+	char *start;
+	char *end;
+	char *cur;
+};
+
+struct augstr {
+	struct str str;
+	int auxval;
+};
+
+struct strbuf {
+	struct augstr *buf;
+	int len;
+	int size;
+};
+
+struct rule_body {
+	struct strbuf prereqs;
+	int normal_prereq_count;
+
+	struct strbuf *recipes;
+};
+
+struct full_rule {
+	struct str *target;
+	struct rule_body *rest;
+};
+
+struct rule_details {
+	struct rule_body *body;
+	struct strbuf targets;
+	int patrule;
+	int lineno;
+};
+
+struct vt_cell {
+	struct str vname;
+	struct str value;
+};
+
+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 world {
+	char *makefile;
+	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;
+	int linenum;
+	struct full_rule *rule;
+
+	struct buf *mainbuf;
+	struct buf *auxbuf;
+	struct world *world;
+};
+
+static void lerror(int line, char *str, ...)
+{
+	va_list vl;
+
+	eprintf("%s: line %d: ", progname, 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)
+{
+	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 (cell->vname.start == NULL) {
+		if (alloc_name)
+			strdup(&cell->vname, key, 0);
+		else
+			cell->vname = *key;
+	}
+	cell->value = *value;
+}
+
+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 void parse_cmdargs(struct conf *conf, char **argv)
+{
+	++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");
+				conf->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) {
+				conf->debug_mode = 1;
+			} else {
+				error("%s: unknown flag", argv[0]);
+			}
+		} else {
+			if (conf->target)
+				error("%s: target already provided");
+			conf->target = argv[0];
+		}
+	}
+	if (conf->makefile == NULL)
+		conf->makefile = "Makefile";
+}
+
+static char *mmap_makefile(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;
+
+	tmp = mmap(NULL, st.size + 1, PROT_READ|PROT_WRITE,
+		MAP_PRIVATE, fd, 0);
+	if (tmp == (void*)-1)
+		goto syserr;
+	if (close(fd) == -1)
+		goto syserr;
+	return tmp;
+syserr:
+	syscall_error(fname);
+	return NULL; /* unreachable */
+}
+
+static int readline(char **makefile, struct line *line)
+{
+	static int linenum = 1;
+	char *tmp = *makefile;
+	char *marker = NULL;
+
+	for (; *tmp && *tmp != '\n'; ++tmp) {
+		if (*tmp == '#' && marker == NULL)
+			marker = tmp;
+		else if (tmp[0] == '\\' && tmp[1] == '\n') {
+			tmp[0] = tmp[1] = ' ';
+			++tmp;
+			++linenum;
+		}
+	}
+
+	if (*tmp == 0) {
+		if (tmp == *makefile)
+			return 0;
+		else
+			error("last line missing '\\n'");
+	}
+
+	*tmp = 0;
+	line->linenum = linenum;
+	++linenum;
+	line->str.start = *makefile;
+	line->str.end = marker ? marker : tmp;
+	*makefile = tmp + 1;
+
+	return 1;
+}
+
+static int nextline_starts_with_tab(char *file)
+{
+	return file[0] == '\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(int line, struct str *str)
+{
+	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;
+		}
+	}
+	lerror(line, "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 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,
+		int line)
+{
+	if (word->end == all->end)
+		return;
+	lerror(line, "(%S): variable name must be a single word", all);
+}
+
+static void parse_subref(struct eprofile *prof, struct str *vname,
+		struct str *all, int line)
+{
+	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)
+		lerror(line, "%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, int line,
+	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)
+		lerror(line, "invalid symbol during first word parsing");
+	first_word = (struct str) { str->start, wend };
+
+	if (wend != str->end && *wend == ':') {
+		parse_subref(prof, &first_word, str, line);
+		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, line);
+	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].str);
+}
+
+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].str);
+		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, int linenum)
+{
+	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:
+	lerror(linenum, "%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->linenum);
+
+	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->linenum);
+
+	if (!arg_is_single_word(args))
+		lerror(aux->linenum, "%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, str, NULL))
+			return ret_when_matches;
+	}
+	return !ret_when_matches;
+}
+
+static void sbuf_init(struct strbuf *buf);
+static void sbuf_save(struct strbuf *buf, struct str *str, int aux);
+
+static void collect_words(struct strbuf *buf, struct str *words)
+{
+	sbuf_init(buf);
+
+	for (;;) {
+		struct str word;
+		int ret = extract_word(words, &word);
+		if (ret == 0)
+			break;
+		sbuf_save(buf, &word, -1);
+	}
+}
+
+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->linenum);
+
+	heap_offset_save();
+	collect_words(&pats, args);
+	filter_words(args + 1, &pats, aux, mode);
+	heap_offset_restore();
+}
+
+static void merge(struct augstr *to, struct augstr *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].str, &from[i].str)) {
+			to[k].str = from[i].str;
+			++i;
+		} else {
+			to[k].str = from[j].str;
+			++j;
+		}
+	}
+	if (i < mid) {
+		for (; i < mid; ++i, ++k)
+			to[k].str = from[i].str;
+	} else {
+		for (; j < n; ++j, ++k)
+			to[k].str = from[j].str;
+	}
+}
+
+static void mergesort(struct augstr *array, struct augstr *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 augstr *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 augstr *array = words->buf;
+	for (i = 0, j = 0; i < words->len; ++i) {
+		if (j > 0 && streq(&array[i].str, &array[j-1].str))
+			continue;
+		array[j].str = array[i].str;
+		++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->linenum);
+	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].str);
+	}
+
+	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->linenum);
+	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/dash", "-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->linenum);
+
+	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:
+	lerror(aux->linenum, "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->linenum);
+
+	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:
+	lerror(aux->linenum, "patsubst: from/to must be single words");
+no_wildcard_err:
+	lerror(aux->linenum, "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;
+	int linenum;
+
+	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, int line)
+{
+	for (; *pat; ++pat) {
+		if (*pat == '*') {
+			char *sc;
+			for (sc = str; ; ++sc) {
+				if (__match(pat + 1, sc, line))
+					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)
+				lerror(line, "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, int line)
+{
+	char c = *pat->end;
+	int ret;
+
+	*pat->end = 0;
+
+	ret = __match(pat->start, s, line);
+
+	*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->linenum);
+		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,
+		int linenum)
+{
+	static struct pathbuf pbuf;
+	pbuf.limbs = 0;
+	pbuf.cur = pbuf.buf;
+	pbuf.add_space = add_space;
+	pbuf.dest = buf;
+	pbuf.linenum = linenum;
+
+	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->linenum);
+	for (;;) {
+		struct str word;
+		if (extract_word(&arg, &word) == 0)
+			break;
+		int ret = wexpand(aux->mainbuf, &word, !first,
+			aux->linenum);
+		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))
+		lerror(aux->linenum, "stray '$'");
+
+	if (*str->start == '(') {
+		char *end = find_cparent(aux->linenum, str);
+
+		++str->start;
+		estr = (struct str) { str->start, end };
+		str->start = end + 1;
+	} else {
+		estr = (struct str) { str->start, str->start + 1 };
+		++str->start;
+	}
+	parse_profile(&profile, &estr, aux->linenum, 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->linenum,
+		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);
+}
+
+static void set_single_var(struct vtable *vt, int mode, struct str *prefix,
+	struct str *vname,struct str *value, int alloc_name)
+{
+	static char localbuf[buf_static_size];
+	struct buf buf;
+	struct str tmp;
+
+	buf_static_init(buf, localbuf, buf_static_size);
+
+	if (prefix != NULL) {
+		make_full_vname(&buf, prefix, vname);
+		tmp = (struct str) { buf.start, buf.cur };
+	} else {
+		tmp = *vname;
+	}
+	if (mode == svmode_set) {
+		vtable_update(vt, &tmp, alloc_name, value);
+	} else {
+		struct str newval;
+		struct str *oldval = vtable_find(vt, &tmp);
+		if (oldval == NULL)
+			oldval = vtable_find(vt, vname);
+		str_combine(&newval, oldval, value);
+		vtable_update(vt, &tmp, alloc_name, &newval);
+	}
+}
+
+static void setvar(struct vtable *vt, int mode, struct strbuf *targets,
+		struct str *vname, struct str *value)
+{
+	trim(value);
+
+	if (targets != NULL) {
+		int i;
+		for (i = 0; i < targets->len; ++i) {
+			set_single_var(vt, mode, &targets->buf[i].str, vname, value, 1);
+		}
+	} else {
+		set_single_var(vt, mode, NULL, vname, value, 0);
+	}
+}
+
+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)) {
+		line->str.start += 2;
+		return;
+	}
+	lerror(line->linenum, "expected %c after %c", c,
+		line->str.start[0]);
+}
+
+static void parse_assignment(struct world *world, struct strbuf *targets,
+		struct buf *buf, struct line *line)
+{
+	struct str vname = { buf->start, buf->cur };
+
+	trim(&vname);
+	if (!valid_var_name(&vname)) {
+		lerror(line->linenum, "[%S]: invalid variable name",
+			&vname);
+	}
+	if (line->str.start[0] == '+') {
+		follows(line, '=');
+		setvar(&world->vtable, svmode_append, targets, &vname,
+				&line->str);
+	} else {
+		++line->str.start;
+		setvar(&world->vtable, svmode_set, targets, &vname,
+				&line->str);
+	}
+}
+
+static void sbuf_init(struct strbuf *buf)
+{
+	buf->size = 1;
+	buf->len = 0;
+	buf->buf = malloc(sizeof(*buf->buf) * buf->size);
+}
+
+static void sbuf_save(struct strbuf *buf, struct str *str, int aux)
+{
+	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].auxval = aux;
+	++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, int line)
+{
+	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;
+
+	sbuf_save(buf, &word, line);
+	return;
+err:
+	lerror(line, "%c: invalid target/prereq name symbol", *str->start);
+}
+
+static void parse_targets(struct strbuf *targets, struct buf *buf, int line)
+{
+	struct str str = { buf->start, buf->cur };
+	sbuf_init(targets);
+
+	for (;;) {
+		trim_front(&str);
+		if (strempty(&str))
+			break;
+		save_word(targets, &str, -1);
+	}
+	if (targets->len == 0)
+		lerror(line, "zero targets before ':'");
+}
+
+static void parse_prereqs(struct rule_body *rule, struct buf *buf)
+{
+	struct str str = { buf->start, buf->cur };
+	sbuf_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, -1);
+		++i;
+	}
+	rule->normal_prereq_count = normal == -1 ? i : normal;
+}
+
+static struct strbuf *parse_recipes(char **file)
+{
+	struct strbuf *tmp = malloc(sizeof(*tmp));
+	sbuf_init(tmp);
+
+	while (nextline_starts_with_tab(*file)) {
+		struct line line;
+		readline(file, &line);
+
+		trim(&line.str);
+		sbuf_save(tmp, &line.str, line.linenum);
+	}
+	return tmp;
+}
+
+static void save_first_target(struct world *world,
+		struct rule_details *rule)
+{
+	if (!strempty(&world->target) || rule->patrule ||
+		streq(&rule->targets.buf->str, &CSTR(".PRECIOUS")))
+	{
+		return;
+	}
+	world->target = rule->targets.buf->str;
+}
+
+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, int line)
+{
+	if (contains_char(&targets->buf[0].str, '%') == NULL)
+		return 0;
+	if (targets->len == 1)
+		return 1;
+	lerror(line, "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)
+		lerror(rule->lineno, "pattern rules limit reached");
+	world->pat_rules[world->pat_rule_num] = (struct full_rule) {
+		&rule->targets.buf[0].str,
+		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->body->recipes = parse_recipes(&world->makefile);
+
+	if (rule->patrule) {
+		add_patrule(world, rule);
+		return;
+	}
+
+	for (i = 0; i < rule->targets.len; ++i) {
+		if (streq(&rule->targets.buf[i].str, &CSTR(".PRECIOUS")))
+			continue;
+		rtable_add(&world->rtable, &rule->targets.buf[i].str, 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)
+		lerror(line->linenum, target_spec_in_patrules);
+	if (*line->str.start == ':')
+		lerror(line->linenum, "expected target-specific var");
+
+	parse_assignment(world, &rule->targets, buf, line);
+}
+
+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.lineno = line->linenum;
+
+	parse_targets(&rule.targets, buf, line->linenum);
+	rule.patrule = is_patrule(&rule.targets, line->linenum);
+
+	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 int parse_toplev(struct world *world)
+{
+	struct line line;
+	struct buf *buf;
+
+	if (!readline(&world->makefile, &line))
+		return 0;
+	buf = eval(world, &line, NULL);
+
+	if (strempty(&line.str)) {
+		struct str tmp = { buf->start, buf->cur };
+		trim(&tmp);
+		if (!strempty(&tmp))
+			lerror(line.linenum, "missing separator");
+	} else if (*line.str.start == ':') {
+		parse_rule(world, buf, &line);
+	} else {
+		parse_assignment(world, NULL, buf, &line);
+	}
+	return 1;
+}
+
+static void parse(struct world *world)
+{
+	while (parse_toplev(world))
+		;
+}
+
+static void world_init(struct world *world, struct conf *conf, char **envp)
+{
+	world->makefile = mmap_makefile(conf->makefile);
+	world->target = conf->target ? STR(conf->target) : CSTR("");
+	world->envp = envp;
+
+	world->pat_rule_num = 0;
+	world->debug_mode = conf->debug_mode;
+
+	vtable_init(&world->vtable);
+	rtable_init(&world->rtable);
+}
+
+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 augstr *astr = rule->rest->recipes->buf + i;
+	struct line line = { astr->auxval, astr->str };
+
+	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].str,
+			&patrule->rest->prereqs.buf[i].str, 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].str,
+			&rule_body->prereqs.buf[i].str);
+	}
+	/*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].str;
+		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;
+	/*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].str;
+		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");
+		hexit(0);
+	}
+	tinfo_get(&info, &world->target);
+	exec_target(world, &world->target, &info);
+}
+
+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;
+	struct conf conf = { NULL, NULL };
+
+	parse_cmdargs(&conf, argv);
+
+	world_init(&world, &conf, envp);
+	parse(&world);
+
+	exec(&world);
+	print_program_time(world.debug_mode);
+	return 0;
+}
diff --git a/tools/sed.c b/tools/sed.c
index fd60a07..c427acd 100644
--- a/tools/sed.c
+++ b/tools/sed.c
@@ -96,7 +96,6 @@ struct threadlist {
 
 	struct ins *ref;
 	struct node **presence_table;
-
 };
 
 struct input_buf {
@@ -117,16 +116,6 @@ struct compiled_command {
 static struct compiled_command command_buf[max_commands];
 static int command_num = 0;
 
-static void error(char *fmt, ...)
-{
-	va_list vl;
-	va_start(vl, fmt);
-	evprintf(fmt, vl);
-	va_end(vl);
-	print_strz(&stderr, "\n");
-	hexit(1);
-}
-
 static void inbuf_init()
 {
 	input_buf.start = input_buf.end = input_buf.buf;
@@ -818,6 +807,7 @@ static char **exec_threadlist(struct threadlist *clist,
 		struct threadlist *nlist, char c, char *offset)
 {
 	struct thread tmp;
+	struct thread tmp2;
 	while (threadlist_getfront(clist, &tmp)) {
 start:
 		switch(tmp.pc->opcode) {
@@ -847,7 +837,7 @@ start:
 			tmp.pc = tmp.pc->arg_labels[0];
 			goto start;
 		case op_split:
-			struct thread tmp2 = thread_copy(&tmp);
+			tmp2 = thread_copy(&tmp);
 			tmp2.pc = tmp.pc->arg_labels[1];
 			tmp.pc = tmp.pc->arg_labels[0];
 			threadlist_addfront(clist, tmp2);
@@ -888,9 +878,9 @@ static char **__regex_exec(struct regex_prog *prog, struct str *str)
 static char **regex_exec(struct regex_prog *prog, struct str *str)
 {
 	char **ret;
-	save_heap_offset();
+	heap_offset_save();
 	ret = __regex_exec(prog, str);
-	restore_heap_offset();
+	heap_offset_restore();
 	return ret;
 }