analyzer: check borrow returns of forward-called functions at the unit's end; borrows clause for prototypes, definitions, externs and function types, checked against the body

6 files changed, 115 insertions, 9 deletions

diff --git a/src/compiler/analyzer.zc b/src/compiler/analyzer.zc
index 48debee..103f732 100644
--- a/src/compiler/analyzer.zc
+++ b/src/compiler/analyzer.zc
@@ -83,6 +83,51 @@ int effect_specialize(int original, int instance, word requirements, word edges)
 	while (e && e != edges) { if (e[3] == original) e[3] = instance; e = e[0]; }
 	return 0;
 }
+// borrow returns of functions called before their body. such a call's result
+// may turn out to alias an argument's owner, which is only known once the body
+// has been read. the result's local keeps a shadow record (callee, the mask of
+// parameters that got the owner, the owner, the token after the call, so only a call that is the whole right side counts); a
+// use of the local after its owner ended is remembered, and effect_finish
+// reports it when the callee's return aliases one of those parameters.
+word shadow_new(int callee, int mask, int owner) {
+ word e;
+ if (!fchk || !live || dry || owner < 0 || !mask) return 0;
+ e = talloc(4); e[0] = callee; e[1] = mask; e[2] = owner; e[3] = tpack();
+ return e;
+}
+// the local i is assigned: it takes the shadow of a forward call that is its whole right side.
+int shadow_take(int i) {
+ if (!local_shadow) return 0;
+ local_shadow[i] = 0;
+ // the local read just before is the target of this assignment, not a use
+ if (effect_shadows && effect_shadows[10] == i && effect_shadows[11] == lreadpos[i]) effect_shadows = effect_shadows[0];
+ if (xshadow && xshadow[3] == tpack()) local_shadow[i] = xshadow;
+ xshadow = 0; return 0;
+}
+int shadow_use(int i) {
+ word s = local_shadow[i], e; int o = s[2];
+ if (!fchk || !live || lstate[o] != S_DEAD) return 0;
+ local_shadow[i] = 0;
+ e = talloc(12); e[10] = i; e[11] = tpack(); e[0] = effect_shadows; e[1] = s[0]; e[2] = s[1]; e[3] = tpack(); e[4] = curinc; e[5] = effect_floor;
+ e[6] = lname[i]; e[7] = 0; if (local_end_info) e[7] = local_end_info[o]; e[8] = lname[o]; e[9] = local_ended[o];
+ effect_shadows = e; return 0;
+}
+int shadow_finish(int from) {
+ word e = effect_shadows, next; int flags, k;
+ effect_shadows = 0;
+ while (e) {
+  next = e[0];
+  if (e[5] < from) { e[0] = effect_shadows; effect_shadows = e; e = next; continue; }
+  flags = 0; k = 0;
+  while (k < 24) { if ((e[2] >> k) & 1) flags = flags | effect_get(e[1], k); k++; }
+  if ((flags & (EF_ALIAS | EF_IDENTITY)) && !(flags & EF_UNKNOWN) && !dry) {
+   tunpack(e[3]); curinc = e[4]; panic = 0;
+   errat(); ended_message(e[6], e[7], e[8], e[9]); rt.put_s("; "); rt.put_s(sname[e[1]]); rt.put_s(", defined after this call, returns a borrow of its argument"); errend();
+  }
+  e = next;
+ }
+ 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;
@@ -110,6 +155,7 @@ int effect_finish(int from) {
   }
   e = next;
  }
+ shadow_finish(from);
  tunpack(save); curinc = inc; return 0;
 }
 int borrow_begin() { return 0; }
@@ -393,6 +439,7 @@ int newloc(int n) {
  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;
+ if (!local_shadow) local_shadow = chk_resize(0, 0, loccap); local_shadow[i] = 0;
 	lpos[i] = 0;
 	lreadpos[i] = 0;
 	lowner[i] = 0;
@@ -1459,6 +1506,7 @@ int reassign_free(int i, int rc, int bor) {
 // 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) shadow_take(i); else xshadow = 0;
  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);
diff --git a/src/compiler/base.zc b/src/compiler/base.zc
index 32549d4..bfed062 100644
--- a/src/compiler/base.zc
+++ b/src/compiler/base.zc
@@ -254,7 +254,7 @@ int fn_return_type;	// a consistent return type inferred from the function body
 // effects come from the real compiler's uses, stores, returns and call edges; unknown bodies stay conservative.
 const int EF_READ = 1, EF_WRITE = 2, EF_RETAIN = 4, EF_CONSUME = 8, EF_UNKNOWN = 16, EF_ALIAS = 32, EF_IDENTITY = 64;
 word effect_symbols, effect_edges, effect_requirements, effect_current; int effect_floor, effect_argument_base;
-word local_origin, local_origin_mask, local_cell, local_captured, local_ended, local_end_info; word effect_value, argorigin_mask; int capture_enabled; word[1] capture_dummy;
+word local_origin, local_origin_mask, local_cell, local_captured, local_ended, local_end_info, local_shadow, xshadow, effect_shadows; int argowner_mask; word effect_value, argorigin_mask; int capture_enabled; word[1] capture_dummy;
 // drops (docs/design/destructors.md): the code position just past a drop form (a fresh
 // value with a drop still on the stack there), the type `this` gets in the next closure,
 // a local whose drop is set, a mailbox send whose arguments are checked, and o3 block depth.
@@ -758,6 +758,7 @@ int reserve_locals(int need) {
  if (local_captured) local_captured = chk_resize(local_captured, nloc, cap);
  if (local_ended) local_ended = chk_resize(local_ended, nloc, cap);
  if (local_end_info) local_end_info = chk_resize(local_end_info, nloc, cap);
+ if (local_shadow) local_shadow = chk_resize(local_shadow, nloc, cap);
 	lafact = chk_resize(lafact, nloc, cap); laaddr = chk_resize(laaddr, nloc, cap); lprev = chk_resize(lprev, nloc, cap);
 	if (lvkind) { lvkind = chk_resize(lvkind, nloc, cap); lvvalue = chk_resize(lvvalue, nloc, cap); lvescaped = chk_resize(lvescaped, nloc, cap); }
 	o3cache = chk_resize(o3cache, nloc, cap);
diff --git a/src/compiler/builtins.zc b/src/compiler/builtins.zc
index d28d2fd..f40e223 100644
--- a/src/compiler/builtins.zc
+++ b/src/compiler/builtins.zc
@@ -1119,6 +1119,7 @@ int kw_extern() {
 		}
 	}
 	expect(s_rp);
+	int borrowed = borrows_clause(0, np, 1);
 	if (accept(s_eq)) {
 		if (tk != T_STR) { die("expected the c name as a string"); return 0; }
 		cname = tv;
@@ -1194,7 +1195,10 @@ int kw_extern() {
 		ebn10(i);
 		i++;
 	}
-	ebs(") { let b = "); ebn10(a); ebs(";");
+	ebs(")");
+	// the stub keeps the declaration's borrows clause, so calls see it in the signature
+	if (borrowed) { ebs(" borrows "); i = 0; g = 0; while (i < np) { if ((borrowed >> i) & 1) { if (g) ebs(", "); ebs("p"); ebn10(i); g = 1; } i++; } }
+	ebs(" { let b = "); ebn10(a); ebs(";");
 	// the native descriptor borrows an integer address, not ownership of r.
 	// clear that scratch address after the call so it cannot keep the result rooted.
 	if (sret) { ebs(" "); ebs(rn); ebs("* r = rt.new("); ebs(rn); ebs("); b[3] = core.addr_b(r) >> 3;"); }
diff --git a/src/compiler/decl.zc b/src/compiler/decl.zc
index dfcff4f..52d08c7 100644
--- a/src/compiler/decl.zc
+++ b/src/compiler/decl.zc
@@ -282,6 +282,18 @@ int body() {
 // (this is also where a function's signature is packed into ssig and its type
 // into stype, checked against any earlier prototype or prescan result, and
 // where the o3 region for an o3 function is handed to the core)
+// a body against its borrows clause: it may return a borrow only of the parameters the clause names.
+int borrows_check(int s, int np, char** pn, word pty) {
+	int mask = sig_borrows(ssig[s]), i = 0;
+	if (!mask || !fchk || !effect_current || effect_current[0] != 1) return 0;
+	while (i < np && i < 24) {
+		if (!((mask >> i) & 1) && (effect_current[26 + i] & (EF_ALIAS | EF_IDENTITY)) && (isptr(pty[i]) || pty[i] == tword)) {
+			if (!panic && !dry) { errat(); rt.put_s(sname[s]); rt.put_s(": returns a borrow of "); if (pn[i]) rt.put_s(pn[i]); else rt.put_n(i); rt.put_s(", but its borrows clause doesn't name it"); errend(); }
+		}
+		i++;
+	}
+	return 0;
+}
 int fndef(int chk, int rty, int ret, int n) {
 	int s, np = 0, tags = 0, t, sig, i; char*[24] pn; word[24] pt; word[24] pty; int typed = 0, ft, explicit_rty = !!rty, o3f = o3nxt, lo, hi, pk, lt, lend, lfl = tline, redef, amb = 0, nonm = 0;
 	o3nxt = 0;
@@ -348,6 +360,10 @@ int fndef(int chk, int rty, int ret, int n) {
 		amb = amb >> 1; i++;
 	}
 	sig = ret + np + np + tags * 64;
+	lo = borrows_clause(pn, np, 1);
+	// a definition after a prototype keeps the prototype's borrows clause
+	if (!lo && (sflag[s] & F_SIG) && !(sflag[s] & F_PRE)) lo = sig_borrows(ssig[s]);
+	sig = sig + (lo << SIG_BORROWS);
 	if ((sflag[s] & F_SIG) && !(sflag[s] & F_PRE)) {
 		if (ssig[s] != sig) serrn(n, "doesn't match its earlier declaration");
 	}
@@ -408,6 +424,7 @@ int fndef(int chk, int rty, int ret, int n) {
 		i = 0; while (i < np) { t = lbase + i; o3mkcache(t); o3refresh(t); i++; }
 	}
 	body();
+	borrows_check(s, np, pn, pty);
 	if (!explicit_rty && fn_return_type > 0 && fn_return_type != tword) {
 		stype[s] = tfn(fn_return_type, np, pty, ssig[s]);
 		sig_attach(n, fn_return_type, np, pn, pty, 1);
diff --git a/src/compiler/expr.zc b/src/compiler/expr.zc
index d9c91d6..a6cc55c 100644
--- a/src/compiler/expr.zc
+++ b/src/compiler/expr.zc
@@ -63,7 +63,7 @@ int stmtonly() {
 // fat asks for every pointer argument to be fattened first, for o3 code
 // calling code that is not o3.)
 int args(int tags, word ft, int bs, int fat) {
-	int np = 0, c, pt, t, cs = ifcall, freeing = 0, harmless = 0; word first = 0; int origin = -1, anytemp = 0, current, tag, place, parameter_base = effect_argument_base, owner = -1, current_owner, owner_seen = 0, aliases; word origins = 0, current_mask, owner_fact = 0;
+	int np = 0, c, pt, t, cs = ifcall, freeing = 0, harmless = 0; word first = 0; int origin = -1, anytemp = 0, current, tag, place, parameter_base = effect_argument_base, owner = -1, current_owner, owner_seen = 0, aliases; word origins = 0, current_mask, owner_fact = 0; int owner_mask = 0, borrowed = callee_borrows(cs, ft);
 	if (cs >= 0 && cs < ubase) {
 		freeing = sname[cs] == s_free || sname[cs] == s_recycle;
 		harmless = sname[cs] == s_put_s || rt.eq_w(sname[cs], "rt.put_n") || rt.eq_w(sname[cs], "rt.put_c") || rt.eq_w(sname[cs], "len") || rt.eq_w(sname[cs], "cap");
@@ -88,9 +88,11 @@ int args(int tags, word ft, int bs, int fat) {
    if (c >= C_VAR && tracked(c - C_VAR)) current_owner = lroot(c - C_VAR);
    if (tag <= 1 && current_owner >= 0 && tracked(current_owner)) effect_require_mode(cs, np + parameter_base, place, 1);
    aliases = effect_get(cs, np + parameter_base);
+   if (borrowed) { aliases = 0; if (np + parameter_base < 12 && ((borrowed >> (np + parameter_base)) & 1)) aliases = EF_ALIAS; }
    if (aliases & (EF_ALIAS | EF_IDENTITY | EF_UNKNOWN)) {
-    if (!owner_seen) { owner = current_owner; owner_fact = xaf; owner_seen = 1; }
+    if (!owner_seen) { owner = current_owner; owner_fact = xaf; owner_seen = 1; owner_mask = 0; }
     else if (owner != current_owner) { owner = -1; owner_fact = 0; }
+    if (owner >= 0 && owner == current_owner && np + parameter_base < 24) owner_mask = owner_mask | (1 << (np + parameter_base));
    }
    if (fchk && c == C_FRESH && tag != 2) {
     if (!(cs < 0 && tag == 1)) effect_require(cs, np + parameter_base, place); emit_borrow_hold(); c = C_PLAIN; anytemp = 1;
@@ -127,7 +129,7 @@ int args(int tags, word ft, int bs, int fat) {
 		}
 	}
 	expect(s_rp);
-	argfact = first; argorigin = origin; argorigin_mask = origins; argtemporary = anytemp; argowner = owner; argowner_fact = owner_fact; xaf = 0; vf_effect();
+	argfact = first; argorigin = origin; argorigin_mask = origins; argtemporary = anytemp; argowner = owner; argowner_mask = owner_mask; argowner_fact = owner_fact; xaf = 0; vf_effect();
 	return np;
 }
 // memdebug records the source line on the next new, via the runtime global
@@ -487,13 +489,16 @@ int call(int s) {
 	xlenloc = -1; xstamp = 0;
 	if (o3on && (sflag[s] & F_O3) && ft && hasptr(xty)) xstamp = 1;
  borrow_depth--; effect_value = 0;
- if (!ret && (isptr(xty) || xty == tword)) {
+ if (!ret && (isptr(xty) || xty == tword || callee_borrows(original, ft))) {
   effect_value = origins;
-  if (owner >= 0 && (isptr(xty) || (effect_get(original, 0) & EF_IDENTITY))) xbor = owner;
+  if (owner >= 0 && (isptr(xty) || (effect_get(original, 0) & EF_IDENTITY) || callee_borrows(original, ft))) xbor = owner;
   if (owner_fact && (effect_get(original, 0) & EF_IDENTITY)) xaf = owner_fact;
   if (origin >= 0 && owner < 0) { int oi = lbase; while (oi < nloc) { if (lrskind[oi] == RS_PARAM && oi - lbase == origin) { xbor = oi; break; } oi++; } }
   if (temporary) { int ai = 0, aliases = 0; while (ai < np) { aliases = aliases | effect_get(original, ai); ai++; } if (aliases & (EF_ALIAS | EF_UNKNOWN)) xaf = af_new(-1, 5, cp); }
  }
+ // a result from a function whose body comes later is checked once the body is read
+ xshadow = 0;
+ if (!ret && xbor < 0 && owner >= 0 && original >= ubase && !(sflag[original] & (F_DEF | F_EXT)) && tracked(owner) && (isptr(xty) || xty == tword)) xshadow = shadow_new(original, argowner_mask, owner);
 	if_value = 0;
 	if (ifs && !dry) {
 		word result_node = if_get(original);
@@ -1009,6 +1014,7 @@ int primary() {
 	if (i >= 0) {
 		if (if_local) if_value = if_local[i];
 		lreadpos[i] = tpack();
+		if (local_shadow && local_shadow[i]) shadow_use(i);
 		luse(i); effect_note_mask(effect_mask(C_VAR + i), EF_READ);
 		rs_note(lrskind[i], lrsoff[i]); os_at(toff, i);
 		xaf = lafact[i]; af_record(toff, xaf);
@@ -1588,7 +1594,7 @@ int postfix_tail(int c) {
 			xty = tword;
 			if (ft) xty = subst(ft[4], bs);
    if (ft && (ft[5] & 1)) c = C_FRESH;
-   else if (isptr(xty) || xty == tword) { effect_value = call_origins; if (isptr(xty)) xbor = call_owner; if (temporary) xaf = af_new(-1, 5, place); }
+   else if (isptr(xty) || xty == tword) { effect_value = call_origins; if (isptr(xty) || (ft && sig_borrows(ft[5]))) xbor = call_owner; if (temporary) xaf = af_new(-1, 5, place); }
 			xfloat = 0; if (isfl(xty)) xfloat = 1; xstr = 0;
 			continue;
 		}
diff --git a/src/compiler/types.zc b/src/compiler/types.zc
index 81547a5..322d0fd 100644
--- a/src/compiler/types.zc
+++ b/src/compiler/types.zc
@@ -105,6 +105,35 @@ word tsized(char* name, int bytes, int sgn) {
 	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) {
@@ -388,7 +417,8 @@ int ptype() {
 			}
 		}
 		expect(s_rp);
-		t = tfn(t, np, ps, np + np + tags * 64);
+		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;