namespace std;
include rt, run;

// small helpers for strings, files, the clock and byte buffers. not part of the
// genome as declarations; its source is embedded. include it with: include std;
// syscall numbers (SYS_OPEN and the rest) live in the runtime.
// a character string has type char*, one character per word and a 0 at the end.
// the Bytes group takes packed byte strings (b"..."), whose
// type is bstr.
// the helpers are grouped in structs, and each is a static function, so it is
// called as std.Group.name(args): std.Text.itoa(n, buf), std.Host.now(),
// std.Buf.get(b, 0).
// the constructors arena(n) and bnew(n) and the argv helpers are plain
// functions, because an owned result has to carry its .u tag.

// ---- the command line and the environment ----

// argc and argv, envc and envp, as passed to main by c. a zc string is
// one character per word, so an array of them is char*[?]. libinit() fills
// these and the runtime calls it before main, if the program has one (an
// image built by build_image, or a check-mode document, does not).

// the number of command line arguments, set by libinit().
int argc;
// the command line arguments, one string each. argv[0] is the program path,
// or <eval> when the source came from stdin.
char*[?] argv;
// the number of environment entries, set by libinit().
int envc;
// the environment, one NAME=value string per entry, set by libinit().
char*[?] envp;

// one entry of a vector syscall, as a fresh string, or 0 past the end.
//   op: the syscall that fetches an entry (SYS_ARG or SYS_ENV)
//   i: which entry
//   returns: the entry, owned by the caller; 0 when there is no entry i
char*.u argstr(int op, int i) {
	int n = rt.syscall(op, i, 0, 0);
	char* s;
	if (n < 0) return 0;
	s = rt.new(n + 1);
	rt.syscall(op, i, s, n + 1);
	return s;
}

// every entry of a vector syscall, in order.
//   cntop: the syscall that counts the entries (SYS_ARGC or SYS_ENVC)
//   stop: the syscall that fetches one (SYS_ARG or SYS_ENV)
//   returns: a new array of the strings, owned by the caller
char*[?].u argsvec(int cntop, int stop) {
	int n = rt.syscall(cntop, 0, 0, 0), i = 0;
	char*[?] a = rt.new(char*[?], 0);
	while (i < n) { push(a, argstr(stop, i)); i++; }
	return a;
}

// reads the command line and the environment into argc, argv, envc and envp.
// it stays a plain function: the compiler looks it up by name.
//   returns: 0
int libinit() {
	argv = argsvec(rt.SYS_ARGC, rt.SYS_ARG);
	envp = argsvec(rt.SYS_ENVC, rt.SYS_ENV);
	argc = len(argv); envc = len(envp);
	return 0;
}

// ---- capturing output ----

// capture.start() redirects everything the program writes into a string and
// returns it. writes go to the buffer instead of the terminal until end()
// stops it, so the buffer is a string once end() has run:
//   let buf = std.capture.start();
//   rt.put_s("hello world!");   // nothing on the terminal
//   std.capture.end(buf);
//   rt.put_s(buf);              // hello world!
// the buffer holds 256 characters, and output past that is dropped. it has one
// more word for the 0 that end() writes, so a full capture is still a string.
// one capture at a time, and the buffer belongs to whoever holds it.
struct capture {
	// starts a capture: output goes into a new buffer instead of the terminal.
	//   returns: the buffer, managed by the collector; read it after end(buffer)
	static char* start() {
		int cap = 256;
		rt.outmode = 2; rt.outn = 0; rt.outcap = cap;
		rt.outbuf = rt.new(cap + 1);
		return rt.outbuf;
	}
	// stops the capture and ends the buffer with a 0.
	//   buffer: the buffer that start returned
	//   returns: the same buffer, now a string
	static char* end(char* buffer) {
		rt.outbuf[rt.outn] = 0;
		rt.outmode = 0; rt.outbuf = 0; rt.outn = 0; rt.outcap = 0;
		return buffer;
	}
}

// ---- character strings ----

// helpers for char* strings: one character per word, ended by a 0 word.
// called as std.Text.name(args).
struct Text {
	// the number written in decimal at the start of s. a leading '-' makes it
	// negative and the first character that is not a digit ends it.
	//   s: the string to read
	//   returns: the number, 0 when s starts with no digit
	static int atoi(char* s) {
		int n = 0, i = 0, sign = 1;
		if (s[0] == '-') { sign = 0 - 1; i = 1; }
		while (s[i] >= '0' && s[i] <= '9') { n = n * 10 + s[i] - '0'; i++; }
		return n * sign;
	}

	// writes n in decimal into dst, with a 0 after it.
	//   n: the number
	//   dst: where the text goes; 21 words is always enough (20 characters and the 0)
	//   returns: how many characters were written, not counting the 0
	static int itoa(int n, char* dst) {
		int b[24], i = 0, j = 0, neg = 0;
		if (!n) { dst[0] = '0'; dst[1] = 0; return 1; }
		if (n < 0) { neg = 1; n = 0 - n; }
		if (n < 0) { rt.copy_w(dst, "-9223372036854775808", 21); return 20; }
		while (n) { b[i] = '0' + n % 10; i++; n = n / 10; }
		if (neg) { dst[0] = '-'; j = 1; }
		while (i) { i--; dst[j] = b[i]; j++; }
		dst[j] = 0;
		return j;
	}

	// joins two strings into dst.
	//   dst: where the result goes, with room for both and a 0; not a or b
	//   a: the first string
	//   b: the second string
	//   returns: the length of the result
	static int cat(char* dst, char* a, char* b) {
		int i = 0, j = 0;
		while (a[i]) { dst[j] = a[i]; i++; j++; }
		i = 0;
		while (b[i]) { dst[j] = b[i]; i++; j++; }
		dst[j] = 0;
		return j;
	}

	// does s begin with pfx?
	//   s: the string to test
	//   pfx: the beginning to look for
	//   returns: 1 if it does (always, for an empty pfx), 0 if not
	static int starts(char* s, char* pfx) {
		int i = 0;
		while (pfx[i]) { if (s[i] != pfx[i]) return 0; i++; }
		return 1;
	}

	// does s end with suffix? an empty suffix always matches.
	//   s: the string to test
	//   suffix: the ending to look for
	//   returns: 1 when it matches, 0 otherwise
	static int ends(char* s, char* suffix) {
		int n = 0, m = 0, i = 0;
		while (s[n]) n++;
		while (suffix[m]) m++;
		if (m > n) return 0;
		while (i < m) { if (s[n - m + i] != suffix[i]) return 0; i++; }
		return 1;
	}

	// how many characters come before the 0.
	//   s: the string
	//   returns: the length, not counting the 0
	static int len(char* s) {
		int n = 0;
		while (s[n]) n++;
		return n;
	}

	// are the two strings the same, character for character?
	//   a, b: the strings to compare
	//   returns: 1 if they are equal, 0 if not
	static int eq(char* a, char* b) {
		int i = 0;
		while (a[i] && a[i] == b[i]) i++;
		return a[i] == b[i];
	}

	// copies s into dst, with a 0 after it.
	//   dst: where the copy goes, with room for s and the 0
	//   s: the string to copy
	//   returns: the length of the copy
	static int copy(char* dst, char* s) {
		int i = 0;
		while (s[i]) { dst[i] = s[i]; i++; }
		dst[i] = 0;
		return i;
	}

	// where pat first appears in s.
	//   s: the string to search
	//   pat: the string to look for; an empty pat is found at 0
	//   returns: the index of the first match, or -1 when there is none
	static int find(char* s, char* pat) {
		int i = 0, j;
		if (!pat[0]) return 0;
		while (s[i]) {
			j = 0;
			while (pat[j] && s[i + j] == pat[j]) j++;
			if (!pat[j]) return i;
			i++;
		}
		return 0 - 1;
	}

	// changes the ASCII letters of s to lower case, in place.
	//   s: the string to change
	//   returns: the length of s
	static int lower(char* s) {
		int i = 0;
		while (s[i]) {
			if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] + 32;
			i++;
		}
		return i;
	}

	// changes the ASCII letters of s to upper case, in place.
	//   s: the string to change
	//   returns: the length of s
	static int upper(char* s) {
		int i = 0;
		while (s[i]) {
			if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 32;
			i++;
		}
		return i;
	}

	// removes the spaces, tabs and line breaks from both ends of s, in place.
	//   s: the string to change
	//   returns: the length of what is left
	static int trim(char* s) {
		int n = 0, a = 0, b, i = 0, c;
		while (s[n]) n++;
		while (a < n && (s[a] == ' ' || s[a] == '\t' || s[a] == '\n' || s[a] == '\r')) a++;
		b = n;
		while (b > a) {
			c = s[b - 1];
			if (!(c == ' ' || c == '\t' || c == '\n' || c == '\r')) break;
			b--;
		}
		n = b - a;
		while (i < n) { s[i] = s[i + a]; i++; }
		s[n] = 0;
		return n;
	}
}

// ---- numbers ----

// plain integer helpers, called as std.Num.name(args). none of them can fail:
// an out of range result wraps the same way the arithmetic does.
struct Num {
	// the absolute value of n, using wrapping word arithmetic. the minimum
	// word remains negative because its positive value cannot fit in a word.
	//   n: the value
	//   returns: its absolute value, or the minimum word
	static int abs(int n) {
		if (n < 0) return 0 - n;
		return n;
	}

	// the smaller of a and b.
	//   a, b: the values to compare
	//   returns: the smaller value (a when they are equal)
	static int min(int a, int b) {
		if (a < b) return a;
		return b;
	}

	// the larger of a and b.
	//   a, b: the values to compare
	//   returns: the larger value (a when they are equal)
	static int max(int a, int b) {
		if (a > b) return a;
		return b;
	}

	// v, kept between lo and hi.
	//   v: the value
	//   lo, hi: the bounds, lo first; lo must not exceed hi
	//   returns: v clamped to the bounds
	static int clamp(int v, int lo, int hi) {
		if (v < lo) return lo;
		if (v > hi) return hi;
		return v;
	}

	// the greatest common divisor of a and b, computed with word arithmetic.
	//   a, b: the values
	//   returns: their greatest common divisor
	static int gcd(int a, int b) {
		if (a < 0) a = 0 - a;
		if (b < 0) b = 0 - b;
		int t;
		while (b) { t = a % b; a = b; b = t; }
		return a;
	}

	// b raised to the power e, by one multiply per step of e, so a large e is slow.
	// e below 0 gives 1, and the result wraps as a word.
	//   b: the base
	//   e: the exponent
	//   returns: b to the power e, or 1 when e is negative
	static int pow(int b, int e) {
		int r = 1;
		while (e > 0) { r = r * b; e--; }
		return r;
	}

	// the whole square root of n, rounded down. n below 0 gives 0.
	//   n: the value
	//   returns: the greatest integer whose square is at most n, or 0 for n <= 0
	static int isqrt(int n) {
		int lo = 0, hi = 3037000499, mid;
		if (n <= 0) return 0;
		while (lo < hi) {
			mid = lo + (hi - lo + 1) / 2;
			if (mid <= n / mid) lo = mid; else hi = mid - 1;
		}
		return lo;
	}

	// -1, 0 or 1 according to the sign of n.
	//   n: the value
	//   returns: -1 when n is negative, 0 when it is zero, and 1 when it is positive
	static int sign(int n) {
		if (n < 0) return 0 - 1;
		if (n > 0) return 1;
		return 0;
	}
}

// ---- the host ----

// the argument block for Host.raw: word 0 is the syscall number, words 1 to 6
// are its arguments. Host.raw fills it on each call.
int rawblk[7];

// an open file, from Host.open. its drop closes the descriptor, so the file is
// closed when its owner's block ends, when it is freed, or when the collector
// reclaims it (docs/SPEC.md 6.15). called as f.write(s), f.read(buf, n).
struct File {
	int fd;
	// writes a string.
	//   s: the text to write
	//   returns: how many bytes were written, negative on an error
	int write(char* s) { return rt.syscall(rt.SYS_WRITE, this.fd, s, rt.len_w(s)); }
	// reads bytes, one to a word.
	//   buf: where they go
	//   n: the most to read
	//   returns: how many were read, 0 at the end of the file, negative on an error
	int read(char* buf, int n) { return rt.syscall(rt.SYS_READ, this.fd, buf, n); }
	// the file dies: close its descriptor
	void drop() { rt.syscall(rt.SYS_CLOSE, this.fd, 0, 0); }
}

// calls into the host that runs the vm: the environment, the clock, files and
// raw system calls. called as std.Host.name(args).
struct Host {
	// calls any linux system call on the host. this is the escape hatch below
	// the named helpers: the number is the kernel's, so the meaning of each
	// argument depends on the call. the words reach the kernel unchanged, so a
	// pointer is a host address to it, not a place in the vm's memory. the call
	// runs on the real machine, so only use it where that is wanted.
	//   nr: the syscall number (x86-64 and arm64 numbers differ, so check the host)
	//   a..f: the six arguments, unused ones 0
	//   returns: the kernel's result, -errno on failure, or -1 on unsupported hosts
	static int raw(int nr, int a, int b, int c, int d, int e, int f) {
		rawblk[0] = nr; rawblk[1] = a; rawblk[2] = b; rawblk[3] = c;
		rawblk[4] = d; rawblk[5] = e; rawblk[6] = f;
		return rt.syscall(rt.SYS_RAW, rawblk, 0, 0);
	}

	// copies the value of an environment variable into dst, as a 0-terminated string.
	//   name: the variable's name
	//   dst: where the value goes
	//   n: the size of dst in words, the 0 included
	//   returns: how many characters were copied, at most n - 1, so a longer value
	//     is cut short; -1 if the variable is not set or n is below 1
	static int env(char* name, char* dst, int n) { return rt.syscall(rt.SYS_GETENV, name, dst, n); }

	// the clock.
	//   returns: the time in seconds since 1970
	static int now() { return rt.syscall(rt.SYS_TIME, 0, 0, 0); }

	// opens a file. the result owns the descriptor: its drop closes it (see File).
	//   path: the file's name
	//   mode: 0 to read, 1 to write (the file is replaced, or created)
	//   returns: the open file, or null if it could not be opened
	static File*.u open(char* path, int mode) {
		int fd = rt.syscall(rt.SYS_OPEN, path, mode, 0);
		if (fd < 0) return 0;
		File* f = rt.new(File);
		f.fd = fd;
		return f;
	}

	// writes a string to a file, replacing what was there. the file is created if
	// it is missing.
	//   path: the file's name
	//   s: the text to write
	//   returns: how many bytes were written, -1 if the file could not be opened
	static int writefile(char* path, char* s) {
		File* f = Host.open(path, 1);
		if (!f) return -1;
		return f.write(s);	// f's drop closes the file after the write
	}
}

// ---- byte strings ----

// the same helpers as Text, for packed byte strings of type bstr (b"..."
// literals). len reads the stored byte length. called as std.Bytes.name(args).
struct Bytes {
	// reads a decimal number at the start of s; a leading '-' makes it
	// negative, and the first non-digit ends the number.
	//   s: the byte string
	//   returns: the number, or 0 when s starts with no digit
	static int atoi(bstr s) { return rt.s_to_n(s); }

	// like Text.itoa, but the text is made fresh.
	//   n: the number
	//   returns: a new byte string, managed by the collector; the caller does not free it
	static bstr itoa(int n) { return rt.n_to_s(n); }

	// like Text.starts, for byte strings.
	//   s: the byte string to test
	//   pfx: the beginning to look for
	//   returns: 1 if s begins with pfx, 0 if not
	static int starts(bstr s, bstr pfx) {
		int i = 0, n = rt.len_s(s), m = rt.len_s(pfx);
		if (m > n) return 0;
		while (i < m) { if (rt.at_s(s, i) != rt.at_s(pfx, i)) return 0; i++; }
		return 1;
	}

	// the number of bytes in a packed byte string.
	//   s: the byte string
	//   returns: its stored length
	static int len(bstr s) { return rt.len_s(s); }

	// are two packed byte strings equal, byte for byte.
	//   a, b: the byte strings to compare
	//   returns: 1 if equal, 0 otherwise
	static int eq(bstr a, bstr b) {
		int i = 0;
		if (rt.len_s(a) != rt.len_s(b)) return 0;
		while (i < rt.len_s(a)) { if (rt.at_s(a, i) != rt.at_s(b, i)) return 0; i++; }
		return 1;
	}

	// where pat first appears in s.
	//   s: the byte string to search
	//   pat: the byte string to find; an empty pat is found at 0
	//   returns: its byte index, or -1 when absent
	static int find(bstr s, bstr pat) {
		int i = 0, j, n = rt.len_s(s), m = rt.len_s(pat);
		if (!m) return 0;
		while (i + m <= n) {
			j = 0;
			while (j < m && rt.at_s(s, i + j) == rt.at_s(pat, j)) j++;
			if (j == m) return i;
			i++;
		}
		return 0 - 1;
	}

	// does s end with suffix? an empty suffix always matches.
	//   s: the byte string to test
	//   suffix: the ending to look for
	//   returns: 1 when it matches, 0 otherwise
	static int ends(bstr s, bstr suffix) {
		int n = rt.len_s(s), m = rt.len_s(suffix), i = 0;
		if (m > n) return 0;
		while (i < m) { if (rt.at_s(s, n - m + i) != rt.at_s(suffix, i)) return 0; i++; }
		return 1;
	}

	// like Host.env, for byte strings. the value is written into the bytes of dst,
	// and the length of dst is not changed, so make dst big enough first.
	//   name: the variable's name, a byte string
	//   dst: the byte string that receives the value
	//   n: the most bytes dst may use, the 0 after the value included
	//   returns: how many bytes were copied, at most n - 1; -1 if the variable is not set or n is below 1
	static int env(bstr name, bstr dst, int n) { return rt.bgetenv(name, dst, n); }

	// like Host.writefile, for a byte string. the file is replaced, or created.
	//   path: the file's name, a byte string
	//   s: the bytes to write
	//   returns: how many bytes were written, -1 if the file could not be opened
	static int writefile(bstr path, bstr s) {
		int fd = rt.bopen(path, 1), n;
		if (fd < 0) return -1;
		n = rt.bwrite(fd, s, rt.len_s(s));
		rt.syscall(rt.SYS_CLOSE, fd, 0, 0);
		return n;
	}
}

// ---- arenas ----

// a region of n words that Arena.alloc hands out and Arena.reset frees all at once.
//   n: its capacity in words; values below 1 allocate one word
//   returns: the arena, owned by the caller
int .u arena(int n) { return rt.arena_new(n); }

// helpers for an arena made by std.arena. called as std.Arena.name(args).
struct Arena {
	// takes n zeroed words from an arena.
	//   a: the arena
	//   n: how many words
	//   returns: the first word; 0 when n words do not fit, or n is negative
	static int alloc(word a, int n) { return rt.arena_alloc(a, n); }

	// gives every block of an arena back at once. pointers returned by alloc
	// before the reset are no longer valid.
	//   a: the arena
	//   returns: 0
	static int reset(word a) { return rt.arena_reset(a); }
}

// ---- growable byte buffers ----

// makes an empty byte buffer with room for n bytes. the buffer keeps its length
// and capacity in two words, followed by the bytes, packed.
//   n: the capacity in bytes; a negative value is treated as 0
//   returns: the buffer, owned by the caller
word .u bnew(int n) {
	int words;
	word p;
	if (n < 0) n = 0;
	words = (n + 7) >> 3;
	p = rt.new(2 + words);
	p[0] = 0;
	p[1] = n;
	return u*p;
}

// byte buffers made by bnew. the length grows as bytes are set, up to the
// capacity, which is fixed. called as std.Buf.name(args).
struct Buf {
	// how many bytes a buffer holds.
	//   b: the buffer, from bnew
	//   returns: its length
	static int length(word b) { return b[0]; }

	// how many bytes a buffer can hold.
	//   b: the buffer, from bnew
	//   returns: its capacity
	static int capacity(word b) { return b[1]; }

	// one byte of a buffer.
	//   b: the buffer
	//   i: the position
	//   returns: the byte, 0 when i is outside the buffer (below 0, or at or past the length)
	static int get(word b, int i) { if (i < 0 || i >= b[0]) return 0; return rt.ld8(rt.addr_b(b + 2) + i); }

	// sets one byte of a buffer. a write at or past the length makes the length
	// i + 1, and the bytes skipped over are left at 0.
	//   b: the buffer
	//   i: the position, below the capacity
	//   v: the value; only its low 8 bits are kept
	//   returns: the byte stored, 0 when i is outside the capacity
	static int set(word b, int i, int v) {
		if (i < 0 || i >= b[1]) return 0;
		rt.st8(rt.addr_b(b + 2) + i, v & 255);
		if (i >= b[0]) b[0] = i + 1;
		return v & 255;
	}
}

// array algorithms borrow their input and visit elements in index order.
// map and filter return independent handles. reference elements are shared
// with the collector, so freeing the input does not invalidate the result.

// the first index equal to value, or -1 when no element matches.
//   source: the array, only read
//   value: the element to find
int array_find<T>(fixed T[?].m source, T value) {
	int length = len(source);
	for (int i = 0; i < length; i++) if (source[i] == value) return i;
	return -1;
}
// true when an element equals value.
//   source: the array, only read
//   value: the element to find
int array_contains<T>(fixed T[?].m source, T value) { return array_find(source, value) >= 0; }
// the first index whose predicate is true, or -1 when none matches.
//   source: the array, only read
//   predicate: called on each element; nonzero means a match
int array_find_if<T>(fixed T[?].m source, int(T).m predicate) {
	int length = len(source);
	for (int i = 0; i < length; i++) if (predicate(source[i])) return i;
	return -1;
}
// true when any element satisfies predicate; false for an empty array.
//   source: the array, only read
//   predicate: called on each element; nonzero means a match
int array_any<T>(fixed T[?].m source, int(T).m predicate) { return array_find_if(source, predicate) >= 0; }
// true when every element satisfies predicate, including an empty array.
//   source: the array, only read
//   predicate: called on each element; nonzero means a match
//   returns: 1 or 0
int array_all<T>(fixed T[?].m source, int(T).m predicate) {
	int length = len(source);
	for (int i = 0; i < length; i++) if (!predicate(source[i])) return 0;
	return 1;
}
// the number of elements satisfying predicate.
//   source: the array, only read
//   predicate: called on each element; nonzero means a match
int array_count<T>(fixed T[?].m source, int(T).m predicate) {
	int length = len(source);
	int count = 0;
	for (int i = 0; i < length; i++) if (predicate(source[i])) count++;
	return count;
}
// apply transform once to each element and return the transformed array.
// the result element type follows the callback's return type.
//   source: the array, only read
//   transform: called once on each element, in order
//   returns: a new array of the results, owned by the caller
U[?].u array_map<T,U>(fixed T[?].m source, U(T).m transform) {
	int length = len(source);
	U[?] result = rt.new(U[?]);
	for (int i = 0; i < length; i++) push(result, run.share_value(transform(source[i])));
	return result;
}
// copy elements satisfying predicate into a new array, preserving order.
//   source: the array, only read
//   predicate: called on each element; nonzero keeps it
//   returns: the new array, owned by the caller
T[?].u array_filter<T>(fixed T[?].m source, int(T).m predicate) {
	int length = len(source);
	T[?] result = rt.new(T[?]);
	for (int i = 0; i < length; i++) if (predicate(source[i])) push(result, run.share_value(source[i]));
	return result;
}
// fold elements from left to right, starting with initial; an empty array
// returns initial without calling combine.
//   source: the array, only read
//   initial: the starting value
//   combine: called as combine(total, element) for each element, in order
//   returns: the folded value
A array_reduce<T,A>(fixed T[?].m source, A initial, A(A,T).m combine) {
	int length = len(source);
	for (int i = 0; i < length; i++) initial = combine(initial, source[i]);
	return initial;
}

run.method("find", array_find);
run.method("contains", array_contains);
run.method("find_if", array_find_if);
run.method("any", array_any);
run.method("all", array_all);
run.method("count", array_count);
run.method("map", array_map);
run.method("filter", array_filter);
run.method("reduce", array_reduce);