path: root/src/compiler/analyzer.zc

// ---- function effects and temporary borrows ----

word effect_record(int symbol) {
 if (symbol < 0) return 0;
 if (!effect_symbols) effect_symbols = chk_resize(0, 0, symcap);
 if (!effect_symbols[symbol]) effect_symbols[symbol] = chk_resize(0, 0, 50);
 return effect_symbols[symbol];
}
// trusted runtime contracts apply only to built-ins, never a user function with the same name.
int effect_contract(int symbol, int parameter) {
 word n;
 if (symbol < 0 || symbol >= ubase) return EF_UNKNOWN;
 n = sname[symbol];
 if (n == s_put_s || rt.eq_w(n, "rt.put_bs") || rt.eq_w(n, "rt.len_w") || rt.eq_w(n, "rt.len_s") || rt.eq_w(n, "rt.eq_w") || rt.eq_w(n, "rt.eq_s") || rt.eq_w(n, "rt.at_s") || rt.eq_w(n, "rt.put_n") || rt.eq_w(n, "rt.put_c")) return EF_READ;
 if (n == s_free || n == s_recycle) return EF_CONSUME;
 if (rt.eq_w(n, "rt.copy_w")) { if (!parameter) return EF_WRITE; return EF_READ; }
 if (rt.eq_w(n, "rt.fill_w")) { if (!parameter) return EF_WRITE; return EF_READ; }
 return EF_UNKNOWN;
}
int effect_get(int symbol, int parameter) {
 word r;
 if (parameter < 0 || parameter >= 24) return EF_UNKNOWN;
 if (symbol < 0 || symbol >= nsym) return EF_UNKNOWN;
 if (symbol < ubase) return effect_contract(symbol, parameter);
 r = effect_record(symbol);
 if (r[0] != 1 || (sflag[symbol] & F_EXT)) {
  if (parameter < 12 && (((ssig[symbol] >> 6) >> (parameter + parameter)) & 3) == 1) return EF_READ | EF_WRITE | EF_ALIAS;
  return EF_UNKNOWN;
 }
 return r[2 + parameter];
}
int effect_origin(int c) {
 int i = xbor;
 if (c >= C_VAR) i = c - C_VAR;
 if (i < lbase || i >= nloc) return -1;
 if (local_origin && local_origin[i] >= 0) return local_origin[i];
 if (lrskind[i] == RS_PARAM && i - lbase < 24) return i - lbase;
 return -1;
}
word effect_mask(int c) {
 int i;
 if (c >= C_VAR) {
  i = c - C_VAR;
  if (local_origin_mask && local_origin_mask[i]) return local_origin_mask[i];
  if (i >= lbase && lrskind[i] == RS_PARAM && i - lbase < 24) return 1 << (i - lbase);
 }
 return effect_value;
}
int effect_note_mask(word mask, int flags) {
 int i = 0;
 while (mask && i < 24) { if (mask & 1) effect_note(i, flags); mask = mask >> 1; i++; }
 return 0;
}
int effect_args_mask(int callee, int parameter, word mask) {
 int i = 0;
 while (mask && i < 24) { if (mask & 1) effect_arg(callee, parameter, i); mask = mask >> 1; i++; }
 return 0;
}
int effect_note(int origin, int flags) {
 if (effect_current && origin >= 0 && origin < 24) { effect_current[2 + origin] = effect_current[2 + origin] | flags; effect_current[26 + origin] = effect_current[26 + origin] | flags; }
 return 0;
}
int effect_arg(int callee, int parameter, int origin) {
 word e;
 if (!effect_current || origin < 0) return 0;
 e = talloc(6); e[0] = effect_edges; e[1] = effect_current; e[2] = origin; e[3] = callee; e[4] = parameter; e[5] = 0;
 effect_edges = e; return 0;
}
int effect_require_mode(int callee, int parameter, int place, int mode) {
 word e;
 if (!fchk || !live || dry) return 0;
 e = talloc(7); e[6] = mode;
 e[5] = effect_floor;
 e[0] = effect_requirements; e[1] = callee; e[2] = parameter; e[3] = place; e[4] = curinc;
 effect_requirements = e; return 0;
}
int effect_require(int callee, int parameter, int place) { return effect_require_mode(callee, parameter, place, 0); }
// argument checks for a generic call use the instantiated body's effects.
int effect_specialize(int original, int instance, word requirements, word edges) {
	word e = effect_requirements;
	while (e && e != requirements) { if (e[1] == original) e[1] = instance; e = e[0]; }
	e = effect_edges;
	while (e && e != edges) { if (e[3] == original) e[3] = instance; e = e[0]; }
	return 0;
}
int effect_finish(int from) {
 word e, r, next; int changed = 1, flags, prior, save = tpack(), inc = curinc, i = 0;
 if (chkabort) return 0;
 // direct body effects are immutable inputs; recompute callee effects so an earlier nested unit cannot leave stale unknowns.
 while (effect_symbols && i < nsym) { r = effect_symbols[i]; if (r) rt.copy_w(r + 2, r + 26, 24); i++; }
 while (changed) {
  changed = 0; e = effect_edges;
  while (e) {
   r = e[1]; flags = effect_get(e[3], e[4]) & ~(EF_ALIAS | EF_IDENTITY); prior = r[2 + e[2]];
   r[2 + e[2]] = prior | flags; if (prior != r[2 + e[2]]) changed = 1;
   e = e[0];
  }
 }
 e = effect_requirements; effect_requirements = 0;
 while (e) {
  next = e[0];
  if (e[5] < from) { e[0] = effect_requirements; effect_requirements = e; e = next; continue; }
  flags = effect_get(e[1], e[2]);
  if ((!e[6] && (flags & (EF_RETAIN | EF_CONSUME | EF_UNKNOWN))) || (e[6] && !(flags & EF_UNKNOWN) && (flags & (EF_RETAIN | EF_CONSUME)))) {
   tunpack(e[3]); curinc = e[4];
   if (e[6]) serr("this callee retains or consumes a borrowed owner; declare its parameter .d to transfer ownership");
   else if (flags & EF_UNKNOWN) serr("a temporary argument requires a proved non-escaping borrow; bind it to a name first or provide an explicit parameter contract");
   else serr("a temporary argument requires a proved non-escaping borrow; this callee retains or consumes it, so transfer ownership through a .d parameter");
   panic = 0;
  }
  e = next;
 }
 tunpack(save); curinc = inc; return 0;
}
int borrow_begin() { return 0; }
int borrow_prologue() { borrow_jump = hole(); op(O_JMP); borrow_entry = here; return 0; }
int borrow_initializer() {
 word p = borrow_slots;
 if (borrow_jump < 0) return 0;
 if (!p) { setlit(borrow_jump, borrow_entry); return 0; }
 setlit(borrow_jump, here);
 while (p) { lit(0); laddr(p[1]); op(O_ST); p = p[0]; }
 jmp(borrow_entry); return 0;
}
int emit_borrow_hold() {
 word p;
 if (!infn) { cerr("temporary borrow outside a function"); return 0; }
 p = talloc(2); p[0] = borrow_slots; p[1] = fslots; fslots++; borrow_slots = p;
 lit(0); op(O_PICK); laddr(p[1]); op(O_ST); borrow_pending++; return 0;
}
// release only temporaries introduced by this full expression. zero slots cover untaken branches.
int borrow_cleanup_since(word stop) {
 word p = borrow_slots; int skip;
 while (p && p != stop) {
  laddr(p[1]); op(O_LD); skip = hole(); op(O_JZ);
  laddr(p[1]); op(O_LD); callname(s_recycle); op(O_DROP);
  lit(0); laddr(p[1]); op(O_ST); setlit(skip, here); p = p[0];
 }
 return 0;
}
int borrow_cleanup() { return borrow_cleanup_since(0); }
int borrow_condition() {
 word before = borrow_slots; int c = expr(); rval(); plainuse(c); ftest(); borrow_cleanup_since(before); return c;
}

// ---- locals and the analyzer's view of them ----

// value tracking is for check mode only; it never changes emitted code.
int vf_symbols() {
	if (!svkind) { svkind = chk_resize(0, 0, symcap); svvalue = chk_resize(0, 0, symcap); }
	return 0;
}
int vf_at(int r, int kind, word value) {
	if (!cmode || dry || chkind != 3 || chbase != rsbase || r < 0 || r >= rsn) return 0;
	rsrec[r * RS_W + 9] = kind; rsrec[r * RS_W + 10] = value; return 0;
}
char* vf_string(char* text) {
	word p; int n;
	if (!cmode || dry) return 0;
	n = rt.len_w(text) + 1; p = talloc(n); rt.copy_w(p, text, n); return p;
}
int vf_forget() {
	if (!cmode || dry) return 0;
	if (lvkind) rt.fill_w(lvkind + lbase, 0, nloc - lbase);
	if (svkind) rt.fill_w(svkind, 0, nsym);
	xvk = 0; return 0;
}
// a call or indirect write can change globals, escaped locals, and string data.
int vf_effect() {
	int i = lbase;
	if (!cmode || dry) return 0;
	while (i < nloc) { if (lvescaped[i] || lvkind[i] >= 3) lvkind[i] = 0; i++; }
	if (svkind) rt.fill_w(svkind, 0, nsym);
	xvk = 0; return 0;
}
word vf_i2f(word v) { return asm { v @ #1216 }; }
word vf_f2i(word v) { return asm { v @ #1218 }; }
word vf_negf(word v) { return asm { 0.0 v @ #1204 }; }
int vf_coerce(word t, int convert) {
	if (!xvk || !t) return 0;
	if (xvk >= 3) { if (t != tword && t != tbstr && t[0] != TY_PTR) xvk = 0; return 0; }
	if (isfl(t)) {
		if (xvk == 1) { if (convert) xvv = vf_i2f(xvv); xvk = 2; }
		if (t == tf32 && convert) xvv = rt.zs2f(rt.zf2s(xvv));
	} else {
		if (xvk == 2 && convert && isnum(t)) xvv = vf_f2i(xvv);
		xvk = 1; xvv = cnorm(t, xvv);
	}
	return 0;
}
int vf_store(int i) {
	if (!cmode || dry || !live) return 0;
	lvkind[i] = xvk; lvvalue[i] = xvv; return 0;
}

// these warnings add no ownership rules. facts are discarded at control-flow
// joins and after unknown effects, so a possible failure is never called definite.
word af_new(int length, int kind, int place) {
	word f;
	if (dry || stubgen) return 0;
	f = talloc(15); rt.fill_w(f, 0, 15); f[0] = length; f[1] = 1; f[2] = kind;
	f[3] = place; f[4] = 0; f[5] = -1;
	return f;
}
// owner-relative projections retain provenance and the array generation at the time of borrowing.
word af_base(word f) { while (f && f[6]) f = f[6]; return f; }
word af_project(word f, int offset, int extent, int place, int elements) {
 word p, base = af_base(f); int start = offset;
 if (!f || !base) return 0;
 if (f[6] && f[7] >= 0 && offset >= 0) start = f[7] + offset;
 p = af_new(extent, base[2], base[3]);
 if (!p) return 0;
 p[1] = base[1]; p[4] = base[4]; p[5] = base[5]; p[6] = base; p[7] = start;
 p[8] = elements; p[9] = base[10]; p[12] = place;
 if (base[2] == 3) p[2] = 2;
 if (elements) {
  p[0] = -1;
  if (offset >= 0 && f[0] >= 0) { p[0] = f[0] - offset; p[13] = f[13] - offset; p[14] = 1; }
 }
 return p;
}
int af_mutate(word f, int place) {
 word base = af_base(f);
 if (!base || dry || !live) return 0;
 af_mutation_tick++; base[10] = af_mutation_tick; base[11] = place; base[0] = -1; return 0;
}
int af_projection_access(word f, int place) {
 word base; int saved;
 if (!f || !f[6] || !f[8]) return 0;
 base = af_base(f);
 if (base[10] < 0 || base[10] == f[9] || dry || !live) return 0;
 saved = tpack(); tunpack(place);
 if (fchk) { if (panic) { tunpack(saved); return 0; } errat(); }
 else if (!af_warning(place)) { tunpack(saved); return 0; }
 rt.put_s("element borrow was invalidated by array mutation on line "); rt.put_n(base[11] & 0xFFFFFF);
 rt.put_s("; borrow created on line "); rt.put_n(f[12] & 0xFFFFFF);
 if (fchk) errend(); else af_warning_end(); tunpack(saved); return 0;
}

int af_forget() {
	vf_forget();
	int i = lbase;
	while (i < nloc) { lafact[i] = 0; i++; }
	xaf = 0; return 0;
}
// an unknown callee may change a passed allocation's length or lifetime.
int af_escape(word f) {
	if (f) { word base = af_base(f); base[0] = -1; base[1] = 0; base[10] = -1; f[0] = -1; f[1] = 0; }
	return 0;
}
int af_store(int i) {
	if (!dry) lafact[i] = xaf;
	return 0;
}
int af_expired(word f) {
 word base;
 if (!f) return 0;
 if (f[1] == 2) return 1;
 if (!f[6] || !f[8]) return 0;
 base = af_base(f); return base[10] >= 0 && base[10] != f[9];
}
int af_snapshot(word f) {
 if (f && f[6] && af_expired(f)) { f[1] = 2; f[4] = af_base(f)[11]; }
 return 0;
}
int af_record(int off, word f) {
	int at;
	if (!f || !cmode || dry || chkind != 3 || chbase != rsbase || !rsn) return 0;
	af_snapshot(f);
	at = (rsn - 1) * RS_W;
	if (rsrec[at] != off) return 0;
	rt.copy_w(rsrec + at + 4, f, 5); return 0;
}
// keep declaration previews as well as the facts at each use site.
int af_declaration(int off, word f) {
	int i = rsn;
	if (!f || !cmode || dry || chkind != 3 || chbase != rsbase) return 0;
	while (i) { i--; if (rsrec[i * RS_W] == off) { rt.copy_w(rsrec + i * RS_W + 4, f, 5); return 0; } }
	return 0;
}
int af_warning(int place) {
	int sv;
	if (dry || panic || chkabort || stubgen || !live) return 0;
	sv = tpack(); tunpack(place);
	if (cmode) dg_open(2);
	else { rt.put_s("zc: line "); rt.put_n(tline); rt.put_s(": warning: "); }
	tunpack(sv); return 1;
}
int af_warning_end() { if (cmode) dg_close(); else rt.put_c(10); return 0; }
int af_access(word f, int place) {
 af_projection_access(f, place); if (f && f[6]) { word base = af_base(f); f[1] = base[1]; f[4] = base[4]; }
	if (!f || f[1] != 2 || !af_warning(place)) return 0;
	rt.put_s("use after free: this storage's lifetime ended on line ");
	rt.put_n(f[4] & 0xFFFFFF); af_warning_end(); return 0;
}
int af_use(word f, int place, int c) {
 if (fchk && c >= C_VAR && lstate[lroot(c - C_VAR)] == S_DEAD) return 0;
 return af_access(f, place);
}
int af_index(word f, int place) {
	int lower = 0;
 if (f && f[6]) { word base = af_base(f); if (base[1] == 0 || base[10] < 0) return 0; if (f[14]) lower = f[13]; }
 if (!f || f[1] == 2 || f[0] < 0 || !xconst || (xcval >= lower && xcval < f[0])) return 0;
	if (!af_warning(place)) return 0;
	rt.put_s("out-of-bounds access: index "); rt.put_n(xcval);
	rt.put_s(" is outside length "); rt.put_n(f[0]); rt.put_s(" (storage declared or allocated on line "); rt.put_n(f[3] & 0xFFFFFF); rt.put_c(')'); af_warning_end(); return 0;
}
// freeing an alias ends the same allocation as freeing its original name.
int af_end(word f, int place) {
	if (f && !dry && live) { f[1] = 2; f[4] = place; }
	return 0;
}
int af_close(int save) {
	int i = save; word f;
	if (dry) return 0;
	while (i < nloc) {
		f = laaddr[i]; if (f && f[2] == 1) af_end(f, tpack());
		f = lafact[i];
		if (f && fchk && lstate[i] == S_M && lown[i] && !local_captured[i]) af_end(f, tpack());
		i++;
	}
	return 0;
}
// the analyzer's model of a local. locals are numbered in declaration order
// and every fact about one lives in a parallel array indexed by that number
// (see the data region). for ownership the ones that matter are:
//   lstate   what the local holds right now:
//              S_PLAIN   nothing tracked (a number, or untracked memory)
//              S_M       owns an object; the compiler frees it when the block ends
//              S_U       owns one that has to leave the block (return it, make
//                        it the block's value, or assign it to the enclosing block)
//              S_D       was handed in to be given away, and hasn't been yet
//              S_DEAD    the object is gone (given away); any use is an error
//              S_CHILD   the object belongs to a container, lowner says which local
//              S_BORROW  a .m parameter: usable but not freeable or storable
//   lhome    the block depth that owns the object (fdepth where it was declared)
//   lown     1 once the local has owned an object, lused the line of its last use
//   ltag     the tag written on the declaration, plus the flag bits (float,
//            byte string, o3 register, hint bits)
// fchk says the function being compiled is analyzed at all (unchecked turns
// it off) and live says the code just emitted is reachable. ownership rules
// return when fchk is off; definite storage warnings also inspect unchecked code.
// findloc looks a name up among the current function's locals, innermost first.
// name heads and shadow links keep declaration and use lookup independent of
// the number of earlier locals. dropping a scope restores the previous heads.
int local_bucket(int n, int cap) { return ((n ^ (n >> 16)) * 0x9E37) & (cap - 1); }
int local_key(int n) {
	int k = local_bucket(n, lkeycap);
	while (lkeys[k] && lkeys[k] != n) k = (k + 1) & (lkeycap - 1);
	return k;
}
int local_bind(int n, int i) {
	int k, j, at, cap; word keys, heads;
	if (lkeyn + lkeyn >= lkeycap) {
		keys = lkeys; heads = lheads; cap = lkeycap * 2;
		lkeys = chk_resize(0, 0, cap); lheads = chk_resize(0, 0, cap);
		j = 0;
		while (j < lkeycap) {
			if (keys[j]) { at = local_bucket(keys[j], cap); while (lkeys[at]) at = (at + 1) & (cap - 1); lkeys[at] = keys[j]; lheads[at] = heads[j]; }
			j++;
		}
		lkeycap = cap;
	}
	k = local_key(n);
	if (!lkeys[k]) { lkeys[k] = n; lheads[k] = -1; lkeyn++; }
	lprev[i] = lheads[k]; lheads[k] = i; return 0;
}
int local_drop(int save) {
	int i = nloc, k;
	while (i > save) { i--; k = local_key(lname[i]); lheads[k] = lprev[i]; }
	nloc = save; return 0;
}
int findloc(int n) {
	int k = local_key(n), i;
	if (!lkeys[k]) return -1;
	i = lheads[k];
	while (i >= nloc) i = lprev[i];
	if (i >= lbase) return i;
	return -1;
}
// declare a local: take the next slot in the frame (fslots) and reset every
// per-local fact so a reused index never inherits the old variable's state
int newloc(int n) {
	int i = nloc;
	if (nloc >= loccap) reserve_locals(nloc + 1);
	nloc++;
	lname[i] = n; local_bind(n, i); lslot[i] = fslots; lhome[i] = fdepth; lstate[i] = S_PLAIN; lsmark(0, n);
	if (!local_origin) local_origin = chk_resize(0, 0, loccap); local_origin[i] = -1;
	if (if_local) if_local[i] = 0;
 if (!local_origin_mask) local_origin_mask = chk_resize(0, 0, loccap); local_origin_mask[i] = 0;
 if (!local_cell) local_cell = chk_resize(0, 0, loccap); local_cell[i] = 0;
 if (!local_captured) local_captured = chk_resize(0, 0, loccap); local_captured[i] = 0;
 if (!local_ended) local_ended = chk_resize(0, 0, loccap); local_ended[i] = 0;
 if (!local_end_info) local_end_info = chk_resize(0, 0, loccap); local_end_info[i] = 0;
	lpos[i] = 0;
	lreadpos[i] = 0;
	lowner[i] = 0;
	lrsoff[i] = 0 - 1; lrskind[i] = RS_LOCAL;
	lused[i] = 0;
	larr[i] = 0;
	lown[i] = 0;
	ltype[i] = tword;
	ltag[i] = 0;
	o3cache[i] = 0;
	lafact[i] = 0; laaddr[i] = 0;
	if (cmode) {
		if (!lvkind) { lvkind = chk_resize(0, 0, loccap); lvvalue = chk_resize(0, 0, loccap); lvescaped = chk_resize(0, 0, loccap); }
		lvkind[i] = 0; lvvalue[i] = 0; lvescaped[i] = 0;
	}
	return i;
}
// a local's known lower bound, and the array whose length it holds. -1 is unknown.
// the table is dropped as scopes close, so a reused slot does not keep the old fact.
word getlo(int i) {
	int k = 0;
	while (k < nfact) {
		if (floc[k] == i) return flo[k];
		k++;
	}
	return -1;
}
// the length of the recorded fact for line i, or -1 when there is none.
word getln(int i) {
	int k = 0;
	while (k < nfact) {
		if (floc[k] == i) return flen[k];
		k++;
	}
	return -1;
}
// record the range lo to lo+ln for line i.
int putfact(int i, int lo, int ln) {
	int k = 0;
	while (k < nfact) { if (floc[k] == i) { flo[k] = lo; flen[k] = ln; return 0; } k++; }
	if (lo < 0 && ln < 0) return 0;
	if (nfact >= factcap) {
		floc = chk_resize(floc, nfact, factcap * 2); flo = chk_resize(flo, nfact, factcap * 2); flen = chk_resize(flen, nfact, factcap * 2);
		factcap = factcap * 2;
	}
	floc[nfact] = i; flo[nfact] = lo; flen[nfact] = ln; nfact++;
	return 0;
}
// drop the recorded facts from line from onward.
int fdrop(int from) {
	int k = 0, w = 0;
	while (k < nfact) {
		if (floc[k] < from) {
			if (w != k) { floc[w] = floc[k]; flo[w] = flo[k]; flen[w] = flen[k]; }
			w++;
		}
		k++;
	}
	nfact = w;
	return 0;
}
// a loop fact stores three full local indices: the
// induction variable, its bound and the array the bound is the length of. a
// loop "for (i = 0; i < len(a); i++)" records (i, bound, a) in lpfact, which
// is how proven() knows that a[i] needs no bounds check inside it.
int pfact(int iv, int bd, int ar) { word p = talloc(3); p[0] = iv; p[1] = bd; p[2] = ar; return p; }
// the induction variable of a loop proof.
int p_iv(int w) { return w[0]; }
// the array's bound in a loop proof.
int p_bd(int w) { return w[1]; }
// the array a loop proof refers to.
int p_ar(int w) { return w[2]; }
// a store to the induction variable, the bound, or the array ends the proof
int bpoison(int i) {
	int k = lsp, w;
	while (k > loopbase) {
		k--;
		w = lpfact[k];
		if (w >= 0 && (p_iv(w) == i || p_bd(w) == i || p_ar(w) == i)) lpfact[k] = -1;
	}
	return 0;
}
// note a store to a local: a constant or a length it now holds.
int note_store(int i) {
	if (if_local && !dry) {
		if (!if_local[i]) if_local[i] = chk_resize(0, 0, 1);
		if (if_value) if_link(if_local[i], if_value);
		else if (xty == tword) *if_local[i] = -1;
		if_join(if_local[i], xty);
	}
	int lo = -1, ln = -1;
	if (xconst && xcval >= 0) lo = xcval;
	if (xlenloc >= 0) ln = xlenloc;
	putfact(i, lo, ln);
	bpoison(i);
	return 0;
}
// i >= 0 and i < len(a), proved by the loop test and a step of +1
int proven(int a, int ix) {
	int k = lsp, w;
	if (ltype[a][0] != TY_DYN || !ltype[a][3] || tbytes(ltype[a][4])) return 0;
	while (k > loopbase) {
		k--;
		w = lpfact[k];
		if (w >= 0 && p_iv(w) == ix && p_ar(w) == a) return 1;
	}
	return 0;
}
// i >= 0 and i < n for a fixed array of n elements, proved by a loop test
// against a constant of at most n and a step of +1 (kw_for records the
// constant as the array field, minus two, with -1 for the bound local)
int proven_n(int ix, int n) {
	int k = lsp, w;
	while (k > loopbase) {
		k--;
		w = lpfact[k];
		if (w >= 0 && p_iv(w) == ix && p_bd(w) == -1 && 0 - p_ar(w) - 2 <= n) return 1;
	}
	return 0;
}
// ---- loop bodies and hoisted checks ----

// a loop proof only holds while the body leaves the index, the bound and the
// array alone. the compiler reads the body once, in order, so before it
// compiles one it reads its tokens ahead (as capture_scan does) and notes
// every name the body assigns, increments, decrements or takes the address
// of. the record is r = lpinfo + depth * LPI_W: r[0] is 1 when the scan could
// not see the whole body (the source is stdin, it ran out) or found a closure
// (which can change any captured local), and then every name counts; r[1]
// names follow from r[2], at most 32. the body is read as one statement, the
// way the parser will read it (bs_stmt).
// r[40] the loop's index variable (or -1), r[41] its bound, r[42] the entry
// jump to patch, r[43] how many hoisted checks, r[44..47] their element
// counts, r[48..51] their flag slots, r[52] 1 when checks against the bound
// can be hoisted, r[53] 1 when index and bound are left alone, r[54] 1 when
// the record is in use, r[55] 1 when the body might free or resize a block
// (any pointer, which may alias the one a proof is about): it calls a function,
// uses push, pop, resize, defer, asm, quote or new, or stores to a local that
// can own a block. then the size a pointer proof read can change. r[56] the
// allocation facts of the locals at the loop entry (lafact_save), which the
// loop top forgets.
int body_name(word r, int nm) {
	if (r[1] >= 32) { r[0] = 1; return 0; }
	r[2 + r[1]] = nm; r[1]++;
	return 0;
}
// can a store to the name nm free a block? a store to a pointer, a word or
// an array local can (an owner frees what it held), and so can one to a name
// the loop declares, unless a number type comes right before it (pk2, pv2: the
// token before the name)
int body_mayfree(int nm, int pk2, int pv2) {
	int j = findloc(nm); word t;
	if (j < 0) return !(pk2 == T_ID && (pv2 == sx_int || pv2 == sx_char || pv2 == sx_bool || pv2 == sx_float));
	t = ltype[j];
	if (!t || t == tword || isptr(t) || t[0] == TY_DYN || tracked(j)) return 1;
	return 0;
}
// the scan's view of the token before the current one and the one before that
int bs_pk, bs_pv, bs_pk2, bs_pv2;
// note what the current token says about the body, then read the next one
int bs_adv(word r) {
	int j;
	if (is_id(s_fn)) { peek(); if (pk_tk == T_OP && (pk_tv == s_lp || pk_tv == s_colon)) r[0] = 1; }
	if (tk == T_OP && bs_pk == T_ID && (tv == s_eq || tv == s_inc || tv == s_dec || asgfind(tv) >= 0)) { body_name(r, bs_pv); if (body_mayfree(bs_pv, bs_pk2, bs_pv2)) r[55] = 1; }
	if (tk == T_ID && bs_pk == T_OP && (bs_pv == s_inc || bs_pv == s_dec || bs_pv == s_amp)) body_name(r, tv);
	if (tk == T_OP && tv == s_lp && bs_pk == T_ID) { j = lookup(bs_pv); if (j < 0 || skind[j] != K_KW) r[55] = 1; }
	if (tk == T_ID && (tv == sx_push || tv == sx_pop || tv == sx_resize || tv == sx_defer || tv == sx_asm || tv == sx_quote || tv == sx_new)) r[55] = 1;
	bs_pk2 = bs_pk; bs_pv2 = bs_pv; bs_pk = tk; bs_pv = tv;
	next();
	return 0;
}
// a bracketed group from the current ( [ or {, through its closer
int bs_group(word r) {
	int depth = 0;
	while (1) {
		if (tk == T_EOF) { r[0] = 1; return 0; }
		if (tk == T_OP && (tv == s_lb || tv == s_lp || tv == s_lk)) depth++;
		else if (tk == T_OP && (tv == s_rb || tv == s_rp || tv == s_rk)) depth--;
		bs_adv(r);
		if (depth <= 0) return 0;
	}
	return 0;
}
// one statement, read the way the parser will: a block, if/else, a loop or
// switch with its body, do/while, or anything else up to its ; at depth 0
int bs_stmt(word r) {
	int depth = 0;
	if (tk == T_EOF) { r[0] = 1; return 0; }
	if (is_op(s_lb)) return bs_group(r);
	if (is_id(sx_if)) {
		bs_adv(r); if (is_op(s_lp)) bs_group(r);
		bs_stmt(r);
		if (is_id(sx_else)) { bs_adv(r); bs_stmt(r); }
		return 0;
	}
	if (is_id(sx_while) || is_id(sx_for) || is_id(sx_switch)) {
		bs_adv(r); if (is_op(s_lp)) bs_group(r);
		return bs_stmt(r);
	}
	if (is_id(sx_do)) {
		bs_adv(r); bs_stmt(r);
		if (is_id(sx_while)) { bs_adv(r); if (is_op(s_lp)) bs_group(r); }
		if (is_op(s_semi)) bs_adv(r);
		return 0;
	}
	while (1) {
		if (tk == T_EOF) { r[0] = 1; return 0; }
		if (tk == T_OP && (tv == s_lb || tv == s_lp || tv == s_lk)) depth++;
		else if (tk == T_OP && (tv == s_rb || tv == s_rp || tv == s_rk)) { depth--; if (depth < 0) return 0; }
		if (depth == 0 && is_op(s_semi)) { bs_adv(r); return 0; }
		bs_adv(r);
	}
	return 0;
}
int body_scan(word r) {
	word old, f; int docs = docs_on, record = grec, sp = panic;
	r[0] = 0; r[1] = 0; r[55] = 0;
	if (isp < 0 || R_SRC[isp * 32] == 0) { r[0] = 1; return 0; }
	src_push(1, capture_dummy, 0, 0); old = R_SRC + (isp - 1) * 32; f = R_SRC + isp * 32;
	f[0] = old[0]; f[1] = old[1]; f[2] = old[2]; f[3] = old[3]; f[4] = 0; pq_n = f[14];
	docs_on = 0; grec = 0; dry++;
	bs_pk = 0; bs_pv = 0; bs_pk2 = 0; bs_pv2 = 0;
	bs_stmt(r);
	dry--; src_pop(); docs_on = docs; grec = record; panic = sp;
	return 0;
}
// may the loop body behind r change the local named nm?
int ldirty(word r, int nm) {
	int k = 0;
	if (!r || r[0]) return 1;
	while (k < r[1]) { if (r[2 + k] == nm) return 1; k++; }
	return 0;
}
// a local nothing outside the function's own code can change: no address
// taken, not captured by a closure
int lclean(int i) {
	if (laaddr[i]) return 0;
	if (local_cell && local_cell[i]) return 0;
	if (local_captured && local_captured[i]) return 0;
	return 1;
}
// a fresh record for the loop at depth k, or 0 past the first LPI_N depths
word linfo_new(int k) {
	word r;
	if (k >= LPI_N) return 0;
	if (!lpinfo) lpinfo = chk_resize(0, 0, LPI_N * LPI_W);
	r = lpinfo + k * LPI_W;
	rt.fill_w(r, 0, LPI_W);
	r[54] = 1;
	return r;
}
// the record of the live loop at depth k, or 0
word linfo(int k) {
	word r;
	if (k >= LPI_N || !lpinfo) return 0;
	r = lpinfo + k * LPI_W;
	if (!r[54]) return 0;
	return r;
}
// for a check of index ix against n elements of the array local arr (-1 for
// a fixed array) inside a loop "for (...; ix < bound; ix++)" whose body leaves
// ix and bound alone: the loop entry works out once whether ix < bound <= n
// can fail (0 <= ix at the entry, bound <= n), and the check runs only when it
// can. a plain early fault would move the fault before the side effects of the
// iterations that come first; the flag keeps the check where it was. emits
// the load of the flag and the jump over the check; returns the hole to patch
// past it, or -1 when the check cannot be hoisted.
int hoist_guard(int ix, int n, int arr) {
	int k = lsp, j; word r;
	if (ix < 0 || n <= 0) return 0 - 1;
	while (k > loopbase) {
		k--;
		r = linfo(k);
		if (!r || r[40] != ix) continue;
		if (!r[52]) return 0 - 1;
		if (arr >= 0 && (ldirty(r, lname[arr]) || !lclean(arr) || r[55])) return 0 - 1;
		j = 0;
		while (j < r[43] && r[44 + j] != n) j++;
		if (j == r[43]) {
			if (j >= 4) return 0 - 1;
			r[44 + j] = n; r[48 + j] = fslots; fslots++; r[43]++;
		}
		laddr(r[48 + j]); op(O_LD);
		j = hole(); op(O_JZ);
		return j;
	}
	return 0 - 1;
}
// the loop entry of a loop with hoisted checks: each flag is 1 when ix < 0 or
// bound > n, then on to the test at c0
int hoist_stub(word r, int c0) {
	int k = 0;
	setlit(r[42], here);
	while (k < r[43]) {
		vaddr(r[40]); op(O_LD); lit(r[44 + k]); vaddr(r[41]); op(O_LD); op(O_SUB); op(17);
		lit(0); op(O_LT);
		laddr(r[48 + k]); op(O_ST);
		k++;
	}
	jmp(c0);
	return 0;
}
// i < n for a pointer local arr to a block of n words: a loop test against a
// constant of at most n, in a loop whose body leaves arr alone
int proven_p(int ix, int n, int arr) {
	int k = lsp, w; word r;
	while (k > loopbase) {
		k--;
		w = lpfact[k];
		if (w >= 0 && p_iv(w) == ix && p_bd(w) == -1 && 0 - p_ar(w) - 2 <= n) {
			r = linfo(k);
			return r && !ldirty(r, lname[arr]) && lclean(arr) && !r[55];
		}
	}
	return 0;
}
// the allocation facts of the function's locals, kept past the loop top that forgets them
word lafact_save() {
	word b; int i = lbase;
	if (dry || nloc <= lbase) return 0;
	b = chk_resize(0, 0, nloc - lbase + 2); b[0] = lbase; b[1] = nloc;
	while (i < nloc) { b[2 + i - lbase] = lafact[i]; i++; }
	return b;
}
// after a loop that frees nothing: the locals its body left alone get back the
// allocation facts the loop forgot
int lafact_keep(word r, word b) {
	int i;
	if (!b || dry || r[0] || r[55]) return 0;
	i = b[0];
	while (i < b[1] && i < nloc) { if (b[2 + i - b[0]] && !lafact[i] && !ldirty(r, lname[i]) && lclean(i)) lafact[i] = b[2 + i - b[0]]; i++; }
	return 0;
}
// the allocation fact of the pointer local bl at the entry of the innermost
// loop over ix, or 0
word entry_fact(int ix, int bl) {
	int k = lsp; word r, b;
	if (ix < 0 || bl < 0) return 0;
	while (k > loopbase) {
		k--;
		r = linfo(k);
		if (!r || r[40] != ix) continue;
		b = r[56];
		if (!b || bl < b[0] || bl >= b[1]) return 0;
		return b[2 + bl - b[0]];
	}
	return 0;
}
// the number of elements behind a pointer local: the requested size of the
// block it was set from, when the analyzer knows it (never a rounded block
// size), for one-word elements; -1 when unknown
int ptr_elems(word f, word et, int bl) {
	word base;
	if (bl < 0 || !f || f[1] == 2 || f[0] < 0 || tbytes(et) || tsz(et) != 1) return 0 - 1;
	if (f[6]) { base = af_base(f); if (base[1] == 0 || base[10] < 0) return 0 - 1; if (f[14] && f[13]) return 0 - 1; }	// as af_inrange: a live allocation, from its start
	return f[0];
}

// ---- --explain-checks ----

// zy --explain-checks [file] < source compiles the unit without running it and
// prints, as json lines, every bounds check the compiler kept, from the same
// decisions that drop the others. the first line is {"version":1}; the format
// is in docs/SPEC.md. the reason codes:
const int XC_NOT_LOOP = 1, XC_NOT_INVARIANT = 2, XC_NOT_LEN = 3, XC_SIZE = 4, XC_PACKED = 5, XC_HOISTED = 6, XC_MAYFREE = 7;
// why a check of index ix (a local, or -1) into the array local arr stays
int xc_reason(int ix, int arr) {
	int k = lsp; word r;
	if (ix < 0) return XC_NOT_LOOP;
	while (k > loopbase) {
		k--;
		r = linfo(k);
		if (!r || r[40] != ix) continue;
		if (!r[53]) return XC_NOT_INVARIANT;
		if (arr >= 0 && (ldirty(r, lname[arr]) || !lclean(arr))) return XC_NOT_INVARIANT;
		if (arr >= 0 && r[55]) return XC_MAYFREE;
		return XC_NOT_LEN;
	}
	return XC_NOT_LOOP;
}
// the record of one kept check: kind 0 index, 1 pointer; the place of its [
// and, as the end, the token just read (its ]). src/lib/explain.zc writes it.
int xc_note(int kind, int why, int place) {
	int o1, o2, d = 0, k = loopbase, f;
	if (!xc_on || dry || cmode || incdepth > 0 || !xc_src || chbase != xc_src || !xc_hook) return 0;
	o1 = ((place >> 40) & 0x1FFFFF) - 1; o2 = tpend;
	if (o1 < 0 || o2 < o1) return 0;
	while (k < lsp) { if (R_LOOP[k * 8] != 0 - 1) d++; k++; }
	f = xc_hook; f(xc_src, kind, why, place & 0xFFFFFF, o1, tpline, o2, d, xc_fn, xc_file);
	return 0;
}
// is argument 1 --explain-checks? the file name for the records is argument 2.
// then src/lib/explain.zc is compiled, and its note becomes the hook.
int xc_init() {
	int n = rt.syscall(rt.SYS_ARGC, 0, 0, 0), k, s, f; word b;
	if (n < 2) return 0;
	b = chk_resize(0, 0, 32);
	if (rt.syscall(rt.SYS_ARG, 1, b, 31) < 0 || !rt.eq_w(b, "--explain-checks")) return 0;
	xc_on = 1;
	if (n > 2) { k = rt.syscall(rt.SYS_ARG, 2, 0, 0); if (k >= 0) { b = chk_resize(0, 0, k + 1); rt.syscall(rt.SYS_ARG, 2, b, k + 1); xc_file = b; } }
	inc_compile(bstr_text(explain_source()), "tinyvm:explain.zc", 0);
	s = lookup(intern("explain.note")); if (s >= 0) xc_hook = sval[s];
	s = lookup(intern("explain.version")); if (s >= 0) { f = sval[s]; f(); }
	return 0;
}
// is the constant index xcval known to be inside the allocation f? the same
// facts af_index warns from, so a possible failure is never called definite.
int af_inrange(word f) {
	int lower = 0; word base;
	if (!f || !xconst || f[1] == 2 || f[0] < 0) return 0;
	if (f[6]) { base = af_base(f); if (base[1] == 0 || base[10] < 0) return 0; if (f[14]) lower = f[13]; }
	return xcval >= lower && xcval < f[0];
}
// follow child links up to the local that really owns the object
int lroot(int i) {
	while (lstate[i] == S_CHILD) i = lowner[i];
	return i;
}
// lend a local owner to global s for the rest of the current block.
int lend_add(int s, int i) {
	if (nlend * 3 + 3 > lendcap) { if (!lendcap) lendcap = 48; else lendcap = lendcap * 2; lendrec = chk_resize(lendrec, nlend * 3, lendcap); }
	lendrec[nlend * 3] = s; lendrec[nlend * 3 + 1] = i; lendrec[nlend * 3 + 2] = fdepth; nlend++;
	return 0;
}
// remove entry k, keeping the others in order.
int lend_remove(int k) {
	if (k + 1 < nlend) rt.copy_w(lendrec + k * 3, lendrec + k * 3 + 3, (nlend - k - 1) * 3);
	nlend--;
	return 0;
}
// an assignment to global s in the block that lent it ends the lend.
int lend_clear(int s) {
	int k = nlend;
	while (k > 0) { k--; if (lendrec[k * 3] == s && lendrec[k * 3 + 2] == fdepth && lendrec[k * 3 + 1] >= lbase) lend_remove(k); }
	return 0;
}
// report local i still lent to the global of entry k.
int lend_err(int k, char* msg) {
	int i = lendrec[k * 3 + 1];
	if (!fchk || !live || panic || dry) return 0;
	errat(); rt.put_s(lname[i]); rt.put_s(": is lent to global "); rt.put_s(sname[lendrec[k * 3]]); rt.put_s(msg); errend();
	return 0;
}
// local i is about to be given away or released: no global may still borrow it.
int lend_check(int i) {
	int k = 0;
	while (k < nlend) {
		if (lendrec[k * 3 + 1] == i && i >= lbase) { lend_err(k, "; assign the global again before giving the local away"); lend_remove(k); }
		else k++;
	}
	return 0;
}
// leaving every block at depth dep or deeper: a lend made there must have ended.
int lend_exit(int dep) {
	int k = 0;
	while (k < nlend) {
		if (lendrec[k * 3 + 2] >= dep && lendrec[k * 3 + 1] >= lbase) lend_err(k, "; assign the global again before the block that lent it ends");
		k++;
	}
	return 0;
}
// forget the lends made at depth dep or deeper, or by locals from index from onward.
int lend_drop(int dep, int from) {
	int k = 0;
	while (k < nlend) {
		if ((lendrec[k * 3 + 2] >= dep && lendrec[k * 3 + 1] >= lbase) || lendrec[k * 3 + 1] >= from) lend_remove(k);
		else k++;
	}
	return 0;
}
// retire existing aliases together with their owner. dead aliases do not keep later loop snapshots live.
int end_owner(int i) {
 int j = lbase; word info = talloc(3);
 lend_check(i);
 info[0] = lname[i]; info[1] = lpos[i]; info[2] = tpack();
 local_ended[i] = info[2]; local_end_info[i] = info; lstate[i] = S_DEAD;
 while (j < nloc) {
  if (j != i && isalias(j) && lroot(j) == i) { local_ended[j] = info[2]; local_end_info[j] = info; lstate[j] = S_DEAD; }
  j++;
 }
 return 0;
}
// true when a local has an ownership state the analyzer follows.
word tracked(int i) { return lstate[i] != S_PLAIN; }
// a child link with nothing owned: a pointer computed from some other variable
word isalias(int i) { return lstate[i] == S_CHILD && !lown[i]; }
// record the last-use line and saturating reference count for diagnostics.
int luse(int i) {
	lused[i] = tline;
	if ((ltag[i] >> 56) < 100) ltag[i] = ltag[i] + LCNT1;
	return 0;
}
// touch records a use of a tracked local and rejects dead objects. a d object
// read in an inner block moves there, where the block owns it as m.
int touch(int i) {
	int r;
	luse(i);
	ltag[i] = ltag[i] | LREAD;
	if (!fchk) return 0;
	r = lroot(i);
	luse(r);
	if (lstate[r] == S_DEAD) { cerrn(i, "used after it was given away"); return 0; }
	// a d object that shows up in a deeper block is given to that block
	if (lstate[r] == S_D && lhome[r] < fdepth) { lhome[r] = fdepth; lstate[r] = S_M; lown[r] = 1; }
	return 0;
}
// an expression of class c used as a plain value (a lend, an operand). a new
// object can't be used that way, since nothing would own it.
int plainuse(int c) {
	if (c == C_FRESH) cerr("a new object can't be used as a plain value; bind it to a name first");
	if (c >= C_VAR) touch(c - C_VAR);
	return C_PLAIN;
}
// the size class of an n word object, for a constant-size new
int szclass(int n) {
	int k = 3;
	while (rt.pow2[k] < n + rt.HDR) k++;
	return k;
}
// freeing an owned local. one that holds a typed object with no pointer
// fields goes back through recycle_leaf, which knows its class
int freevar(int i) {
 if (local_captured && local_captured[i]) { lit(0); laddr(lslot[i]); op(O_ST); return 0; }
	vaddr(i); op(O_LD);
	if (lleaf[i] && !o3on && !dry && lookup(s_recycle_leaf) >= 0) {
		lit(lleaf[i]);
		lit(szclass(lnsz[i]));
		callname(s_recycle_leaf);
	}
	else callname(s_recycle); op(O_DROP); lit(0); laddr(lslot[i]); op(O_ST); return 0;
}
// leaving every block deeper than or equal to dep: free what is owned, and
// complain about what should have left already. final means the block really
// ends here rather than an early exit.
int exit_vars(int dep, int final) {
	int i = nloc, st;
	if (!fchk || !live) return 0;
	lend_exit(dep);
	while (i > lbase) {
		i--;
		if (lhome[i] < dep) continue;
		st = lstate[i];
		if (st == S_M) {
			if (!local_captured || !local_captured[i]) ev_put(i, EV_FREE, -1); freevar(i);
		} else if (st == S_U) {
			cerrn(i, "u object must leave this block (block value, assignment to the enclosing block, or return)");
		}
		else if (st == S_D) cerrn(i, "d object was never given away");
	}
	return 0;
}
// an m object has to be used somewhere in the block that owns it, on any path
// block ends.
int unused_check(int from) {
	while (from < nloc) {
		if (fchk && lown[from] && !lused[from] && !(lrskind[from] == RS_PARAM && rt.eq_w(lname[from], "_"))) serrn(lname[from], "owned object is never used");
		from++;
	}
	return 0;
}
// what a block's own variables show once it ends (check mode only)
int hint_name(int i, char* msg, int kind) {
	if (!hint_begin(lpos[i], kind)) return 0;
	rt.put_s(lname[i]); rt.put_s(msg);
	dg_close();
	return 0;
}
// report the locals declared from token from onward that were never used.
int local_hints(int from) {
	int i = from, f;
	if (!cmode || dry || panic || chkabort || stubgen) return 0;
	while (i < nloc) {
		f = ltag[i];
		if (lrskind[i] == RS_PARAM && lname[i] != s_this && !rt.eq_w(lname[i], "_") && !(f & LREAD)) {
			if (hint_begin(lpos[i], HINT_SMALL)) {
				rt.put_s("unused parameter `"); rt.put_s(lname[i]); rt.put_s("`"); dg_close();
			}
		} else if ((f & LDECL) && !larr[i] && !rt.eq_w(lname[i], "_")) {	// _ discards its value
			if (!(f & LREAD)) hint_name(i, " is never read", HINT_SMALL);
			else if ((f & LCONST) && !(f & LASG) && !(ltype[i] && treadonly(ltype[i]))) hint_name(i, " is never reassigned; make it a const", HINT_ALL);
			else if (fchk && lstate[i] == S_M && lown[i] && lnsz[i] > 0 && lnsz[i] <= 64) hint_name(i, " never leaves this function; a stack buffer (let name[n]) avoids the heap", HINT_SMALL);
			else if (fchk && lstate[i] == S_M && lown[i] && lused[i] && tline - lused[i] >= 4) hint_name(i, " is last used several lines above the end of its block; close the block sooner so it is freed sooner", HINT_ALL);
		}
		i++;
	}
	return 0;
}
// block_close runs the analyzer's end-of-block work in order: hints for the
// block's variables, o3 registers go back to the pool, an m object that was
// never used is an error, exit_vars frees what is owned and complains about
// what should have left, aliases whose owner dies are marked dead, then the
// block's locals are dropped. unused_check comes first because an unused m
// object is an error, not a free.
int block_close(int save) {
	int i = save, k;
	defer_run(fdepth, 1);	// deferred statements of this block, before its variables go
	af_close(save);
	local_hints(save);
	if (o3on) {
		while (i < nloc) {
			k = (ltag[i] >> 8) & 7;
			if ((ltag[i] & 16) && k && no3free < 8) {
				if (getflt(i)) k = 0 - k;
				o3free[no3free] = k;
				no3free++;
			}
			i++;
		}
	}
	i = lbase;
	unused_check(save);
	exit_vars(fdepth, 1);
	lend_drop(fdepth, save);
	alias_end(fdepth, save);
	while (i < save) { if (lhome[i] >= fdepth) { lstate[i] = S_DEAD; lhome[i] = fdepth - 1; } i++; }
	local_drop(save);
	fdrop(save);
	td_end(fdepth);
	return 0;
}

// an alias in an outer block whose owner is about to disappear dies with it
int alias_end(int dep, int save) {
	int i, r;
	if (!fchk) return 0;
	i = lbase;
	while (i < save) {
		if (isalias(i)) {
			r = lroot(i);
			if (r >= save || lhome[r] >= dep || lstate[r] == S_DEAD) lstate[i] = S_DEAD;
		}
		i++;
	}
	return 0;
}
// snapshots: [lbase] [nloc] then state, owner, home per local
// save the states of all current locals; returns the snapshot offset
int snap_push() {
	int b = snaptop, i = lbase; word p;
	af_forget();
	reserve_R_SNAP(b + 2 + 3 * (nloc - lbase));
	p = R_SNAP + b;
	p[0] = lbase; p[1] = nloc;
	p = p + 2;
	while (i < nloc) { p[0] = lstate[i]; p[1] = lowner[i]; p[2] = lhome[i]; p = p + 3; i++; }
	snaptop = p - R_SNAP;
	return b;
}
// drop the snapshot at base b.
int snap_pop(int b) { snaptop = b; return 0; }
// restore the local states saved in snapshot b.
int snap_restore(int b) {
	word p = R_SNAP + b; int i = p[0], e = p[1];
	af_forget();
	if (e > nloc) e = nloc;
	p = p + 2;
	while (i < e) { lstate[i] = p[0]; lowner[i] = p[1]; lhome[i] = p[2]; p = p + 3; i++; }
	return 0;
}
// true for a plain or dead local state, which merge to dead.
int empty(int s) { return s == S_PLAIN || s == S_DEAD; }
// compare the current states with a snapshot: -1 if they agree, else the
// first local that differs. plain and dead agree and merge to dead.
int snap_cmp(int b) {
	word p = R_SNAP + b; int i = p[0], e = p[1], s;
	if (e > nloc) e = nloc;
	p = p + 2;
	while (i < e) {
		s = lstate[i];
		if (empty(s) && empty(p[0])) { if (p[0] == S_DEAD) lstate[i] = S_DEAD; }
		else if (s != p[0] || lhome[i] != p[2] || (s == S_CHILD && lowner[i] != p[1])) return i;
		p = p + 3; i++;
	}
	return -1;
}
// the state names used in join and loop messages
int statename(int s) {
	if (s == S_PLAIN) return "empty";
	if (s == S_M) return "m";
	if (s == S_U) return "u";
	if (s == S_D) return "d";
	if (s == S_DEAD) return "given away";
	if (s == S_CHILD) return "owned by a container";
	return "borrowed";
}
// report that local i ends two paths in different states
int merge_err(int i, int sa, int what) {
	if (!fchk || panic || dry) return 0;
	errat(); rt.put_s(lname[i]); rt.put_s(": "); rt.put_s(what);
	rt.put_s(" (one path leaves it ");
	rt.put_s(statename(sa));
	rt.put_s(", another ");
	rt.put_s(statename(lstate[i]));
	rt.put_s(")");
	errend();
	return 0;
}

// ---- snapshots and comparing paths ----

// to analyze an if, the compiler snapshots the locals' states before the
// branch, compiles the then path, restores the snapshot for the else path, and
// then compares or merges the two. a snapshot is [lbase, nloc] followed by
// state, owner and home for each local; the stack of them is at R_SNAP.
// ---- joins ----

// where control flow comes back together (after an if, a loop, a switch or
// ?:) every variable has to agree across the paths that reach the join. one
// exception: a variable that became d, or was given away, on some path is dead
// after the join, and the paths where it's still alive free it on the way in
// (fixups). u objects and borrows don't get this treatment: a u object still
// has to leave, and a borrow never changes.

int extop; word[JOIN_PATHS] jps_initial; word jps = jps_initial; int jpscap = JOIN_PATHS, njps;			// the paths being joined: [lbase, nloc, triples]
// accessors on a path record p (a snapshot or an exit record): the state,
// owner and home of local i on that path. locals declared after the snapshot
// read as plain.
word jst(word p, int i) {
	if (i >= p[1]) return S_PLAIN;
	return p[2 + 3 * (i - p[0])];
}
// the owner recorded in a jump's state for local i.
word jow(word p, int i) { return p[3 + 3 * (i - p[0])]; }
// the jump's marker for local i, in the same record as jow.
word jhm(word p, int i) { return p[4 + 3 * (i - p[0])]; }
// the states at a break, with the jump to patch: [site] then a snapshot
word exit_rec(int site) {
	word p; int i = lbase; word q;
	reserve_R_EXIT(extop + 3 + 3 * (nloc - lbase)); p = R_EXIT + extop;
	p[0] = site; p[1] = lbase; p[2] = nloc;
	q = p + 3;
	while (i < nloc) { q[0] = lstate[i]; q[1] = lowner[i]; q[2] = lhome[i]; q = q + 3; i++; }
	extop = q - R_EXIT;
	return p;
}
// jps is the set of paths about to be joined. jadd adds one, jsame compares
// what two paths say about a local, and join folds them all into the current
// states (reporting any local that disagrees)
int jadd(int p) {
	if (njps >= jpscap) { jps = chk_resize(jps, njps, jpscap * 2); jpscap = jpscap * 2; }
	jps[njps] = p;
	njps++;
	return 0;
}
// true when the states of two jumps agree for local i.
word jsame(int p, int q, int i) {
	int s = jst(p, i), t = jst(q, i);
	if (empty(s) && empty(t)) return 1;
	return s == t && jhm(p, i) == jhm(q, i) && (s != S_CHILD || jow(p, i) == jow(q, i));
}
// join the paths in jps over the locals [lbase, n0) into the current states
int join(int n0, int what) {
	int i = lbase, j, p, s, s0, dead, okdead, bad;
	af_forget();
	if (!njps) return 0;
	while (i < n0) {
		p = jps[0]; s0 = jst(p, i);
		dead = 0; okdead = 1; bad = -1;
		j = 0;
		while (j < njps) {
			s = jst(jps[j], i);
			if (s == S_DEAD || s == S_D) dead = 1;
			if (s == S_U || s == S_BORROW) okdead = 0;
			if (!jsame(p, jps[j], i)) bad = j;
			j++;
		}
		lstate[i] = s0; lowner[i] = jow(p, i); lhome[i] = jhm(p, i);
		if (bad < 0) {
			if (empty(s0)) {
				j = 0;
				while (j < njps) {
					if (jst(jps[j], i) == S_DEAD) lstate[i] = S_DEAD;
					j++;
				}
			}
		} else if (dead && okdead) lstate[i] = S_DEAD;
		else if (fchk && !panic && !dry) {
			errat(); rt.put_s(lname[i]); rt.put_s(": "); rt.put_s(what);
			rt.put_s(" (one path leaves it ");
			rt.put_s(statename(s0));
			rt.put_s(", another ");
			rt.put_s(statename(jst(jps[bad], i)));
			rt.put_s(")");
			errend();
		}
		i++;
	}
	return 0;
}
// on path p: count (and with doit, emit) the frees for what the join made dead but p still owns
int fixups(int p, int n0, int doit) {
	int i = lbase, n = 0, s;
	if (!fchk) return 0;
	while (i < n0) {
		s = jst(p, i);
		if (lstate[i] == S_DEAD && (s == S_M || s == S_D)) { n++; if (doit) freevar(i); }
		i++;
	}
	return n;
}
// a jump back to the top of a loop: whatever the loop owns has to be as it was
int backedge(int s0) {
	word p = R_SNAP + s0; int i = p[0], e = p[1], s;
	if (!fchk || !live) return 0;
	if (e > nloc) e = nloc;
	while (i < e) {
		s = lstate[i];
		if (empty(s) && empty(jst(p, i))) { if (jst(p, i) == S_DEAD) lstate[i] = S_DEAD; }
		else if (s != jst(p, i) || lhome[i] != jhm(p, i) || (s == S_CHILD && lowner[i] != jow(p, i))) {
			if (s == S_DEAD || s == S_D) {
				cerrn(i, "is given away inside a loop that comes back around to it; give it away on a path that leaves the loop");
			}
			else if (!panic && !dry) {
				errat();
				rt.put_s(lname[i]);
				rt.put_s(": changes state inside a loop; each pass has to leave it as it found it (it went from ");
				rt.put_s(statename(jst(p, i))); rt.put_s(" to "); rt.put_s(statename(s)); rt.put_s(")"); errend();
			}
		}
		i++;
	}
	return 0;
}
// joins two paths that end at the same point, like the branches of if/else:
// path a jumped (through the hole at ja) and path b falls through to here
// (the then path's snapshot is sa; livea / livebv say whether each path can
// reach the join at all, since a path that returned is not part of it)
int join2(int sa, int livea, int ja, int livebv, int n0, int what) {
	int sb, nt, cj;
	sb = snap_push();
	njps = 0; if (livea) jadd(R_SNAP + sa); if (livebv) jadd(R_SNAP + sb);
	join(n0, what);
	if (livebv) fixups(R_SNAP + sb, n0, 1);
	nt = 0; if (livea) nt = fixups(R_SNAP + sa, n0, 0);
	if (nt) { cj = hole(); op(O_JMP); setlit(ja, here); fixups(R_SNAP + sa, n0, 1); setlit(cj, here); }
	else setlit(ja, here);
	live = livea || livebv;
	return 0;
}

// the rules below are the heart of the analyzer. each is a function the parser
// calls at one kind of place where a value moves: recast (u*x), argument
// passing, assignment, return, block values, and discarding. the argument
// c they take is an expression class: C_PLAIN (an ordinary word), C_FRESH (a
// new object nobody owns yet) or C_VAR + n (a bare local, number n), which is
// how the analyzer knows the thing being moved is a variable it tracks.
// ---- analyzer rules for the places values flow ----

// recast: x as u / x as d / x as m
int recast(int c, int t) {
	int i, st;
	if (c == C_FRESH && t == S_M) return C_PLAIN;	// m*f(): the unnamed result is let go on purpose, so it can be discarded
	if (!fchk) return c;
	if (c < C_VAR) { cerr("only a named owned object can be recast; this expression has no owner"); return c; }
	i = c - C_VAR;
	st = lstate[i];
	luse(i);
	if (st == S_CHILD)  cerrn(i, "belongs to a container; recast the container instead");
	else if (st == S_BORROW) cerrn(i, "is borrowed and can't be recast");
	else if (st == S_PLAIN) cerrn(i, "isn't an owned object");
	else if (st == S_DEAD) cerrn(i, "used after it was given away");
	else if (t == S_M && st != S_M) cerrn(i, "can't be recast back to m");
	else lstate[i] = t;
	return c;
}
// an argument for a parameter tagged t (0 plain, 1 m, 2 d)
int argcheck(int c, int t) {
	int i, st;
	if (fchk && t == 2 && xaf && xaf[2] == 5) { cerr("a borrowed temporary cannot transfer ownership"); return 0; }
	if (fchk && t == 2 && xaf && xaf[2] == 4 && (isptr(xty) || isagg(xty))) { cerr("an array literal cannot transfer ownership to a d parameter"); return 0; }
	if (!fchk) return 0;
 if (t == 2 && c < C_VAR && c != C_FRESH && xbor >= 0 && tracked(lroot(xbor))) { cerr("a borrowed projection cannot transfer ownership; transfer its owner"); return 0; }
	if (c == C_FRESH) {
		if (t != 2) {
			cerr("a new object can only go straight to a d parameter; bind it to a name first");
		} else {
			xgive = 1;
		}
		return 0;
	}
	if (c < C_VAR || !tracked(c - C_VAR)) return 0;
	i = c - C_VAR;
	if (t == 2 && isalias(i)) { cerr("a borrowed projection cannot transfer ownership; transfer its owner"); return 0; }
	st = lstate[i];
	if (lstate[lroot(i)] == S_DEAD) { cerrn(i, "used after it was given away"); return 0; }
	if (t <= 1) {	// untagged parameters are m: a lend
		if (st == S_D) {
			cerrn(i, "is d; pass it to a d parameter (lending it would lose it)");
			return 0;
		}
		touch(i);
		return 0;
	}
	if (st == S_D || ((st == S_M || st == S_U) && lown[i])) { end_owner(i); luse(i); xgive = 1; ev_put(i, EV_DOWN, -1); return 0; }
	if (st == S_M) cerrn(i, "is m; write d*x to give it away");
	else if (st == S_U) cerrn(i, "is u; write d*x to give it away instead of returning it");
	else if (st == S_CHILD) cerrn(i, "belongs to a container and can't be given away alone");
	else cerrn(i, "is borrowed and can't be given away");
	return 0;
}
// child, owner on the stack (owner on top). write owner into the child's
// header and leave the child. a shared child keeps the owner it has. a null
// child's address is out of range and the store does not land.
// o3 code can't call own(), so this is own() inlined: skip the store when the
// child is shared (flag bit 8) and otherwise write the owner into the child's
// header word p[-2]
int o3own() {
	int sk, st;
	lit(1); op(O_PICK); lit(4); op(O_SUB); op(O_LD); lit(8); op(16);
	sk = hole(); op(O_JZ);
	op(O_DROP);
	st = hole(); op(O_JMP);
	setlit(sk, here);
	lit(1); op(O_PICK); lit(2); op(O_SUB); op(O_SWAP); op(O_SWAP); op(O_ST);
	setlit(st, here);
	return 0;
}
// storing a child into container local p: emit the call that records the
// owner in the child's header. a growable array's elements live in its items
// object, so that is the owner there.
int emitown(int p) {
	vaddr(p); op(O_LD);
	// a T[?]'s elements live in its items object
	if (ltype[p][0] == TY_DYN) {
		lit(2);
		op(O_ADD);
		op(O_LD);
	}
	if (o3on && !mdbg) o3own();
	else callname(s_own);
	if (o3on && hasptr(xty) && !xstamp) { lit(xty); callname(s_fatten); }
	return 0;
}
// a store of class rc into an lvalue of kind k (local or container index i)
int assigncheck(int k, int i, int rc) {
	int st, j, r, js, bor, origin = effect_origin(rc);
 if (k == LV_LOCAL && local_origin) { local_origin[i] = origin; local_origin_mask[i] = local_origin_mask[i] | effect_mask(rc); }
 if (k == LV_ELEM) { effect_note_mask(effect_mask(C_VAR + i), EF_WRITE); }
 if (k != LV_LOCAL && isptr(xty)) effect_note_mask(effect_mask(rc), EF_RETAIN);
 else if (k != LV_LOCAL && xty == tword) effect_note_mask(effect_mask(rc), EF_UNKNOWN);
 if (fchk && xaf && xaf[2] == 5 && (isptr(xty) || xty == tword)) cerr("a borrowed temporary cannot escape its expression into a variable or container");
	bor = xbor; xbor = -1;
	if (!fchk) return C_PLAIN;
	if (k != LV_LOCAL && xaf && xaf[2] == 4 && (isptr(xty) || isagg(xty))) { cerr("an array literal cannot escape into a global or container"); return C_PLAIN; }
	j = -1;
	if (rc >= C_VAR && tracked(rc - C_VAR)) j = rc - C_VAR;
	if (j >= 0 && lstate[lroot(j)] == S_DEAD) {
		cerrn(j, "used after it was given away");
		return C_PLAIN;
	}
	if (k == LV_LOCAL) {
		st = lstate[i];
		if (isalias(i)) st = S_PLAIN;	// a borrow isn't an owner; overwriting it drops the alias
		if (j < 0 && rc != C_FRESH) {
			if (!empty(st)) cerrn(i, "still owns an object; overwriting it would leak it");
			else if (bor >= 0 && bor != i && (tracked(bor) || larr[bor])) { lstate[i] = S_CHILD; lowner[i] = bor; lown[i] = 0; }
			else lstate[i] = S_PLAIN;
			return C_PLAIN;
		}
		if (!empty(st)) {
			cerrn(i, "still owns an object; overwriting it would leak it");
			return C_PLAIN;
		}
		if (rc == C_FRESH) {
			lstate[i] = S_M;
			lused[i] = 0;
			lown[i] = 1;
			local_ended[i] = 0; local_end_info[i] = 0;
			if (ltag[i] & 15) lstate[i] = ltag[i] & 15;
			return C_PLAIN;
		}
		js = lstate[j];
  if (js == S_BORROW || isalias(j)) { lstate[i] = S_CHILD; lowner[i] = lroot(j); lown[i] = 0; touch(j); return C_PLAIN; }
		// replace a released owner by moving a same-scope owner into its empty slot.
		// fresh declarations still cannot copy owners; the source and its aliases expire.
		if (st == S_DEAD && lown[i] && js == S_M && lown[j] && lhome[j] >= lhome[i]
			&& !local_captured[i] && !local_captured[j]) {
			lstate[i] = S_M; lused[i] = 0; lown[i] = 1;
			lnsz[i] = lnsz[j]; lleaf[i] = lleaf[j];
			local_ended[i] = 0; local_end_info[i] = 0;
			end_owner(j); luse(j); ev_put(j, EV_MOVE, i);
			if (ltag[i] & 15) lstate[i] = ltag[i] & 15;
			return C_PLAIN;
		}
		if (js == S_U && lhome[i] == lhome[j] - 1) {	// handing a u object up one block
			lstate[i] = S_M;
			lused[i] = 0;
			lown[i] = 1;
			end_owner(j);
			luse(j); ev_put(j, EV_UP, i);
			if (ltag[i] & 15) lstate[i] = ltag[i] & 15;
			return C_PLAIN;
		}
		if (js == S_U) {
			cerrn(j, "is u; it can only be handed to a variable of the enclosing block, or returned");
		}
		else cerrn(j, "is an owned object and can't be copied into another variable");
		return C_PLAIN;
	}
	if (k == LV_ELEM) {
		r = lroot(i);
		st = lstate[r];
		touch(i);
		if (rc == C_FRESH) { emitown(i); return C_PLAIN; }
		if (j < 0) return C_PLAIN;
		js = lstate[j];
		if (js == S_CHILD) cerrn(j, "already belongs to a container");
		else if (js == S_BORROW) cerrn(j, "is borrowed and can't be stored");
		else if (st == S_BORROW) {
			if (js == S_U) {
				cerrn(j, "is u; it has to leave through the block above, not into a borrowed object");
			}
			else { end_owner(j); luse(j); ev_put(j, EV_STORE, i); emitown(i); }	// storing it gives it away
		} else if (js != st) cerrn(j, "its tag doesn't match its container's (both have to be m, u or d)");
		else if (lhome[j] < lhome[r]) cerrn(j, "lives in an outer block than the container it's stored into");
		else { lstate[j] = S_CHILD; lowner[j] = i; luse(j); ev_put(j, EV_STORE, i); emitown(i); }
		return C_PLAIN;
	}
	// a global, or memory the analyzer doesn't track: the collector takes it
	// an owner (d, u, or an m local that owns its object) is transferred as if by u*x
	if (k == LV_GLOBAL) lend_clear(i);
	if (j >= 0 && k == LV_GLOBAL && xlend == j && lstate[j] == S_M && lown[j]) { xlend = -1; touch(j); lend_add(i, j); return C_PLAIN; }
	xlend = -1;
	if (j >= 0) {
		if (lstate[j] == S_D || lstate[j] == S_U || (lstate[j] == S_M && lown[j])) { ev_put(j, EV_GLOBAL, -1); end_owner(j); luse(j); }
		else cerrn(j, "is not an owner, so it can't be stored in a global or in untracked memory (the collector takes it over)");
	}
	return C_PLAIN;
}
// return c: an owned object (d, or u after u*x) goes up with the return, and the
// function's return is owned: declared with .u, or inferred from this return when
// the function has no .u (its callers compiled after this point see it). an m
// object is lent, not given, so returning it is an error, and so is a plain word
// from an owned function that was called before its body.
int retcheck(int c) {
 int i;
 if (isptr(xty) || xty == tword) {
  effect_note_mask(effect_mask(c), EF_ALIAS);
  if (c >= C_VAR && lrskind[c - C_VAR] == RS_PARAM) effect_note(effect_origin(c), EF_IDENTITY);
 }
 if (fchk && xaf && xaf[2] == 5 && (isptr(xty) || xty == tword)) cerr("a borrowed temporary cannot escape its expression through return");
	if (!fchk) return 0;
	if (c < C_VAR && c != C_FRESH && xbor >= 0 && (isptr(xty) || xty == tword)) {
  int root = lroot(xbor);
  if (fret) { cerr("a borrowed projection cannot be returned as an owned result"); return 0; }
  if (lown[root] && (lstate[root] == S_M || lstate[root] == S_U || lstate[root] == S_D)) { cerr("a borrow of a local owner cannot escape through return; return the owner"); return 0; }
 }
 if (c >= C_VAR && isalias(c - C_VAR)) {
  int root = lroot(c - C_VAR);
  if (fret) cerr("a borrowed projection cannot be returned as an owned result");
  else if (lown[root]) cerr("a borrow of a local owner cannot escape through return; return the owner");
  return 0;
 }
 if (c >= C_VAR && lstate[c - C_VAR] == S_BORROW) {
  if (fret) cerr("a borrowed parameter cannot be returned as an owned result");
  return 0;
 }
	if ((isptr(xty) || isagg(xty)) && ((xaf && xaf[2] == 4) || (xbor >= 0 && lafact[xbor] && lafact[xbor][2] == 4))) { cerr("an array literal cannot escape its function through return"); return 0; }
	i = -1;
	if (c >= C_VAR && tracked(c - C_VAR)) i = c - C_VAR;
	if (i >= 0 && lstate[lroot(i)] == S_DEAD) { cerrn(i, "used after it was given away"); return 0; }
	if (i >= 0 && (lstate[i] == S_D || (lstate[i] == S_M && lown[i])) && (fret || finfer)) lstate[i] = S_U;	// returning an owned object (a d object, or a local that owns one) gives it up, as u*x does
	if (!fret && finfer && (c == C_FRESH || (i >= 0 && lstate[i] == S_U))) {
		if (sflag[finsym] & F_EARLY) serrn(sname[finsym], "is called before its body, so its owned return can't be known there; declare the return type with .u");
		ssig[finsym] = ssig[finsym] | 1;	// the return is owned: callers read it from the signature
		sflag[finsym] = sflag[finsym] | F_RETOWN;
  if (stype[finsym]) { word ft = stype[finsym]; stype[finsym] = tfn(ft[4], ft[3], ft + 7, ssig[finsym]); }
		fret = 1; finfer = 0;
	}
	if (fret) {
		if (i >= 0) {
			if (lstate[i] == S_U) { end_owner(i); luse(i); ev_put(i, EV_RETURN, -1); }
			else cerrn(i, "has to be u to be returned");
		}
		return 0;
	}
	if (c == C_FRESH) cerr("returns a new object; give the function a .u return type");
	else if (i >= 0) cerrn(i, "is owned and can't be returned from a function whose return type isn't .u");
	return 0;
}
// the last expression of a block expression
int handup(int c) {
	int i;
	if (!fchk) return C_PLAIN;
	if (c == C_FRESH) return C_FRESH;
	if (c < C_VAR || !tracked(c - C_VAR)) return C_PLAIN;
	i = c - C_VAR;
	if (lstate[i] == S_U && lhome[i] == fdepth) { lstate[i] = S_DEAD; luse(i); ev_put(i, EV_VALUE, -1); return C_FRESH; }
	if (lstate[i] == S_U) cerrn(i, "only a u object of this block can be its value");
	else cerrn(i, "has to be u to be handed up as the block's value");
	return C_PLAIN;
}
// throw away an expression result, which is an error for a fresh object.
int discard(int c) {
	if (c == C_FRESH) cerr("a new object (or a u result) can't be thrown away");
	else if (c >= C_VAR) touch(c - C_VAR);
	xbor = -1;
	return 0;
}

// ---- completion ----

// copy local i (kind: 1 local, 2 parameter, 3 captured from the function around a closure) into the probe,
// unless a nearer local has its name
int probe_add(int i, int kind) {
	int k = 0;
	while (k < probe_n) { if (probe_name[k] == lname[i]) return 0; k++; }
	if (!probe_name || probe_n == probe_cap) {
		if (!probe_cap) probe_cap = 32; else probe_cap = probe_cap * 2;
		probe_name = chk_resize(probe_name, probe_n, probe_cap); probe_kind = chk_resize(probe_kind, probe_n, probe_cap);
		probe_state = chk_resize(probe_state, probe_n, probe_cap); probe_type = chk_resize(probe_type, probe_n, probe_cap); probe_decl = chk_resize(probe_decl, probe_n, probe_cap);
	}
	probe_name[probe_n] = lname[i]; probe_kind[probe_n] = kind;
	probe_state[probe_n] = lstate[lroot(i)] == S_DEAD || af_expired(lafact[i]);
	if (lafact[i] && lafact[i][1] == 2) probe_state[probe_n] = 1;
	probe_type[probe_n] = ltype[i]; probe_decl[probe_n] = lrsoff[i];
	probe_n++;
	return 0;
}
// what is in scope right now: this function's locals, then those of the functions around a closure
int probe_snap() {
	int i = nloc, k = nclo;
	probe_n = 0; probe_has = 1;
	while (i > lbase) {
		i--;
		if (lname[i][0] != '<') { if (lrskind[i] == RS_PARAM) probe_add(i, 2); else probe_add(i, 1); }
	}
	while (k) {
		k--;
		i = clo_hi[k];
		while (i > clo_lo[k]) { i--; if (lname[i][0] != '<') probe_add(i, 3); }
	}
	return 0;
}
// a statement of the document starts here: remember what is in scope, or stop when the place has been passed.
// statements of a method or generic compiled for a call belong to another function and are left alone
int probe_stmt() {
	if (!cmode || dry || ginst || chkabort || incdepth != 0 || ctxsp > nclo) return 0;
	probe_snap();
	if (toff > probe_off) { chkabort = 1; return 0; }
	return 0;
}
// the place asked about is a member name, and t is the type before the dot
int probe_member(word t) {
	probe_mem = t; probe_has = 2; chkabort = 1;
	return 0;
}