+When exiting a sequential scope that immediately enclosed parallel
+scopes, we need to resolve any pending-scope variables. If there was
+no `else` clause, and we cannot determine that the `switch` was exhaustive,
+we need to mark all pending-scope variable as out-of-scope. Otherwise
+all pending-scope variables become conditionally scoped.
+
+###### ast
+ enum closetype { CloseSequential, CloseFunction, CloseParallel, CloseElse };
+
+###### ast functions
+
+ static struct variable *var_decl(struct parse_context *c, struct text s)
+ {
+ struct binding *b = find_binding(c, s);
+ struct variable *v = b->var;
+
+ switch (v ? v->scope : OutScope) {
+ case InScope:
+ /* Caller will report the error */
+ return NULL;
+ case CondScope:
+ for (;
+ v && v->scope == CondScope;
+ v = v->previous)
+ v->scope = OutScope;
+ break;
+ default: break;
+ }
+ v = calloc(1, sizeof(*v));
+ v->previous = b->var;
+ b->var = v;
+ v->name = b;
+ v->merged = v;
+ v->min_depth = v->depth = c->scope_depth;
+ v->scope = InScope;
+ v->in_scope = c->in_scope;
+ v->scope_start = c->scope_count;
+ c->in_scope = v;
+ ## variable init
+ return v;
+ }
+
+ static struct variable *var_ref(struct parse_context *c, struct text s)
+ {
+ struct binding *b = find_binding(c, s);
+ struct variable *v = b->var;
+ struct variable *v2;
+
+ switch (v ? v->scope : OutScope) {
+ case OutScope:
+ case PendingScope:
+ /* Caller will report the error */
+ return NULL;
+ case CondScope:
+ /* All CondScope variables of this name need to be merged
+ * and become InScope
+ */
+ v->depth = v->min_depth;
+ v->scope = InScope;
+ for (v2 = v->previous;
+ v2 && v2->scope == CondScope;
+ v2 = v2->previous)
+ variable_merge(v, v2);
+ break;
+ case InScope:
+ break;
+ }
+ return v;
+ }
+
+ static int var_refile(struct parse_context *c, struct variable *v)
+ {
+ /* Variable just went out of scope. Add it to the out_scope
+ * list, sorted by ->scope_start
+ */
+ struct variable **vp = &c->out_scope;
+ while ((*vp) && (*vp)->scope_start < v->scope_start)
+ vp = &(*vp)->in_scope;
+ v->in_scope = *vp;
+ *vp = v;
+ return 0;
+ }
+
+ static void var_block_close(struct parse_context *c, enum closetype ct,
+ struct exec *e)
+ {
+ /* Close off all variables that are in_scope.
+ * Some variables in c->scope may already be not-in-scope,
+ * such as when a PendingScope variable is hidden by a new
+ * variable with the same name.
+ * So we check for v->name->var != v and drop them.
+ * If we choose to make a variable OutScope, we drop it
+ * immediately too.
+ */
+ struct variable *v, **vp, *v2;
+
+ scope_pop(c);
+ for (vp = &c->in_scope;
+ (v = *vp) && v->min_depth > c->scope_depth;
+ (v->scope == OutScope || v->name->var != v)
+ ? (*vp = v->in_scope, var_refile(c, v))
+ : ( vp = &v->in_scope, 0)) {
+ v->min_depth = c->scope_depth;
+ if (v->name->var != v)
+ /* This is still in scope, but we haven't just
+ * closed the scope.
+ */
+ continue;
+ v->min_depth = c->scope_depth;
+ if (v->scope == InScope)
+ v->scope_end = c->scope_count;
+ if (v->scope == InScope && e && !v->global) {
+ /* This variable gets cleaned up when
+ * 'e' finishes
+ */
+ variable_unlink_exec(v);
+ v->cleanup_exec = e;
+ v->next_free = e->to_free;
+ e->to_free = v;
+ }
+ switch (ct) {
+ case CloseElse:
+ case CloseParallel: /* handle PendingScope */
+ switch(v->scope) {
+ case InScope:
+ case CondScope:
+ if (c->scope_stack->child_count == 1)
+ /* first among parallel branches */
+ v->scope = PendingScope;
+ else if (v->previous &&
+ v->previous->scope == PendingScope)
+ /* all previous branches used name */
+ v->scope = PendingScope;
+ else
+ v->scope = OutScope;
+ if (ct == CloseElse) {
+ /* All Pending variables with
+ * this name are now Conditional
+ */
+ for (v2 = v;
+ v2 && v2->scope == PendingScope;
+ v2 = v2->previous)
+ v2->scope = CondScope;
+ }
+ break;
+ case PendingScope:
+ /* Not possible as it would require
+ * parallel scope to be nested immediately
+ * in a parallel scope, and that never
+ * happens.
+ */ // NOTEST
+ case OutScope:
+ /* Not possible as we already tested for
+ * OutScope
+ */
+ abort(); // NOTEST
+ }
+ break;
+ case CloseFunction:
+ if (v->scope == CondScope)
+ /* Condition cannot continue past end of
+ * function */
+ v->scope = InScope;
+ /* fallthrough */
+ case CloseSequential:
+ switch (v->scope) {
+ case InScope:
+ v->scope = OutScope;
+ break;
+ case PendingScope:
+ /* There was no 'else', so we can only become
+ * conditional if we know the cases were exhaustive,
+ * and that doesn't mean anything yet.
+ * So only labels become conditional..
+ */
+ for (v2 = v;
+ v2 && v2->scope == PendingScope;
+ v2 = v2->previous)
+ v2->scope = OutScope;
+ break;
+ case CondScope:
+ case OutScope: break;
+ }
+ break;
+ }
+ }
+ }
+
+#### Storing Values
+
+The value of a variable is stored separately from the variable, on an
+analogue of a stack frame. There are (currently) two frames that can be
+active. A global frame which currently only stores constants, and a
+stacked frame which stores local variables. Each variable knows if it
+is global or not, and what its index into the frame is.
+
+Values in the global frame are known immediately they are relevant, so
+the frame needs to be reallocated as it grows so it can store those
+values. The local frame doesn't get values until the interpreted phase
+is started, so there is no need to allocate until the size is known.
+
+We initialise the `frame_pos` to an impossible value, so that we can
+tell if it was set or not later.
+
+###### variable fields
+ short frame_pos;
+ short global;
+
+###### variable init
+ v->frame_pos = -1;
+
+###### parse context
+
+ short global_size, global_alloc;
+ short local_size;
+ void *global, *local;
+
+###### forward decls
+ static struct value *global_alloc(struct parse_context *c, struct type *t,
+ struct variable *v, struct value *init);
+
+###### ast functions
+
+ static struct value *var_value(struct parse_context *c, struct variable *v)
+ {
+ if (!v->global) {
+ if (!c->local || !v->type)
+ return NULL; // NOTEST
+ if (v->frame_pos + v->type->size > c->local_size) {
+ printf("INVALID frame_pos\n"); // NOTEST
+ exit(2); // NOTEST
+ }
+ return c->local + v->frame_pos;
+ }
+ if (c->global_size > c->global_alloc) {
+ int old = c->global_alloc;
+ c->global_alloc = (c->global_size | 1023) + 1024;
+ c->global = realloc(c->global, c->global_alloc);
+ memset(c->global + old, 0, c->global_alloc - old);
+ }
+ return c->global + v->frame_pos;
+ }
+
+ static struct value *global_alloc(struct parse_context *c, struct type *t,
+ struct variable *v, struct value *init)
+ {
+ struct value *ret;
+ struct variable scratch;
+
+ if (t->prepare_type)
+ t->prepare_type(c, t, 1); // NOTEST
+
+ if (c->global_size & (t->align - 1))
+ c->global_size = (c->global_size + t->align) & ~(t->align-1);
+ if (!v) {
+ v = &scratch;
+ v->type = t;
+ }
+ v->frame_pos = c->global_size;
+ v->global = 1;
+ c->global_size += v->type->size;
+ ret = var_value(c, v);
+ if (init)
+ memcpy(ret, init, t->size);
+ else
+ val_init(t, ret); // NOTEST
+ return ret;
+ }
+
+As global values are found -- struct field initializers, labels etc --
+`global_alloc()` is called to record the value in the global frame.
+
+When the program is fully parsed, each function is analysed, we need to
+walk the list of variables local to that function and assign them an
+offset in the stack frame. For this we have `scope_finalize()`.
+
+We keep the stack from dense by re-using space for between variables
+that are not in scope at the same time. The `out_scope` list is sorted
+by `scope_start` and as we process a varible, we move it to an FIFO
+stack. For each variable we consider, we first discard any from the
+stack anything that went out of scope before the new variable came in.
+Then we place the new variable just after the one at the top of the
+stack.
+
+###### ast functions
+
+ static void scope_finalize(struct parse_context *c, struct type *ft)
+ {
+ int size = ft->function.local_size;
+ struct variable *next = ft->function.scope;
+ struct variable *done = NULL;
+
+ while (next) {
+ struct variable *v = next;
+ struct type *t = v->type;
+ int pos;
+ next = v->in_scope;
+ if (v->merged != v)
+ continue;
+ if (!t)
+ continue; // NOTEST
+ if (v->frame_pos >= 0)
+ continue;
+ while (done && done->scope_end < v->scope_start)
+ done = done->in_scope;
+ if (done)
+ pos = done->frame_pos + done->type->size;
+ else
+ pos = ft->function.local_size;
+ if (pos & (t->align - 1))
+ pos = (pos + t->align) & ~(t->align-1);
+ v->frame_pos = pos;
+ if (size < pos + v->type->size)
+ size = pos + v->type->size;
+ v->in_scope = done;
+ done = v;
+ }
+ c->out_scope = NULL;
+ ft->function.local_size = size;
+ }
+
+###### free context storage
+ free(context.global);
+
+#### Variables as executables
+
+Just as we used a `val` to wrap a value into an `exec`, we similarly
+need a `var` to wrap a `variable` into an exec. While each `val`
+contained a copy of the value, each `var` holds a link to the variable
+because it really is the same variable no matter where it appears.
+When a variable is used, we need to remember to follow the `->merged`
+link to find the primary instance.
+
+When a variable is declared, it may or may not be given an explicit
+type. We need to record which so that we can report the parsed code
+correctly.
+
+###### exec type
+ Xvar,
+
+###### ast
+ struct var {
+ struct exec;
+ struct variable *var;
+ };
+
+###### variable fields
+ int explicit_type;
+
+###### Grammar
+
+ $TERM : ::
+
+ $*var
+ VariableDecl -> IDENTIFIER : ${ {
+ struct variable *v = var_decl(c, $1.txt);
+ $0 = new_pos(var, $1);
+ $0->var = v;
+ if (v)
+ v->where_decl = $0;
+ else {
+ v = var_ref(c, $1.txt);
+ $0->var = v;
+ type_err(c, "error: variable '%v' redeclared",
+ $0, NULL, 0, NULL);
+ type_err(c, "info: this is where '%v' was first declared",
+ v->where_decl, NULL, 0, NULL);
+ }
+ } }$
+ | IDENTIFIER :: ${ {
+ struct variable *v = var_decl(c, $1.txt);
+ $0 = new_pos(var, $1);
+ $0->var = v;
+ if (v) {
+ v->where_decl = $0;
+ v->constant = 1;
+ } else {
+ v = var_ref(c, $1.txt);
+ $0->var = v;
+ type_err(c, "error: variable '%v' redeclared",
+ $0, NULL, 0, NULL);
+ type_err(c, "info: this is where '%v' was first declared",
+ v->where_decl, NULL, 0, NULL);
+ }
+ } }$
+ | IDENTIFIER : Type ${ {
+ struct variable *v = var_decl(c, $1.txt);
+ $0 = new_pos(var, $1);
+ $0->var = v;
+ if (v) {
+ v->where_decl = $0;
+ v->where_set = $0;
+ v->type = $<Type;
+ v->explicit_type = 1;
+ } else {
+ v = var_ref(c, $1.txt);
+ $0->var = v;
+ type_err(c, "error: variable '%v' redeclared",
+ $0, NULL, 0, NULL);
+ type_err(c, "info: this is where '%v' was first declared",
+ v->where_decl, NULL, 0, NULL);
+ }
+ } }$
+ | IDENTIFIER :: Type ${ {
+ struct variable *v = var_decl(c, $1.txt);
+ $0 = new_pos(var, $1);
+ $0->var = v;
+ if (v) {
+ v->where_decl = $0;
+ v->where_set = $0;
+ v->type = $<Type;
+ v->constant = 1;
+ v->explicit_type = 1;
+ } else {
+ v = var_ref(c, $1.txt);
+ $0->var = v;
+ type_err(c, "error: variable '%v' redeclared",
+ $0, NULL, 0, NULL);
+ type_err(c, "info: this is where '%v' was first declared",
+ v->where_decl, NULL, 0, NULL);
+ }
+ } }$
+
+ $*exec
+ Variable -> IDENTIFIER ${ {
+ struct variable *v = var_ref(c, $1.txt);
+ $0 = new_pos(var, $1);
+ if (v == NULL) {
+ /* This might be a global const or a label
+ * Allocate a var with impossible type Tnone,
+ * which will be adjusted when we find out what it is,
+ * or will trigger an error.
+ */
+ v = var_decl(c, $1.txt);
+ if (v) {
+ v->type = Tnone;
+ v->where_decl = $0;
+ v->where_set = $0;
+ }
+ }
+ cast(var, $0)->var = v;
+ } }$
+
+###### print exec cases
+ case Xvar:
+ {
+ struct var *v = cast(var, e);
+ if (v->var) {
+ struct binding *b = v->var->name;
+ printf("%.*s", b->name.len, b->name.txt);
+ }
+ break;
+ }
+
+###### format cases
+ case 'v':
+ if (loc && loc->type == Xvar) {
+ struct var *v = cast(var, loc);
+ if (v->var) {
+ struct binding *b = v->var->name;
+ fprintf(stderr, "%.*s", b->name.len, b->name.txt);
+ } else
+ fputs("???", stderr); // NOTEST
+ } else
+ fputs("NOTVAR", stderr); // NOTEST
+ break;
+
+###### propagate exec cases
+
+ case Xvar:
+ {
+ struct var *var = cast(var, prog);
+ struct variable *v = var->var;
+ if (!v) {
+ type_err(c, "%d:BUG: no variable!!", prog, NULL, 0, NULL); // NOTEST
+ return Tnone; // NOTEST
+ }
+ v = v->merged;
+ if (v->type == Tnone && v->where_decl == prog)
+ type_err(c, "error: variable used but not declared: %v",
+ prog, NULL, 0, NULL);
+ if (v->type == NULL) {
+ if (type && !(*perr & Efail)) {
+ v->type = type;
+ v->where_set = prog;
+ *perr |= Eretry;
+ }
+ } else if (!type_compat(type, v->type, rules)) {
+ type_err(c, "error: expected %1 but variable '%v' is %2", prog,
+ type, rules, v->type);
+ type_err(c, "info: this is where '%v' was set to %1", v->where_set,
+ v->type, rules, NULL);
+ }
+ if (!v->global || v->frame_pos < 0)
+ *perr |= Eruntime;
+ if (v->constant)
+ *perr |= Econst;
+ return v->type;
+ }
+
+###### interp exec cases
+ case Xvar:
+ {
+ struct var *var = cast(var, e);
+ struct variable *v = var->var;
+
+ v = v->merged;
+ lrv = var_value(c, v);
+ rvtype = v->type;
+ break;
+ }
+
+###### ast functions
+
+ static void free_var(struct var *v)
+ {
+ free(v);
+ }
+
+###### free exec cases
+ case Xvar: free_var(cast(var, e)); break;
+
+### Complex types
+
+Now that we have the shape of the interpreter in place we can add some
+complex types and connected them in to the data structures and the
+different phases of parse, analyse, print, interpret.
+
+Being "complex" the language will naturally have syntax to access
+specifics of objects of these types. These will fit into the grammar as
+"Terms" which are the things that are combined with various operators to
+form an "Expression". Where a Term is formed by some operation on another
+Term, the subordinate Term will always come first, so for example a
+member of an array will be expressed as the Term for the array followed
+by an index in square brackets. The strict rule of using postfix
+operations makes precedence irrelevant within terms. To provide a place
+to put the grammar for terms of each type, we will start out by
+introducing the "Term" grammar production, with contains at least a
+simple "Value" (to be explained later).
+
+We also take this opportunity to introduce the "ExpressionsList" which
+is a simple comma-separated list of expressions - it may be used in
+various places.
+
+###### declare terminals
+ $TERM ,
+
+###### Grammar
+ $*exec
+ Term -> Value ${ $0 = $<1; }$
+ | Variable ${ $0 = $<1; }$
+ ## term grammar
+
+ $*binode
+ ExpressionList -> ExpressionList , Expression ${
+ $0 = new(binode);
+ $0->op = List;
+ $0->left = $<1;
+ $0->right = $<3;
+ }$
+ | Expression ${
+ $0 = new(binode);
+ $0->op = List;
+ $0->left = NULL;
+ $0->right = $<1;
+ }$
+
+Thus far the complex types we have are arrays, structs, functions and
+references.
+
+#### Arrays
+
+Arrays can be declared by giving a size and a type, as `[size]type' so
+`freq:[26]number` declares `freq` to be an array of 26 numbers. The
+size can be either a literal number, or a named constant. Some day an
+arbitrary expression will be supported.
+
+As a formal parameter to a function, the array can be declared with
+unknown size `name:[]string`. This is currently only supported for the
+"argv" parameter to "main" but will be extended more generally in a
+later version of the language. The length of this array - or any array
+- can be found with the "[]" postfix operator.
+
+Arrays cannot be assigned. When reference are extend to allow array
+slices which can refer to part or all of an array the assignment
+syntax will create a slice. For now, an array can only ever be
+referenced by the name it is declared with. It is likely that a
+"`copy`" primitive will eventually be defined which can be used to make a
+copy of an array with controllable recursive depth.
+
+For now we have two sorts of array, those with fixed size either because
+it is given as a literal number or because it is a struct member (which
+cannot have a runtime-changing size), and those with a size that is
+determined at runtime - local variables with a const size. The former
+have their size calculated at parse time, the latter at run time.
+
+For the latter type, the `size` field of the type is the size of a
+pointer, and the array is reallocated every time it comes into scope.
+
+We differentiate struct fields with a const size from local variables
+with a const size by whether they are prepared at parse time or not.
+
+###### type union fields
+
+ struct {
+ int unspec; // size is unspecified - vsize must be set.
+ short size;
+ short static_size;
+ struct variable *vsize;
+ struct type *member;
+ } array;
+
+###### value union fields
+ void *array; // used if not static_size
+
+###### value functions
+
+ static int array_prepare_type(struct parse_context *c, struct type *type,
+ int parse_time)
+ {
+ struct value *vsize;
+ mpz_t q;
+ if (type->array.static_size)
+ return 1; // NOTEST - guard against reentry
+ if (type->array.unspec && parse_time)
+ return 1; // NOTEST - unspec is still incomplete
+ if (parse_time && type->array.vsize && !type->array.vsize->global)
+ return 1; // NOTEST - should be impossible
+
+ if (type->array.vsize) {
+ vsize = var_value(c, type->array.vsize);
+ if (!vsize)
+ return 1; // NOTEST - should be impossible
+ mpz_init(q);
+ mpz_tdiv_q(q, mpq_numref(vsize->num), mpq_denref(vsize->num));
+ type->array.size = mpz_get_si(q);
+ mpz_clear(q);
+ }
+ if (!parse_time)
+ return 1;
+ if (type->array.member->size <= 0)
+ return 0; // NOTEST - error caught before here
+
+ type->array.static_size = 1;
+ type->size = type->array.size * type->array.member->size;
+ type->align = type->array.member->align;
+
+ return 1;
+ }
+
+ static void array_init(struct type *type, struct value *val)
+ {
+ int i;
+ void *ptr = val->ptr;
+
+ if (!val)
+ return; // NOTEST
+ if (!type->array.static_size) {
+ val->array = calloc(type->array.size,
+ type->array.member->size);
+ ptr = val->array;
+ }
+ for (i = 0; i < type->array.size; i++) {
+ struct value *v;
+ v = (void*)ptr + i * type->array.member->size;
+ val_init(type->array.member, v);
+ }
+ }
+
+ static void array_free(struct type *type, struct value *val)
+ {
+ int i;
+ void *ptr = val->ptr;
+
+ if (!type->array.static_size)
+ ptr = val->array;
+ for (i = 0; i < type->array.size; i++) {
+ struct value *v;
+ v = (void*)ptr + i * type->array.member->size;
+ free_value(type->array.member, v);
+ }
+ if (!type->array.static_size)
+ free(ptr);
+ }
+
+ static int array_compat(struct type *require, struct type *have,
+ enum val_rules rules)
+ {
+ if (have->compat != require->compat)
+ return 0;
+ /* Both are arrays, so we can look at details */
+ if (!type_compat(require->array.member, have->array.member, 0))
+ return 0;
+ if (have->array.unspec && require->array.unspec &&
+ have->array.size != require->array.size)
+ return 0; // NOTEST
+ if (have->array.unspec || require->array.unspec)
+ return 1;
+ if (require->array.vsize == NULL && have->array.vsize == NULL)
+ return require->array.size == have->array.size;
+
+ return require->array.vsize == have->array.vsize;
+ }
+
+ static void array_print_type(struct type *type, FILE *f)
+ {
+ fputs("[", f);
+ if (type->array.vsize) {
+ struct binding *b = type->array.vsize->name;
+ fprintf(f, "%.*s%s]", b->name.len, b->name.txt,
+ type->array.unspec ? "::" : "");
+ } else if (type->array.size)
+ fprintf(f, "%d]", type->array.size);
+ else
+ fprintf(f, "]");
+ type_print(type->array.member, f);
+ }
+
+ static struct type array_prototype = {
+ .init = array_init,
+ .prepare_type = array_prepare_type,
+ .print_type = array_print_type,
+ .compat = array_compat,
+ .free = array_free,
+ .size = sizeof(void*),
+ .align = sizeof(void*),
+ };
+
+###### declare terminals
+ $TERM [ ]
+
+###### type grammar
+
+ | [ NUMBER ] Type ${ {
+ char tail[3];
+ mpq_t num;
+ struct type *t;
+ int elements = 0;
+
+ if (number_parse(num, tail, $2.txt) == 0)
+ tok_err(c, "error: unrecognised number", &$2);
+ else if (tail[0]) {
+ tok_err(c, "error: unsupported number suffix", &$2);
+ mpq_clear(num);
+ } else {
+ elements = mpz_get_ui(mpq_numref(num));
+ if (mpz_cmp_ui(mpq_denref(num), 1) != 0) {
+ tok_err(c, "error: array size must be an integer",
+ &$2);
+ } else if (mpz_cmp_ui(mpq_numref(num), 1UL << 30) >= 0)
+ tok_err(c, "error: array size is too large",
+ &$2);
+ mpq_clear(num);
+ }
+
+ $0 = t = add_anon_type(c, &array_prototype, "array[%d]", elements );
+ t->array.size = elements;
+ t->array.member = $<4;
+ t->array.vsize = NULL;
+ } }$
+
+ | [ IDENTIFIER ] Type ${ {
+ struct variable *v = var_ref(c, $2.txt);