path: root/src/compiler/types.zc

// ---- types ----

// types are a compiler primitive: records in the type area, hash-consed so
// the same type is always the same pointer and comparing types is comparing
// words. untyped code is typed word, which goes with anything. the records
// stay in memory after compiling, so programs can inspect them.
//   t[0] kind  t[1] size in words  t[2] name  t[3] n  t[4] a  t[5] b  t[6] c  t[7..] extra
//   ptr: a = element             arr: a = element, n = length
//   fn: a = return type, n = parameter count, b = signature (u m d tags), extra = parameter types
//   struct: n = field count (-1 until laid out), a = fields (name, type, offset),
//           b = generic template, c = type arguments [n, t1, t2 ...]
//   var: a type parameter, n = its index
//   gen: a generic struct: n = parameter count, a = fields (name, type), b = field count, c = parameter names


// the type area is a bump allocator of its own (tytop .. R_TYEND). talloc
// hands out zeroed words, tnew makes a record and adds it to the list of all
// types (R_TY), and the constructors below look that list up first, which is
// the hash-consing: asking for the same pointer type twice returns the same
// record. the list is searched linearly, which is fine for the few hundred
// types a program has.
int talloc(int n) {
	int p = tytop;
	if (tytop + n > tyend) {
		p = chk_resize(0, 0, n + 16385); p[0] = typeblocks; typeblocks = p;
		p++; tytop = p; tyend = p + n + 16384;
	}
	tytop = tytop + n;
	rt.fill_w(p, 0, n);
	return p;
}
// make a type record of the given kind, size and name in the type area.
word tnew(int kind, int size, char* nm, int extra) {
	word t = talloc(7 + extra);
	t[0] = kind; t[1] = size; t[2] = nm;
	if (ntl >= typecap) { typelist = chk_resize(typelist, ntl, typecap * 2); typecap = typecap * 2; }
	typelist[ntl] = t; ntl++;
	return t;
}
// qualified types retain their layout and reference their unqualified record.
word tunconst(word t) {
	word entry = readonly_types;
	while (entry) { if (entry[1] == t) return entry[2]; entry = entry[0]; }
	return t;
}
int treadonly(word t) { return t && tunconst(t) != t; }
word tconst(word t) {
	word entry = readonly_types, qualified; int words = 7;
	if (treadonly(t)) return t;
	while (entry) { if (entry[2] == t) return entry[1]; entry = entry[0]; }
	if (t[0] == TY_FN) words = words + t[3];
	qualified = tnew(t[0], t[1], t[2], words - 7); rt.copy_w(qualified, t, words);
	entry = talloc(3); entry[0] = readonly_types; entry[1] = qualified; entry[2] = t; readonly_types = entry;
	return qualified;
}
// writes require mutable storage, independently of optional type checking.
int require_mutable(word t) {
	if (treadonly(t)) serr("const storage cannot be modified");
	return 0;
}
// the pointer type to type e, reused when it already exists.
word tptr(int e) {
	int i = 0; word t;
	while (i < ntl) { t = typelist[i]; if (t[0] == TY_PTR && t[4] == e && !treadonly(t)) return t; i++; }
	t = tnew(TY_PTR, 1, 0, 0); t[4] = e;
	return t;
}
// sized integers (i8 u8 i16 u16 i32 u32) are TY_INT records with t[5] = bytes,
// t[6] bit 0 = signed, and t[4] = the "packed view" twin: the same name with
// t[6] bit 1 set. a variable, parameter or field of a sized type is an
// ordinary word that is cut to size whenever it is stored. an element of an
// array or a pointer of a sized type is stored packed, 8, 4 or 2 to a word,
// and indexing yields the twin, whose lvalue is a byte address.
word tbytes(word t) { if (t[0] == TY_INT || t[0] == TY_FLOAT) return t[5]; return 0; }
// true for a packed integer or float type.
word ispk(word t) { return (t[0] == TY_INT || t[0] == TY_FLOAT) && (t[6] & 2); }
// the type a packed type stores its elements as, or the type itself.
word tpk(word t) { if (treadonly(t)) return tconst(tpk(tunconst(t))); if ((t[0] == TY_INT || t[0] == TY_FLOAT) && t[4]) return t[4]; return t; }
// an enhancement used by the compiler itself, inline when the runtime has it
int xenh(char* name) {
	int s = lookup(intern(name));
	if (s >= 0 && skind[s] == K_ENH) { op(XOP0 + sval[s]); return 0; }
	callname(intern(name));
	return 0;
}
// words an array of n elements of e takes: packed for a sized integer
word tasz(word e, int n) {
	if (n < 0) return 0;
	if (tbytes(e)) return (n * e[5] + 7) >> 3;
	return n * tsz(e);
}
// the fixed array type of n elements of type e, reused when it already exists.
word tarr(int e, int n) {
	int i = 0; word t;
	while (i < ntl) { t = typelist[i]; if (t[0] == TY_ARR && t[4] == e && t[3] == n && !treadonly(t)) return t; i++; }
	t = tnew(TY_ARR, tasz(e, n), 0, 0); t[4] = e; t[3] = n;
	return t;
}
// a sized integer type and its packed twin
word tsized(char* name, int bytes, int sgn) {
	word t = tnew(TY_INT, 1, intern(name), 0), twin = tnew(TY_INT, 1, t[2], 0);
	t[5] = bytes; t[6] = sgn; t[4] = twin;
	twin[5] = bytes; twin[6] = sgn | 2;
	addsym(t[2], K_TYPE, t);
	return t;
}
// the function type with this return, parameter list and signature.
// ---- borrow returns ----
// `borrows s` after a parameter list says the result is a borrow of parameter s
// (several, comma separated, in a declaration). a parameter is named, or given by
// its position from 0 where it has no name (an extern, a function type). the mask
// lives in bits 50 to 61 of the signature, so a function type carries it too.
const int SIG_BORROWS = 50;
int sig_borrows(int sig) { return (sig >> SIG_BORROWS) & 4095; }
// the declared borrow mask of a call's callee: its symbol's signature, or the function type.
int callee_borrows(int s, word ft) {
	if (s >= 0 && s < nsym && (sflag[s] & F_SIG)) return sig_borrows(ssig[s]);
	if (ft && ft[0] == TY_FN) return sig_borrows(ft[5]);
	return 0;
}
int borrows_clause(char** names, int np, int many) {
	int mask = 0, k;
	if (tk != T_ID || !rt.eq_w(tv, "borrows")) return 0;
	next();
	while (1) {
		k = 0 - 1;
		if (tk == T_NUM) { if (tv >= 0 && tv < np) k = tv; }
		else if (tk == T_ID && names) { int j = 0; while (j < np) { if (names[j] && rt.eq_w(names[j], tv)) k = j; j++; } }
		if (k < 0) { serr("borrows names a parameter, by name or by its position from 0"); next(); return mask; }
		if (k >= 12) serr("only the first 12 parameters can be borrowed by the result");
		else mask = mask | (1 << k);
		next();
		if (!many || !accept(s_comma)) break;
	}
	return mask;
}
word tfn(int ret, int np, word ps, int sig) {
	int i = 0, j; word t;
	while (i < ntl) {
		t = typelist[i];
		if (t[0] == TY_FN && t[4] == ret && t[3] == np && t[5] == sig) {
			j = 0; while (j < np && t[7 + j] == ps[j]) j++;
			if (j == np) return t;
		}
		i++;
	}
	t = tnew(TY_FN, 1, 0, np); t[4] = ret; t[3] = np; t[5] = sig;
	rt.copy_w(t + 7, ps, np);
	return t;
}
// T[?], or fixed T[?]
word tdyn(int e, int f) {
	int i = 0; word t;
	while (i < ntl) { t = typelist[i]; if (t[0] == TY_DYN && t[4] == e && t[3] == f && !treadonly(t)) return t; i++; }
	t = tnew(TY_DYN, 1, 0, 0); t[4] = e; t[3] = f;
	return t;
}
// the type variable with index i, reused when it already exists.
word tvar(int i, char* nm) {
	int k = 0; word t;
	while (k < ntl) { t = typelist[k]; if (t[0] == TY_VAR && t[3] == i) return t; k++; }
	t = tnew(TY_VAR, 1, nm, 0); t[3] = i;
	return t;
}
// the instance of generic struct g with type arguments args[0..n). found if it
// already exists, otherwise created unlaid-out (n = -1), so that mentioning
// vec<T> inside vec<T>'s own methods does not recurse; tresolve lays it out.
word tinst(word g, word args, int n) {
	int i = 0, j; word t, v;
	while (i < ntl) {
		t = typelist[i];
		if (t[0] == TY_STRUCT && t[5] == g) {
			v = t[6]; j = 0; while (j < n && v[1 + j] == args[j]) j++;
			if (j == n) return t;
		}
		i++;
	}
	v = talloc(n + 1); v[0] = n; rt.copy_w(v + 1, args, n);
	t = tnew(TY_STRUCT, 0, g[2], 0); t[3] = -1; t[5] = g; t[6] = v;
	return t;
}
// lay out a generic instance on first use
word tresolve(word t) {
	word g, f; int n, i; word fs; int off = 0, ft; word[8] bs;
	if (t[0] != TY_STRUCT || t[3] >= 0) return t;
	if (t[3] == -2) { serr("a struct can't contain itself by value"); t[3] = 0; return t; }
	t[3] = -2;
	g = t[5]; n = g[5]; f = g[4];
	rt.fill_w(bs, 0, 8); rt.copy_w(bs, t[6] + 1, t[6][0]);
	fs = talloc(n * 3 + 1);
	i = 0;
	while (i < n) {
		ft = subst(f[i + i + 1], bs);
		fs[i * 3] = f[i + i]; fs[i * 3 + 1] = ft; fs[i * 3 + 2] = off;
		off = off + tsz(ft);
		i++;
	}
	t[4] = fs; t[1] = off; t[3] = n;
	return t;
}
// size of a type in words, laying out a generic instance first if it needs it
word tsz(word t) {
	if (t[0] == TY_STRUCT && t[3] < 0) tresolve(t);
	return t[1];
}
// replace type parameters with what they were bound to (unbound ones become word)
word subst(word t, word bs) {
	if (treadonly(t)) return tconst(subst(tunconst(t), bs));
	int k = t[0], i, n; word[24] v; word vec;
	if (k == TY_VAR) { if (bs[t[3]]) return bs[t[3]]; return tword; }
	if (k == TY_PTR) return tptr(subst(t[4], bs));
	if (k == TY_ARR) return tarr(subst(t[4], bs), t[3]);
	if (k == TY_DYN) return tdyn(subst(t[4], bs), t[3]);
	if (k == TY_FN) {
		n = t[3];
		i = 0;
		while (i < n) { v[i] = subst(t[7 + i], bs); i++; }
		return tfn(subst(t[4], bs), n, v, t[5]);
	}
	if (k == TY_STRUCT && t[5]) {
		vec = t[6];
		n = vec[0];
		i = 0;
		while (i < n) { v[i] = subst(vec[1 + i], bs); i++; }
		return tinst(t[5], v, n);
	}
	return t;
}
// small type predicates. an array decays to a pointer to its element where a
// value is wanted, and telem is what indexing a pointer or array yields.
word isnum(word t) { return t[0] == TY_INT || t[0] == TY_CHAR || t[0] == TY_BOOL; }
// true for an aggregate type: an array or a struct.
word isagg(word t) { return t[0] == TY_ARR || t[0] == TY_STRUCT; }
// true for a pointer or an array type.
word isptr(word t) { return t[0] == TY_PTR || t[0] == TY_ARR || t[0] == TY_BSTR; }
// true for a reference value, including growable-array handles and functions.
word isref(word t) { return isptr(t) || t[0] == TY_DYN || t[0] == TY_FN; }
// the pointer an array type turns into when used as a value.
word decay(word t) {
	if (treadonly(t)) return tconst(decay(tunconst(t)));
	if (t[0] == TY_ARR) return tptr(t[4]);
	return t;
}
// the element type of a pointer or array, or word for anything else.
word telem(word t) {
	if (treadonly(t)) return tconst(telem(tunconst(t)));
	if (t[0] == TY_PTR || t[0] == TY_ARR) return t[4];
	return tword;
}
// can a value of type src go where dst is expected?
// type compatibility, used by the optional typechecker. word is compatible with
// everything (untyped code stays legal), numbers convert freely, pointers need
// the same element unless one side is untyped or void, and a literal 0 is a
// null pointer.
word compat(word dst, word src) {
	if (treadonly(src) && isref(src) && !treadonly(dst)) return 0;
	dst = tunconst(dst); src = tunconst(src);
	if (dst == src) return 1;
	if (dst == tword && src && (src == tbstr || (src[0] == TY_PTR && src[4] == tchar) || (src[0] == TY_ARR && src[4] == tchar))) return 0;
	if (dst == tword || src == tword) return 1;
	if (dst == tbstr || src == tbstr) return dst == tbstr && xzero;
	if (dst[0] == TY_PTR && src[0] == TY_STRUCT && dst[4] == src) return 1;	// an in-place struct supplies its address
	if (isen(dst) || isen(src)) {	// an enum takes only its own enum; an enum still becomes an int
		if (isen(dst) && isen(src)) return dst == src;
		if (isen(dst)) return 0;
	}
	if (isnum(dst) && isnum(src)) return 1;
	if (isfl(dst) && isfl(src)) return 1;
	src = decay(src);
	if (dst[0] == TY_PTR && src[0] == TY_PTR) {
		if (dst[4] == tword || src[4] == tword || dst[4] == tvoid || src[4] == tvoid) return 1;
		return dst[4] == src[4];
	}
	if ((dst[0] == TY_PTR || dst[0] == TY_FN || dst[0] == TY_DYN) && xzero) return 1;	// a literal 0 is a null pointer
	if (dst[0] == TY_DYN && src[0] == TY_DYN && dst[4] == src[4]) return dst[3] || !src[3];	// a growable array can't hold a fixed one
	return dst == src;
}
// match pattern type p (which may contain type parameters) against actual type
// a, filling the bindings bs. this is how a call to a generic function infers
// T from its arguments.
word unify(word p, word a, word bs) {
	int i, n; word pv, av;
	if (p[0] != TY_VAR) {
		if (treadonly(a) && isref(a) && !treadonly(p)) return 0;
		p = tunconst(p); a = tunconst(a);
	}
	if (p[0] == TY_VAR) { i = p[3]; if (!bs[i]) { bs[i] = a; return 1; } return compat(bs[i], a); }
	a = decay(a);
	if (p[0] == TY_PTR && a[0] == TY_PTR) { if (a[4] == tword) return 1; return unify(p[4], a[4], bs); }
	if (p[0] == TY_DYN && a[0] == TY_DYN) return (p[3] || !a[3]) && unify(p[4], a[4], bs);
	if (p[0] == TY_FN && a[0] == TY_FN) {
		if (p[3] != a[3] || ((p[5] >> 6) != (a[5] >> 6))) return 0;
		i = 0;
		while (i < p[3]) {
			pv = subst(p[7 + i], bs); av = a[7 + i];
			if (pv != tword && av != tword && pv != av) return 0;
			if (!unify(p[7 + i], av, bs)) return 0;
			i++;
		}
		return unify(p[4], a[4], bs);
	}
	if (p[0] == TY_STRUCT && p[5] && a[0] == TY_STRUCT && a[5] == p[5]) {
		pv = p[6]; av = a[6]; n = pv[0]; i = 0;
		while (i < n) { if (!unify(pv[1 + i], av[1 + i], bs)) return 0; i++; }
		return 1;
	}
	return compat(p, a);
}
// print a type the way it is written in source. function pointers use an alias
// for source spelling; array pointers use T[N]*.
int tprint_dimensions(word t) {
	while (t[0] == TY_ARR || t[0] == TY_DYN) { rt.put_c('['); if (t[0] == TY_DYN) rt.put_c('?'); else if (t[3] >= 0) rt.put_n(t[3]); rt.put_c(']'); t = t[4]; }
	return 0;
}
word tprint(word t) {
	if (treadonly(t)) { rt.put_s("const "); return tprint(tunconst(t)); }
	int k = t[0], i; word v;
	if (k == TY_PTR) {	// postfix pointers; only function pointers keep the display-only prefix form
		v = t[4][0];
		if (v == TY_FN) { rt.put_c('*'); return tprint(t[4]); }
		tprint(t[4]); rt.put_c('*');
		return 0;
	}
	if (k == TY_ARR || k == TY_DYN) { if (k == TY_DYN && t[3]) rt.put_s("fixed "); v = t; while (v[0] == TY_ARR || v[0] == TY_DYN) v = v[4]; tprint(v); return tprint_dimensions(t); }
	if (k == TY_FN) {
		if (t[4] == tword) rt.put_s("fn"); else tprint(t[4]);
		if (t[5] & 1) rt.put_s(".u");
		rt.put_c('(');
		i = 0;
		while (i < t[3]) {
			if (i) rt.put_s(", ");
			tprint(t[7 + i]);
			if (i < 12 && tparamtag(t, i) == 1) rt.put_s(".m");
			if (i < 12 && tparamtag(t, i) == 2) rt.put_s(".d");
			i++;
		}
		rt.put_c(')');
		return 0;
	}
	if (t[2]) rt.put_s(t[2]); else rt.put_s("?");
	if (k == TY_STRUCT && t[5]) {
		v = t[6]; rt.put_c('<');
		i = 0; while (i < v[0]) { if (i) rt.put_s(", "); tprint(v[1 + i]); i++; }
		rt.put_c('>');
	}
	return 0;
}
// typechecker errors. they only fire when "typecheck on" is set, in reachable
// code, and never during a dry run.
int tcerr(int what, int want, int got) {
	if (!tc_on || !live || dry || panic) return 0;
	errat(); rt.put_s("type error: "); rt.put_s(what);
	rt.put_s(": expected "); tprint(want); rt.put_s(", got "); tprint(got);
	errend();
	return 0;
}
// report a type error when ok is false, showing the type it got.
int tcneed(int ok, int what, int got) {
	if (ok || !tc_on || !live || dry || panic) return 0;
	errat(); rt.put_s("type error: "); rt.put_s(what); rt.put_s(", got "); tprint(got);
	errend();
	return 0;
}
// the type parameters in scope (tpn): a generic function or struct body sees
// T as a type. istypename says whether a name starts a type here, which is how
// the parser tells a declaration from an expression.
int tpfind(int n) {
	int i = ntp;
	while (i) {
		i--;
		if (tpn[i] == n) return i;
	}
	return -1;
}
// true when the name n is a type, a type parameter or a generic type.
word istypename(char* n) {
	int s;
	if (n == s_fixed || n == s_const) return 1;
	if (ginst && gfind(n) >= 0) return 1;
	if (tpfind(n) >= 0) return 1;
	if (findloc(n) >= 0) return 0;
	s = lookup(n);
	return s >= 0 && skind[s] == K_TYPE;
}
// the closing > of a type argument list; splits >> in two
int closeangle() {
	if (is_op(s_shr)) { tv = s_gt; return 0; }
	expect(s_gt);
	return 0;
}
// a type, then any number of (params) after it: int(int, int) is a function
// returning int, fn(int) one returning a plain word
// ---- parsing types ----

// grammar, outermost first:
//   ptype   a type, then any number of (params): int(int, int) is a function type
//   ptype0  postfix pointers and array groups: T*, T[N], T[], T[?]
//   ptype1  a type name, fixed qualifier, function base, or generic instance
// the first thing in ptype's comment applies here too: fn(int) is a function
// returning a plain word.
int ptype() {
	int start = toff, t = ptype0(), np, tags, tag; word[24] ps;
	while (is_op(s_lp)) {
		next(); np = 0; tags = 0;
		if (!is_op(s_rp)) {
			while (1) {
				if (np >= 24) fatal("too many parameters");
				ps[np] = ptype(); if (ps[np][0] == TY_ARR) ps[np] = decay(ps[np]);
				tag = 0;
				if (accept(s_dot)) {
					if (tv == s_m) tag = 1; else if (tv == s_d) tag = 2; else die("callback parameter lifetime is .m or .d");
					next();
				}
				tags = tags | (tag << (np + np));
				np++;
				if (!accept(s_comma)) break;
			}
		}
		expect(s_rp);
		tag = borrows_clause(0, np, 0);
		t = tfn(t, np, ps, np + np + tags * 64 + (tag << SIG_BORROWS));
	}
	ht_note(start, toff, t);
	return t;
}
// a type with any stars after it: int*, vec<T>*, point**
int ptype0() {
	int t = ptype1(), cap = 8, n, count, j; word dims = 0;
	while (is_op(s_star) || is_op(s_lk)) {
		if (accept(s_star)) t = tptr(t);
		else {
			count = 0;
			while (accept(s_lk)) {
				if (accept(s_q)) { expect(s_rk); n = -2; }
				else if (accept(s_rk)) n = -1;
				else { n = cexpr(); expect(s_rk); if (n < 0) serr("a negative array length"); }
				if (!dims || count == cap) { if (dims) cap = cap * 2; dims = chk_resize(dims, count, cap); }
				dims[count] = n; count++;
			}
			j = count; while (j) { j--; if (dims[j] == -2) t = tdyn(t, 0); else t = tarr(t, dims[j]); }
		}
	}
	if (dims) rt.free(dims);
	return t;
}
// parse one type with no trailing function parts.
word ptype1() {
	int n, s; word t; word[8] args; int na = 0, i;
	if (is_op(s_lk)) { die("array types are postfix: T[N], T[] or T[?]"); return tword; }
	if (is_id(s_const)) { next(); return tconst(ptype0()); }
	if (is_id(s_fixed)) {	// fixed T[?] can't grow; fixed T[n] says what T[n] already means
		next(); t = ptype0();
		if (t[0] == TY_DYN) { if (treadonly(t)) return tconst(tdyn(t[4], 1)); return tdyn(t[4], 1); }
		if (t[0] != TY_ARR) serr("only arrays can be fixed");
		return t;
	}
	if (is_id(s_fn)) {
		next();
		if (!is_op(s_lp)) die("fn as a type needs its parameters: fn(int)");
		return tword;
	}
	if (tk != T_ID) { diefound("expected a type"); return tword; }
	n = tv;
	if (ginst) {
		i = gfind(n);
		if (i >= 0) { next(); return gib[i]; }
	}
	i = tpfind(n);
	if (i >= 0) { next(); return tvar(i, n); }
	s = source_lookup(n);
	// T in T first<T>(...)
	if (tvauto && (s < 0 || skind[s] != K_TYPE) && ntp < 8) {
		tpn[ntp] = n;
		lsmark(2, n);
		ntp++;
		next();
		return tvar(ntp - 1, n);
	}
	if (s < 0 || skind[s] != K_TYPE) { dien(n, "isn't a type"); return tword; }
	rs_put(toff, RS_SYM, rs_sym(s), s);
	next();
	t = sval[s];
	if (t[0] != TY_GEN) return t;
	expect(s_lt);
	while (1) {
		if (na >= 8) die("too many type arguments");
		args[na] = ptype();
		if (args[na] == tvoid) serr("a type argument can't be void");
		na++;
		if (!accept(s_comma)) break;
	}
	closeangle();
	if (na != t[3]) serrn(n, "wrong number of type arguments");
	return tinst(t, args, na);
}
// does a declaration start here? (a type, or a bare .tag)
// does a declaration start at the current token? (a type name, [, or a bare .tag)
int tstart() {
	if (tk == T_OP) {
		if (tv == s_lk || tv == s_dot) return 1;
		return 0;
	}
	if (tk != T_ID) return 0;
	if (tv == s_fn) return 1;
	if (!istypename(tv)) return 0;
	// Type.name(...) at the start of a statement is a static call, not a declaration:
	// a declaration's dot is followed by a tag, u, m or d
	peekat(0);
	if (pk_tk == T_OP && pk_tv == s_dot) {
		peekat(1);
		if (pk_tk == T_ID && pk_tv != s_u && pk_tv != s_m && pk_tv != s_d) return 0;
	}
	return 1;
}
// [type] [.tag]
// parse a declaration's [type] [.tag] into dty and dtag
int dtype() {
	dty = 0; dtag = 0;
	if (!is_op(s_dot)) dty = ptype();
	if (accept(s_dot)) {
		if (tv == s_m) {
			dtag = S_M;
		} else if (tv == s_u) {
			dtag = S_U;
		} else if (tv == s_d) dtag = S_D; else die("a tag is .u, .m or .d");
		next();
	}
	return 0;
}
// the struct whose body or methods are being compiled: a bare name there is looked up as Struct.name
// (a constant, or a static function called by its bare name) before the global scope, so the struct's
// own wins over a global of the same name
char* mstruct;
// does a constant declaration start in a struct body? const NAME = e;  const T NAME = e;
// (a field of a const type has no initializer, so the = tells them apart)
int struct_const_start() {
	if (!is_id(s_const)) return 0;
	peekat(0); if (pk_tk != T_ID) return 0;
	peekat(1);
	if (pk_tk == T_OP && pk_tv == s_eq) return 1;
	if (pk_tk == T_ID) { peekat(2); return pk_tk == T_OP && pk_tv == s_eq; }
	if (pk_tk == T_OP && pk_tv == s_star) { peekat(2); if (pk_tk != T_ID) return 0; peekat(3); return pk_tk == T_OP && pk_tv == s_eq; }
	return 0;
}
// const NAME = e, NAME = e; inside struct sn: a compile-time constant named Struct.NAME that takes no
// space in the layout. the optional type is read and dropped, as in gconst.
int struct_const(char* sn) {
	int off, s; char* cn;
	next();
	if (tk == T_ID) { peekat(0); if (pk_tk == T_ID || (pk_tk == T_OP && pk_tv == s_star)) ptype(); }
	mstruct = sn;
	while (1) {
		off = toff; cn = name();
		s = lookup(methname(sn, cn));
		if (s >= ubase && s >= 0) serrn(cn, "is defined twice in this struct");
		expect(s_eq);
		s = addsym(methname(sn, cn), K_CONST, cexpr());
		rs_put(off, RS_SYM, rs_sym(s), s);
		if (!is_op(s_comma) && !is_op(s_semi)) {	// a call or a variable's value follows what cprim could read
			serr("a struct constant must be a constant expression");
			while (!is_op(s_semi) && !is_op(s_rb) && tk != T_EOF) next();
			break;
		}
		if (!accept(s_comma)) break;
	}
	accept(s_semi);
	return 0;
}
// struct name { type field, ... }   or   struct name<A, B> { ... }
// the struct keyword. fields go in a scratch buffer first (name, type pairs),
// then are laid out: each field takes tsz(type) words, so offsets are words.
// methods are collected as token lists while the struct is read (grabfn) and
// compiled only when the struct is complete, so a method can use every field
// and call its siblings. a generic struct keeps its fields unresolved and
// can't have methods; each instance is laid out later by tresolve.
int kw_struct() {
	char* n; word t; int s, nf = 0; word buf = chk_resize(0, 0, 64); int bufcap = 64, i; word fs; int off = 0, gen = 0, ft, nm = 0, mcap = STRUCT_METHODS; char** mn = chk_resize(0, 0, mcap); word mq = chk_resize(0, 0, mcap), mst = chk_resize(0, 0, mcap), mty = chk_resize(0, 0, mcap), mrt = chk_resize(0, 0, mcap), mrg = chk_resize(0, 0, mcap); int bo, k, stat = 0; char* fname = 0; char* msv = mstruct;
	next();
	n = module_symbol(name());
	if (is_op(s_lt)) {	// generic
		next(); ntp = 0;
		while (1) {
			if (ntp >= 8) die("too many type parameters");
			tpn[ntp] = name();
			lsmark(2, tpn[ntp]);
			ntp++;
			if (!accept(s_comma)) break;
		}
		closeangle();
		gen = 1;
		t = tnew(TY_GEN, 0, n, 0); t[3] = ntp;
		fs = talloc(ntp); rt.copy_w(fs, tpn, ntp); t[6] = fs;
	} else { t = tnew(TY_STRUCT, 0, n, 0); t[3] = -2; }	// -2 while its fields are read
	s = addsym(n, K_TYPE, t);
	expect(s_lb);
	while (!is_op(s_rb)) {
		if (tk == T_EOF) { die("missing }"); break; }
		stat = 0;
		if (struct_const_start()) { struct_const(n); continue; }
		while (is_id(s_unchecked) || is_id(s_unbounded)) { if (is_id(s_unchecked)) stat = stat | 2; else stat = stat | 4; next(); }
		if (is_id(s_static)) {	// static fn name(params) { body }, or static T name(params) { body }: a function of the struct, called as Struct.name(args), with no this
			next();
			stat = stat | 1;
		}
		if (is_id(s_fn)) {	// fn name(params) { body }: a method, compiled once the struct is complete
			next();
			if (nm >= mcap) {
				mcap = mcap * 2; mn = chk_resize(mn, nm, mcap); mq = chk_resize(mq, nm, mcap);
				mst = chk_resize(mst, nm, mcap); mty = chk_resize(mty, nm, mcap);
				mrt = chk_resize(mrt, nm, mcap); mrg = chk_resize(mrg, nm, mcap);
			}
			mn[nm] = name();
			mst[nm] = stat;
			mq[nm] = grabfn();
			mty[nm] = 0;
			k = methdecl(n, mn[nm]);
			if (stat & 1) sflag[k] = sflag[k] | F_STATIC;
			nm++;
			continue;
		}
		// let x, y; fields are plain words
		fname = 0;
		if (is_id(s_var)) {
			if (stat & 1) die("static must be followed by fn or a typed method");
			next();
			ft = tword;
		} else {
			// T name(params) { body } is a typed method; T name, ...; is a typed field
			rettype();
			fname = name();
			if (is_op(s_lp)) {
				if (nm >= mcap) {
					mcap = mcap * 2; mn = chk_resize(mn, nm, mcap); mq = chk_resize(mq, nm, mcap);
					mst = chk_resize(mst, nm, mcap); mty = chk_resize(mty, nm, mcap);
					mrt = chk_resize(mrt, nm, mcap); mrg = chk_resize(mrg, nm, mcap);
				}
				mn[nm] = fname;
				mst[nm] = stat;
				mq[nm] = grabfn();
				mty[nm] = 1; mrt[nm] = dty; mrg[nm] = dtag == S_U;
				if (dtag && dtag != S_U) serr("the only return tag is .u");
				k = methdecl(n, fname);
				if (stat & 1) sflag[k] = sflag[k] | F_STATIC;
				nm++;
				continue;
			}
			if (stat & 1) die("static must be followed by fn or a typed method");
			if (dtag) serr("a field has no tag");
			ft = dty;
		}
		while (1) {
			if ((nf + 1) * 2 > bufcap) { buf = chk_resize(buf, nf * 2, bufcap * 2); bufcap = bufcap * 2; }
			if (fname) { buf[nf + nf] = fname; fname = 0; } else buf[nf + nf] = name();
			lsmark(3, buf[nf + nf]); buf[nf + nf + 1] = ft;
			field_note(t, buf[nf + nf], nameoff); lt_note(nameoff, ft); rs_put(nameoff, RS_FIELD, nameoff, 0); nf++;
			if (!accept(s_comma)) break;
		}
		expect(s_semi);
	}
	next();
	if (gen) {
		fs = talloc(nf + nf); rt.copy_w(fs, buf, nf + nf);
		t[4] = fs; t[5] = nf;
		mdg = ntp; rt.copy_w(mdn, tpn, ntp);
		ntp = 0;
	} else {
		fs = talloc(nf * 3 + 1);
		i = 0;
		bo = 0;
		while (i < nf) {
			ft = buf[i + i + 1];
			if (ft == t) { serr("a struct can't contain itself by value; use a pointer"); ft = tword; }
			fs[i * 3] = buf[i + i]; fs[i * 3 + 1] = ft;
			// a sized field packs into the current word at its own alignment; its
			// offset is recorded as minus (byte offset + 1). anything else starts a word
			k = tbytes(ft);
			if (k) { bo = (bo + k - 1) / k * k; fs[i * 3 + 2] = 0 - bo - 1; bo = bo + k; }
			else { bo = (bo + 7) / 8 * 8; fs[i * 3 + 2] = bo / 8; bo = bo + tsz(ft) * 8; }
			i++;
		}
		off = (bo + 7) / 8;
		t[4] = fs; t[1] = off; t[3] = nf;
	}
	accept(s_semi);
	i = 0;
	if (!gen) mstruct = n;
	while (i < nm) { fn_method_compile = 1; methdef(n, mn[i], mq[i], mst[i], mty[i], mrt[i], mrg[i]); fn_method_compile = 0; i++; }
	mdg = 0;
	mstruct = msv;
	return s;
}
// ---- methods ----

// a method is an ordinary function named Struct.name whose first parameter is
// this, a pointer to the struct. e.method(a) calls Struct.name(e, a). the
// receiver's struct comes from its type, or, for an untyped word, from the
// one struct that has a method of that name.
// the symbol for a method is the interned string "Struct.name"
char* methname(char* sn, char* mn) {
	char* b = chk_resize(0, 0, rt.len_w(sn) + rt.len_w(mn) + 2); int i = 0, j = 0;
	while (sn[j]) { b[i] = sn[j]; i++; j++; }
	b[i] = '.'; i++;
	j = 0;
	while (mn[j]) { b[i] = mn[j]; i++; j++; }
	b[i] = 0;
	return intern(b);
}
// the method called n on struct type t, as a symbol index, or -1. methwhich
// (below) does the untyped version: search every struct for one with that
// method, which is unique or ambiguous (-2).
int methof(word t, char* n) {
	int s = lookup(methname(t[2], n));
	if (s >= 0 && skind[s] == K_FN) return s;
	return 0 - 1;
}
// the one method called n, -1 for none, -2 for several structs having one
int methscan(char* n) {
	int i = 0; word t; int s, hit = 0 - 1;
	while (i < ntl) {
		t = typelist[i];
		if (t[0] == TY_STRUCT && t[3] >= 0) {
			s = methof(t, n);
			if (s >= 0) { if (hit >= 0) return 0 - 2; hit = s; }
		}
		i++;
	}
	return hit;
}
// declare Struct.name now, so methods can call each other in any order
// (the declaration is what makes mutual recursion between methods work: the
// symbol exists with no body yet, and calls to it go on the patch chain)
int methdecl(char* sn, char* mn) {
	int nm = methname(sn, mn), s = lookup(nm);
	if (s >= ubase && s >= 0 && skind[s] == K_FN) {
		serrn(mn, "is defined twice in this struct");
		return s;
	}
	s = addsym(nm, K_FN, 0);
	sflag[s] = 0;
	return s;
}
// the tokens of a method, from its ( to the } that closes its body, as a token list
// a method body is not parsed when the struct is read. its tokens are copied
// into a token list (kind, value, place triples) up to the matching brace, and
// methdef replays them later. the place travels with each token, so errors
// inside a method still point at the right line.
word .u grabfn() {
	int cap = 768; word q = rt.new(cap); int n = 0, depth = 0; word nq;
	q[0] = 0;
	if (!is_op(s_lp)) { die("expected ( after the method name"); return q; }
	while (tk != T_EOF) {
		if (n * 3 + 4 > cap) {
			nq = rt.new(cap + cap);
			rt.copy_w(nq, q, cap);
			rt.free(q);
			q = nq;
			cap = cap + cap;
		}
		q[1 + n * 3] = tk; q[2 + n * 3] = tv; q[3 + n * 3] = tpack(); n++;
		if (is_op(s_lb)) depth++;
		else if (is_op(s_rb)) { depth--; if (depth <= 0) { next(); break; } }
		next();
	}
	if (tk == T_EOF && depth > 0) die("missing } at the end of a method");
	q[0] = n;
	return q;
}
// compile a method by feeding the parser fn Struct.name(Struct* this, rest...)
// build the token list "fn Struct.name ( Struct* this , rest..." from the
// method's saved tokens, push it as an input source and parse it as an
// ordinary top-level function. a method is therefore just a function whose
// first parameter is this; nothing else about it is special.
int tkput(word r, int k, int kind, int val, int pl) {
	r[1 + k * 3] = kind; r[2 + k * 3] = val; r[3 + k * 3] = pl;
	return k + 1;
}
// compile a struct method once the struct is complete.
int methdef(char* sn, char* mn, word q, int stat, int typed, int rty, int rtag) {
	int n = q[0]; word r; int i, k = 0, lnp, unchecked_method = stat & 2, unbounded_method = stat & 4, pc = (stat & 2) / 2 + (stat & 4) / 4;
 stat = stat & 1;
	if (!n) { rt.free(q); return 0; }
	if (!stat) {
		i = 1;
		while (i < n && q[2 + i * 3] != s_comma && q[2 + i * 3] != s_rp) {
			if (q[1 + i * 3] == T_ID && q[2 + i * 3] == s_this) serr("this is implicit and cannot be declared as a method parameter");
			i++;
		}
	}
	r = rt.new((n + 8 + mdg * 4) * 3 + 1);
	lnp = q[3];
	if (unchecked_method) k = tkput(r, k, T_ID, s_unchecked, lnp);
	if (unbounded_method) k = tkput(r, k, T_ID, s_unbounded, lnp);
 k = tkput(r, k, T_ID, s_fn, lnp);
	r[1 + k * 3] = T_ID; r[2 + k * 3] = methname(sn, mn); r[3 + k * 3] = lnp; k++;
	if (mdg) {	// a method of a generic struct is a generic function over the struct's parameters: fn S.m<K, V>(S<K, V>* this, ...)
		k = tkput(r, k, T_OP, s_lt, lnp);
		i = 0;
		while (i < mdg) {
			if (i) k = tkput(r, k, T_OP, s_comma, lnp);
			k = tkput(r, k, T_ID, mdn[i], lnp);
			i++;
		}
		k = tkput(r, k, T_OP, s_gt, lnp);
	}
	r[1 + k * 3] = q[1]; r[2 + k * 3] = q[2]; r[3 + k * 3] = q[3]; k++;
	if (stat && mdg) die("a static function can't be in a generic struct");
	if (!stat) {
	r[1 + k * 3] = T_ID; r[2 + k * 3] = sn; r[3 + k * 3] = lnp; k++;
	if (mdg) {
		k = tkput(r, k, T_OP, s_lt, lnp);
		i = 0;
		while (i < mdg) {
			if (i) k = tkput(r, k, T_OP, s_comma, lnp);
			k = tkput(r, k, T_ID, mdn[i], lnp);
			i++;
		}
		k = tkput(r, k, T_OP, s_gt, lnp);
	}
	r[1 + k * 3] = T_OP; r[2 + k * 3] = s_star; r[3 + k * 3] = lnp; k++;
	r[1 + k * 3] = T_ID; r[2 + k * 3] = s_this; r[3 + k * 3] = lnp; k++;
	}
	if (!stat && n > 1 && !(q[1 + 3] == T_OP && q[2 + 3] == s_rp)) {
		r[1 + k * 3] = T_OP;
		r[2 + k * 3] = s_comma;
		r[3 + k * 3] = lnp;
		k++;
	}
	i = 1;
	while (i < n) {
		r[1 + k * 3] = q[1 + i * 3];
		r[2 + k * 3] = q[2 + i * 3];
		r[3 + k * 3] = q[3 + i * 3];
		k++;
		i++;
	}
	r[0] = k;
	rt.free(q);
 if (typed && mdg) {
  // retain a typed generic method as ordinary typed function tokens.
  int mode = rt.outmode, length = rt.outn, capacity = rt.outcap, prefix = pc;
  word output = rt.outbuf, grow = rt.outgrow, buffer = rt.new(4096), return_tokens, joined;
  rt.outmode = 2; rt.outbuf = m*buffer; rt.outn = 0; rt.outcap = 4095; rt.outgrow = 0;
  tprint(rty); if (rtag) rt.put_s(".u"); buffer[rt.outn] = 0;
  rt.outmode = mode; rt.outbuf = output; rt.outn = length; rt.outcap = capacity; rt.outgrow = grow;
  return_tokens = tokens(buffer);
  int token = 0, variable;
  while (token < return_tokens[0]) {
   variable = 0;
   while (variable < ntl) {
    word descriptor = typelist[variable];
    if (descriptor[0] == TY_VAR && descriptor[3] < mdg && return_tokens[1 + token * 3] == T_ID && return_tokens[2 + token * 3] == descriptor[2]) return_tokens[2 + token * 3] = mdn[descriptor[3]];
    variable++;
   }
   token++;
  }
  joined = rt.new((r[0] + return_tokens[0]) * 3 + 1);
  joined[0] = r[0] - 1 + return_tokens[0];
  if (prefix) rt.copy_w(joined + 1, r + 1, prefix * 3);
  rt.copy_w(joined + 1 + prefix * 3, return_tokens + 1, return_tokens[0] * 3);
  rt.copy_w(joined + 1 + (prefix + return_tokens[0]) * 3, r + 1 + (prefix + 1) * 3, (r[0] - prefix - 1) * 3);
  rt.free(r); r = joined; rt.free(return_tokens); rt.free(buffer);
 }
	src_push(1, r, 0, 1);
	next();
	if (typed && !mdg) {
		// a typed method: skip the fn and the name, then compile from the ( with the declared return type
		next();
		next();
		ifkp = tpack(); ifkk = 0 - 1; if (isp != 0) ifkk = 0;
		o3nxt = 0; ntp = 0;
		fndone(fndef(1, rty, rtag, methname(sn, mn)), 0);
	} else topitem();
	if (tk != T_EOF) die("unexpected tokens after a method");
	src_pop();
	return 0;
}
// the call e.m(args): the receiver is on the stack and becomes this
// e.m(args): by now the receiver is on the stack, so it simply becomes the
// first argument. the call is checked against the method's signature if it
// has been compiled, and its result class is fresh if the method returns .u.
int methcall(int s, word rst, word receiver_fact, int receiver, word receiver_mask) {
	af_forget();
	int np, tags = 0, ret = 0, temporary, owner, aliases, i; word ft = stype[s]; word[8] bs; word owner_fact, origins;
	word requirements = effect_requirements, edges = effect_edges; int original = s;
	effect_args_mask(s, 0, receiver_mask);
	if (receiver_fact && (receiver_fact[2] == 4 || receiver_fact[2] == 5)) effect_require(s, 0, callpos);
	if (receiver >= 0 && tracked(lroot(receiver))) effect_require_mode(s, 0, callpos, 1);
	if (sflag[s] & F_SIG) { tags = ssig[s] >> 6; ret = ssig[s] & 1; }
	else sflag[s] = sflag[s] | F_UNTYPED;
	if (sflag[s] & F_RETOWN) ret = 1;
	rt.fill_w(bs, 0, 8);
	if (ft && rst) {
		word actual = rst; if (rst[0] == TY_STRUCT) actual = tptr(rst);
		if (!unify(ft[7], actual, bs)) tcerr("receiver", subst(ft[7], bs), actual);
	}
	ifcall = s; effect_argument_base = 1;
	np = args(tags >> 2, ft, bs, 0) + 1;
 temporary = argtemporary || (receiver_fact && receiver_fact[2] == 5); owner = argowner; owner_fact = argowner_fact; origins = argorigin_mask;
 if (effect_get(s, 0) & (EF_ALIAS | EF_IDENTITY | EF_UNKNOWN)) {
  origins = origins | receiver_mask;
  if (owner < 0) { owner = receiver; owner_fact = receiver_fact; }
  else if (owner != receiver) { owner = -1; owner_fact = 0; }
 }
	if ((sflag[s] & F_SIG) && np != ((ssig[s] >> 1) & 31)) serrn(sname[s], "wrong number of arguments");
	if (sflag[s] & F_GEN) { s = ginstance(s, bs); effect_specialize(original, s, requirements, edges); }
	if (!o3on && (sflag[s] & F_O3)) { o3_enter_code(); fnref(s); op(O_CALL); callname(intern("rt.o3_leave")); op(O_DROP); }	// into o3 from normal code, as call() does
	else { fnref(s); op(O_CALL); }
	lv = 0;
	lvk = LV_NONE;
	xzero = 0;
	xbor = -1;
	xconst = 0;
	xfloat = 0;
	xstr = 0;
	xlenloc = -1;
	xstamp = 0;
	xty = tword;
	if (ft) xty = subst(ft[4], bs);
	if (!o3on && (sflag[s] & F_O3) && ft && hasptr(xty)) { lit(xty); callname(s_fatten); }	// non-o3 called o3: fatten the result here
	if (isfl(xty)) xfloat = 1;
 effect_value = 0;
 if (!ret && (isptr(xty) || xty == tword)) {
  effect_value = origins;
  if (isptr(xty)) xbor = owner;
  if (temporary) { aliases = 0; i = 0; while (i < np) { aliases = aliases | effect_get(s, i); i++; } if (aliases & (EF_ALIAS | EF_UNKNOWN)) xaf = af_new(-1, 5, callpos); }
 }
	if (ret) return C_FRESH;
	return C_PLAIN;
}
// type name = T;
// the type keyword makes an alias, which is also how a pointer to an array or
// function type gets a name.
int kw_type() {
	int n;
	next();
	n = name();
	expect(s_eq);
	addsym(n, K_TYPE, ptype());
	expect(s_semi);
	return 0;
}
// does a parameter start with a type? a type name straight before , or ) is the parameter's
// own name (fn f(string)), not a type, since a typed parameter always has a name after it.
int paramstart() {
	if (tk == T_OP) return tv == s_lk;
	if (tk != T_ID) return 0;
	if (tv == s_fn) return 1;
	if (!istypename(tv)) return 0;
	peek();
	return !(pk_tk == T_OP && (pk_tv == s_comma || pk_tv == s_rp));
}
// does a typedef start here? typedef followed by a name is one, so typedef can still be
// a variable or a function's name.
int typedef_ahead() {
	if (tk != T_ID || tv != s_typedef) return 0;
	peekat(0);
	return pk_tk == T_ID;
}
// unlink the symbol s from its name, leaving the rest of the name's chain as it was.
int td_unlink(int s) {
	char* nm = sname[s]; int i = nm[-1] - 1;
	if (i == s) { nm[-1] = snext[s]; return 0; }
	while (i >= 0 && snext[i] - 1 != s) i = snext[i] - 1;
	if (i >= 0) snext[i] = snext[s];
	return 0;
}
// end the scope of the local typedefs made at block depth depth or deeper in this
// compile context (and of any made in a context nested inside it).
int td_end(int depth) {
	int k;
	while (ntd) {
		k = ntd * 3 - 3;
		if (tdstk[k + 2] < ctxsp || (tdstk[k + 2] == ctxsp && tdstk[k + 1] < depth)) break;
		td_unlink(tdstk[k]);
		ntd--;
	}
	return 0;
}
// is the name q (as a symbol is named) already a typedef of the block being compiled?
int td_here(char* q) {
	int k = ntd;
	while (k) {
		k--;
		if (tdstk[k * 3 + 2] != ctxsp || tdstk[k * 3 + 1] != fdepth) break;
		if (sname[tdstk[k * 3]] == q) return 1;
	}
	return 0;
}
// typedef T name;
// the C spelling of type name = T;. name becomes another way to write T: the very same
// type record, so the two are interchangeable everywhere. at the top level the name is
// global; in a function it lasts to the end of its block, like a local. a name that is
// already in use is an error, except the same type under the same name again. a tag
// (.u, .m, .d) belongs to a declaration, not to a type, so a typedef has none.
int kw_typedef() {
	char* n; char* q; word t; int s, at, clash = 0, local = infn;
	next();
	t = ptype();
	if (panic) return 0;
	if (is_op(s_dot)) { die("a typedef names a type, which has no tag: .u, .m and .d go on a declaration"); return 0; }
	at = toff; n = name();
	if (panic) return 0;
	q = module_symbol(n);
	if (local) {
		s = findloc(n);
		if ((s >= 0 && lhome[s] >= fdepth) || td_here(q)) clash = 1;
	} else {
		s = lookup_raw(q);
		if (s < 0 && module_name) { s = lookup_raw(n); if (s >= 0 && skind[s] != K_TYPE && skind[s] != K_KW) s = 0 - 1; }
		if (s >= 0 && skind[s] == K_TYPE && sval[s] == t) return expect(s_semi);	// the same typedef again
		if (s >= 0) clash = 1;
	}
	if (clash) serrn(n, "already defined");
	else {
		s = addsym(n, K_TYPE, t);
		rs_put(at, RS_SYM, rs_sym(s), s);
		if (local) {
			if (ntd == tdcap) { if (tdcap) tdcap = tdcap * 2; else tdcap = 16; tdstk = chk_resize(tdstk, ntd * 3, tdcap * 3); }
			tdstk[ntd * 3] = s; tdstk[ntd * 3 + 1] = fdepth; tdstk[ntd * 3 + 2] = ctxsp; ntd++;
		}
	}
	expect(s_semi);
	return 0;
}
// (T) or (T*) ahead of the current '(', within the lookahead we have
// the parser sees ( and has to decide between a parenthesized expression and a
// cast. a cast is ( type stars ) so peek ahead through the stars to the ).
int caststart() {
	int k;
	peek();
	if (pk_tk == T_ID && (istypename(pk_tv) || pk_tv == s_fn)) {
		k = 1; peekat(k);
		if (pk_tk == T_OP && (pk_tv == s_lk || pk_tv == s_lt || (pk_tv == s_lp && pq_tv[0] == s_fn))) return 1;
		while (pk_tk == T_OP && pk_tv == s_star && k < 3) { k++; peekat(k); }	// (int*)x, (node**)x
		return pk_tk == T_OP && pk_tv == s_rp;
	}
	return 0;
}