merge work/demo-fixes: analyzer ownership fixes (back links, loop-built lists, .u inference), Io.print any args, block-end borrow messages

6 files changed, 141 insertions, 13 deletions

diff --git a/src/compiler/analyzer.zc b/src/compiler/analyzer.zc
index ff6a6c1..55a96bb 100644
--- a/src/compiler/analyzer.zc
+++ b/src/compiler/analyzer.zc
@@ -122,7 +122,7 @@ int shadow_finish(int from) {
   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();
+   errat(); ended_message(e[6], e[7], e[8], e[9], 0); 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;
  }
@@ -1009,7 +1009,7 @@ int end_owner(int i) {
  end_why = 0; end_whom = 0;
  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; }
+  if (j != i && lstate[j] == S_CHILD && lroot(j) == i) { local_ended[j] = info[2]; local_end_info[j] = info; lstate[j] = S_DEAD; }	// aliases and owned children go with it
   j++;
  }
  return 0;
@@ -1147,6 +1147,7 @@ int block_close(int save) {
 	unused_check(save);
 	exit_vars(fdepth, 1);
 	lend_drop(fdepth, save);
+	block_end_owners(save);
 	alias_end(fdepth, save);
 	while (i < save) { if (lhome[i] >= fdepth) { lstate[i] = S_DEAD; lhome[i] = fdepth - 1; } i++; }
 	local_drop(save);
@@ -1155,6 +1156,26 @@ int block_close(int save) {
 	return 0;
 }
 
+// owners freed at this block's end: an outer alias of one, or an outer owner
+// stored into one, dies with it and remembers where (why 9).
+int block_end_owners(int save) {
+	int i = save, j; word info = 0;
+	if (!fchk || !live) return 0;
+	while (i < nloc) {
+		if (lhome[i] >= fdepth && lstate[i] == S_M && lown[i]) {
+			info = 0; j = lbase;
+			while (j < save) {
+				if (lstate[j] == S_CHILD && lroot(j) == i) {
+					if (!info) { info = talloc(6); info[0] = lname[i]; info[1] = lpos[i]; info[2] = tpack(); info[3] = 9; info[4] = 0; info[5] = info[2]; }
+					local_ended[j] = info[2]; local_end_info[j] = info; lstate[j] = S_DEAD;
+				}
+				j++;
+			}
+		}
+		i++;
+	}
+	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;
@@ -1532,6 +1553,19 @@ int assigncheck(int k, int i, int rc) {
 			else lstate[i] = S_PLAIN;
 			return C_PLAIN;
 		}
+		// an outer owner moved into a deeper container takes the container back:
+		// head = item after item.next = head. the container leaves its block.
+		if (st == S_CHILD && lown[i] && j >= 0 && lroot(i) == j && lstate[j] == S_M && lown[j]
+			&& lhome[j] >= lhome[i] && !local_captured[i] && !local_captured[j]) {
+			int k = lbase;
+			while (k < nloc) { if (k != i && lstate[k] == S_CHILD && lowner[k] == j) lowner[k] = i; k++; }
+			lstate[i] = S_M; lused[i] = 0;
+			lnsz[i] = lnsz[j]; lleaf[i] = lleaf[j];
+			local_ended[i] = 0; local_end_info[i] = 0;
+			end_why = 3; end_whom = lname[i]; end_owner(j); luse(j); ev_put(j, EV_MOVE, i);
+			if (ltag[i] & 15) lstate[i] = ltag[i] & 15;
+			return C_PLAIN;
+		}
 		if (!empty(st)) {
 			cerrn(i, "still owns an object; overwriting it would leak it");
 			return C_PLAIN;
@@ -1578,6 +1612,9 @@ int assigncheck(int k, int i, int rc) {
 		touch(i);
 		if (rc == C_FRESH) { emitown(i); return C_PLAIN; }
 		if (j < 0) return C_PLAIN;
+		// a back link: storing the container's own owner (or the container itself)
+		// into it. it stays a plain reference; ownership would form a cycle.
+		if (r == j) { touch(j); 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");
@@ -1587,7 +1624,7 @@ int assigncheck(int k, int i, int rc) {
 			}
 			else { end_why = 4; end_whom = lname[i]; 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 if (lhome[j] < lhome[r] && (r != i || !lown[j] || (local_captured && (local_captured[i] || local_captured[j])))) 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;
 	}
@@ -1607,6 +1644,7 @@ int assigncheck(int k, int i, int rc) {
 // 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 ret_borrowed;
 int retcheck(int c) {
  int i;
  if (isptr(xty) || xty == tword) {
@@ -1633,9 +1671,16 @@ int retcheck(int c) {
 	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;
+	// a value that comes from a parameter the caller still owns (not a .d one,
+	// which is tracked) is a borrow: it can't become the caller's owned result.
+	if (c != C_FRESH && i < 0 && isptr(xty) && effect_mask(c)) {
+		if (fret) { cerr("a borrowed parameter cannot be returned as an owned result"); return 0; }
+		ret_borrowed = 1;
+	}
 	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 (ret_borrowed) cerr("this function also returns a borrowed parameter, so its result can't be owned");
 		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;
diff --git a/src/compiler/base.zc b/src/compiler/base.zc
index bd27e28..a209f2b 100644
--- a/src/compiler/base.zc
+++ b/src/compiler/base.zc
@@ -192,7 +192,7 @@ int bincap = bprec_BASE - bname_BASE, uncap = useq_BASE - uname_BASE, asgcap = a
 
 const int T_EOF = 0, T_NUM = 1, T_ID = 2, T_STR = 3, T_OP = 4, T_FLT = 5, T_BSTR = 6;
 const int K_FN = 1, K_GVAR = 2, K_GARR = 3, K_CONST = 4, K_KW = 5, K_ENH = 6, K_TYPE = 7, K_DOC = 8;
-const int F_DEF = 1, F_SIG = 2, F_UNTYPED = 4, F_STMT = 8, F_EXPR = 16, F_TOP = 32, F_FALLBACK = 64, F_GEN = 128, F_PRE = 256, F_O3 = 512, F_EXT = 1024, F_TPL = 2048, F_STATIC = 4096, F_DECL = 8192, F_RETOWN = 16384, F_EARLY = 32768;
+const int F_DEF = 1, F_SIG = 2, F_UNTYPED = 4, F_STMT = 8, F_EXPR = 16, F_TOP = 32, F_FALLBACK = 64, F_GEN = 128, F_PRE = 256, F_O3 = 512, F_EXT = 1024, F_TPL = 2048, F_STATIC = 4096, F_DECL = 8192, F_RETOWN = 16384, F_EARLY = 32768, F_GUESS = 65536;
 // variable states for the lifetime analyzer
 const int S_PLAIN = 0, S_M = 1, S_U = 2, S_D = 3, S_DEAD = 4, S_CHILD = 5, S_BORROW = 6;
 // expression classes: plain word, a new object, or a bare variable (C_VAR + index)
@@ -986,9 +986,16 @@ int cerr(char* msg) {
 }
 // how an owner ended, from end_owner's record: the use, the owner, what ended it and where.
 // "r: used after it was given away; r borrows t, and t was freed on line 5 (t declared on line 4)"
-int ended_message(char* use, word info, char* root, int cause) {
+int ended_message(char* use, word info, char* root, int cause, int own) {
  char* owner = root; int why = 0; char* whom = 0;
  if (info) { owner = info[0]; why = info[3]; whom = info[4]; dg_related(info[5], info[1], why, owner); }
+ if (why == 9) {
+  rt.put_s(use); rt.put_s(": ");
+  if (rt.eq_w(use, owner)) rt.put_s("was freed");
+  else { if (own) rt.put_s("belongs to "); else rt.put_s("borrows from "); rt.put_s(owner); rt.put_s(", which was freed"); }
+  rt.put_s(" at the end of its block (line "); rt.put_n(cause & 0xFFFFFF); rt.put_c(')');
+  return 0;
+ }
  rt.put_s(use); rt.put_s(": used after it was given away; ");
  if (!rt.eq_w(use, owner)) { rt.put_s(use); rt.put_s(" borrows "); rt.put_s(owner); rt.put_s(", and "); }
  rt.put_s(owner);
@@ -1014,7 +1021,7 @@ int cerrn(int i, char* msg) {
    if (!info && local_end_info) info = local_end_info[root];
    if (info) cause = info[2]; else if (local_ended) cause = local_ended[root];
   }
-  if (cause && !panic && !dry) { errat(); dg_place(lreadpos[i]); ended_message(lname[i], info, lname[root], cause); errend(); }
+  if (cause && !panic && !dry) { errat(); dg_place(lreadpos[i]); ended_message(lname[i], info, lname[root], cause, lown[i]); errend(); }
   else serrn(lname[i], msg);
  }
  return 0;
diff --git a/src/compiler/decl.zc b/src/compiler/decl.zc
index 55e23a7..313d1ab 100644
--- a/src/compiler/decl.zc
+++ b/src/compiler/decl.zc
@@ -81,8 +81,48 @@ int prescan_fn(int ret, int n, int o3) {
 		sflag[s] = sflag[s] | F_SIG | F_PRE;
 	}
 	if (o3) sflag[s] = sflag[s] | F_O3;
+	if (!ret && is_op(s_lb) && prescan_owned(n)) { sflag[s] = sflag[s] | F_GUESS; if (sflag[s] & F_PRE) ssig[s] = ssig[s] | 1; }
 	return 0;
 }
+// true for a token that makes a fresh owned object when called: new or heap.
+// nothing else: a call to the function itself is no evidence.
+int prescan_maker() {
+	return tk == T_ID && (rt.eq_w(tv, "rt.new") || rt.eq_w(tv, "new") || rt.eq_w(tv, "heap"));
+}
+// prescan: at the { of an untagged function's body, guess whether it returns an
+// owned object: a return of a fresh object, or of a local last set from one.
+// the guess only makes the function compile as if declared .u; its body is then
+// checked against that, so a wrong guess is an error, never a silent leak.
+int prescan_owned(int self) {
+	int depth = 0, n, k, found = 0, nown = 0, decl = 0; let owned[16];
+	while (tk != T_EOF) {
+		// a declaration's name follows a type name, a *, let or a comma; a plain
+		// assignment (to a global, say) follows ; { or }
+		int was = decl;
+		decl = tk == T_ID || (tk == T_OP && (rt.eq_w(tv, "*") || rt.eq_w(tv, ",")));
+		if (is_op(s_lb)) depth++;
+		else if (is_op(s_rb)) { depth--; if (!depth) { next(); return found; } }
+		else if (tk == T_ID && rt.eq_w(tv, "return")) {
+			next();
+			if (tk == T_ID) {
+				n = tv; peek();
+				if (pk_tk == T_OP && pk_tv == s_lp && prescan_maker()) found = 1;
+				else if (pk_tk == T_OP && pk_tv == s_semi) { k = 0; while (k < nown) { if (owned[k] == n) found = 1; k++; } }
+			}
+			continue;
+		}
+		else if (tk == T_ID && was) {
+			n = tv; peek();
+			if (pk_tk == T_OP && pk_tv == s_eq) {
+				next(); next();
+				if (prescan_maker()) { peek(); if (pk_tk == T_OP && pk_tv == s_lp && nown < 16) { owned[nown] = n; nown++; } }
+				continue;
+			}
+		}
+		next();
+	}
+	return found;
+}
 // scan ahead, without emitting code, to learn what a block of tokens contains.
 int prescan(int kind, int obj) {
 	int depth = 0, sp = panic, sn = nerr, pend = 0, po3 = 0, n, dep; char* oldmodule = module_name; word oldimports = module_imports;
@@ -409,6 +449,7 @@ int fndef(int chk, int rty, int ret, int n) {
 		if (amb & 1) { t = lookup(pn[i]); if (t >= 0 && skind[t] == K_TYPE) { pty[i] = sval[t]; typed = 1; } }
 		amb = amb >> 1; i++;
 	}
+	if (!ret && (sflag[s] & F_GUESS)) ret = 1;	// prescan saw it return an owned object: compile it as .u
 	sig = ret + np + np + tags * 64;
 	lo = borrows_clause(pn, np, 1);
 	// a definition after a prototype keeps the prototype's borrows clause
@@ -448,7 +489,7 @@ int fndef(int chk, int rty, int ret, int n) {
 	fixall(sfix[s], here); sfix[s] = 0;
 	fn_begin(chk, ret);
 	lt = lt_begin(sval[s], sname[s], lfl); xc_fn = sname[s];
-	finsym = s; finfer = !ret;
+	finsym = s; finfer = !ret; ret_borrowed = 0;
  effect_current = effect_record(s); rt.fill_w(effect_current, 0, 50); effect_current[0] = 1; if (!chk || stubgen) effect_current[0] = 2; effect_current[1] = np;
  i = 0; while (i < np) { if (pt[i] == 2) { effect_current[2 + i] = EF_CONSUME; effect_current[26 + i] = EF_CONSUME; } i++; }
 	if (typed && explicit_rty) fty = rty;
diff --git a/src/compiler/expr.zc b/src/compiler/expr.zc
index 141ca16..2935a9b 100644
--- a/src/compiler/expr.zc
+++ b/src/compiler/expr.zc
@@ -409,9 +409,42 @@ int shifthint(int p, int v) {
 //      function isn't defined yet)
 //   6. the result's type and class are set: .u functions return C_FRESH, which
 //      is how the analyzer knows the caller now owns a new object
+// std.Io.print(a, b, ...) and println: any mix of strings, byte strings,
+// numbers and floats. each argument goes to the writer for its type; a fresh
+// owned string is written and then freed. println ends with a line break.
+int printcall(int line) {
+	int c; char* w;
+	expect(s_lp);
+	if (!is_op(s_rp)) {
+		while (1) {
+			c = expr(); rval();
+			if (xty == tbstr || xstr) w = "std.Io.put_bs";
+			else if (xfloat) w = "std.Io.put_f";
+			else if (xty[0] == TY_PTR && xty[4] == tchar) w = "std.Io.put_s";
+			else if (xty[0] == TY_ARR && xty[4] == tchar) w = "std.Io.put_s";
+			else w = "std.Io.put_n";
+			if (c == C_FRESH && fchk) {
+				if (!rt.eq_w(w, "std.Io.put_s") && !rt.eq_w(w, "std.Io.put_bs")) cerr("a new object can't be printed; bind it to a name first");
+				lit(0); op(O_PICK); callname(intern(w)); op(O_DROP); callname(s_free); op(O_DROP);
+			} else {
+				if (c >= C_VAR && tracked(c - C_VAR)) touch(c - C_VAR);
+				callname(intern(w)); op(O_DROP);
+			}
+			if (!accept(s_comma)) break;
+		}
+	}
+	expect(s_rp);
+	if (line) { lit(10); callname(intern("rt.put_c")); op(O_DROP); }
+	lit(0);
+	lv = 0; lvk = LV_NONE; xty = tint; xzero = 0; xbor = -1; xconst = 0;
+	xfloat = 0; xstr = 0; xlenloc = -1; xstamp = 0; xaf = 0;
+	return C_PLAIN;
+}
 int call(int s) {
 	int np, tags = 0, ret = 0; word ft = stype[s]; word[8] bs; int rs, rhs_type = 0, kop, cp = callpos, original = s; word storage; int origin, temporary, owner; word origins, owner_fact;
 	word requirements = effect_requirements, edges = effect_edges;
+ if (rt.eq_w(sname[s], "std.Io.print")) return printcall(0);
+ if (rt.eq_w(sname[s], "std.Io.println")) return printcall(1);
  borrow_depth++;
 	if (sname[s] == s_new && skind[s] == K_FN) {
 		peek();
diff --git a/src/lib/std.zc b/src/lib/std.zc
index b206888..5c86aa6 100644
--- a/src/lib/std.zc
+++ b/src/lib/std.zc
@@ -421,15 +421,16 @@ struct Host {
 // called as std.Io.name(args). the writers go through rt.put_c, so a capture
 // (std.capture) sees their text too. the rt names (rt.put_n, rt.put_s and the
 // rest) stay; these are the same operations, grouped with the library.
-// zc has no varargs or overloading, so print takes a string, and numbers have
-// their own writers: std.Io.print("n = "); std.Io.put_n(n); std.Io.nl();
+// print and println take any mix of strings, byte strings, numbers and floats,
+// each written by its type: std.Io.println("n = ", n, ", x = ", x);
 struct Io {
-	// writes a string.
-	//   s: the text
+	// writes its arguments in order: any mix of strings, byte strings, numbers
+	// and floats (the compiler picks the writer for each argument's type).
+	//   s: the first value; more may follow
 	//   returns: 0
 	static int print(char* s) { return rt.put_s(s); }
-	// writes a string and a line break.
-	//   s: the text
+	// writes its arguments like print, then a line break. no arguments: just the line break.
+	//   s: the first value; more may follow
 	//   returns: 0
 	static int println(char* s) { rt.put_s(s); return rt.put_c(10); }
 	// writes a line break.
diff --git a/src/lsp/server.zc b/src/lsp/server.zc
index 85f3ea5..536d71c 100644
--- a/src/lsp/server.zc
+++ b/src/lsp/server.zc
@@ -278,6 +278,7 @@ int diag_related(int at) {
 			else if (why == 3) what = " was moved here"; else if (why == 4) what = " was stored into a container here";
 			else if (why == 5) what = " was returned here"; else if (why == 6) what = " was stored in a global here";
 			else if (why == 7) what = " was freed by this reassignment"; else if (why == 8) what = " was pushed into an array here";
+			else if (why == 9) what = " was freed at the end of this block";
 			ws(",\"relatedInformation\":[{\"location\":"); wplace(e[1]); ws(",\"message\":\"owner "); ws(e[4]); ws(what); ws("\"}");
 			if (e[2]) { ws(",{\"location\":"); wplace(e[2]); ws(",\"message\":\"owner "); ws(e[4]); ws(" is declared here\"}"); }
 			wc(']');