+ static void _print_value(struct type *type, struct value *v, FILE *f)
+ {
+ switch (type->vtype) {
+ case Vnone: // NOTEST
+ fprintf(f, "*no-value*"); break; // NOTEST
+ case Vlabel: // NOTEST
+ fprintf(f, "*label-%p*", v->label); break; // NOTEST
+ case Vstr:
+ fprintf(f, "%.*s", v->str.len, v->str.txt); break;
+ case Vbool:
+ fprintf(f, "%s", v->bool ? "True":"False"); break;
+ case Vnum:
+ {
+ mpf_t fl;
+ mpf_init2(fl, 20);
+ mpf_set_q(fl, v->num);
+ gmp_fprintf(f, "%Fg", fl);
+ mpf_clear(fl);
+ break;
+ }
+ }
+ }
+
+ static void _free_value(struct type *type, struct value *v);
+
+ static struct type base_prototype = {
+ .init = _val_init,
+ .print = _print_value,
+ .cmp_order = _value_cmp,
+ .cmp_eq = _value_cmp,
+ .dup = _dup_value,
+ .free = _free_value,
+ };
+
+ static struct type *Tbool, *Tstr, *Tnum, *Tnone, *Tlabel;
+
+###### ast functions
+ static struct type *add_base_type(struct parse_context *c, char *n,
+ enum vtype vt, int size)
+ {
+ struct text txt = { n, strlen(n) };
+ struct type *t;
+
+ t = add_type(c, txt, &base_prototype);
+ t->vtype = vt;
+ t->size = size;
+ t->align = size > sizeof(void*) ? sizeof(void*) : size;
+ if (t->size & (t->align - 1))
+ t->size = (t->size | (t->align - 1)) + 1; // NOTEST
+ return t;
+ }
+
+###### context initialization
+
+ Tbool = add_base_type(&context, "Boolean", Vbool, sizeof(char));
+ Tstr = add_base_type(&context, "string", Vstr, sizeof(struct text));
+ Tnum = add_base_type(&context, "number", Vnum, sizeof(mpq_t));
+ Tnone = add_base_type(&context, "none", Vnone, 0);
+ Tlabel = add_base_type(&context, "label", Vlabel, sizeof(void*));
+
+##### Base Values
+
+We have already met values as separate objects. When manifest constants
+appear in the program text, that must result in an executable which has
+a constant value. So the `val` structure embeds a value in an
+executable.
+
+###### exec type
+ Xval,
+
+###### ast
+ struct val {
+ struct exec;
+ struct type *vtype;
+ struct value val;
+ };
+
+###### ast functions
+ struct val *new_val(struct type *T, struct token tk)
+ {
+ struct val *v = new_pos(val, tk);
+ v->vtype = T;
+ return v;
+ }
+
+###### Grammar
+
+ $TERM True False
+
+ $*val
+ Value -> True ${
+ $0 = new_val(Tbool, $1);
+ $0->val.bool = 1;
+ }$
+ | False ${
+ $0 = new_val(Tbool, $1);
+ $0->val.bool = 0;
+ }$
+ | NUMBER ${ {
+ char tail[3];
+ $0 = new_val(Tnum, $1);
+ if (number_parse($0->val.num, tail, $1.txt) == 0)
+ mpq_init($0->val.num); // UNTESTED
+ if (tail[0])
+ tok_err(c, "error: unsupported number suffix",
+ &$1);
+ } }$
+ | STRING ${ {
+ char tail[3];
+ $0 = new_val(Tstr, $1);
+ string_parse(&$1, '\\', &$0->val.str, tail);
+ if (tail[0])
+ tok_err(c, "error: unsupported string suffix",
+ &$1);
+ } }$
+ | MULTI_STRING ${ {
+ char tail[3];
+ $0 = new_val(Tstr, $1);
+ string_parse(&$1, '\\', &$0->val.str, tail);
+ if (tail[0])
+ tok_err(c, "error: unsupported string suffix",
+ &$1);
+ } }$
+
+###### print exec cases
+ case Xval:
+ {
+ struct val *v = cast(val, e);
+ if (v->vtype == Tstr)
+ printf("\"");
+ print_value(v->vtype, &v->val, stdout);
+ if (v->vtype == Tstr)
+ printf("\"");
+ break;
+ }
+
+###### propagate exec cases
+ case Xval:
+ {
+ struct val *val = cast(val, prog);
+ if (!type_compat(type, val->vtype, rules))
+ type_err(c, "error: expected %1%r found %2",
+ prog, type, rules, val->vtype);
+ return val->vtype;
+ }
+
+###### interp exec cases
+ case Xval:
+ rvtype = cast(val, e)->vtype;
+ dup_value(rvtype, &cast(val, e)->val, &rv);
+ break;
+
+###### ast functions
+ static void free_val(struct val *v)
+ {
+ if (v)
+ free_value(v->vtype, &v->val);
+ free(v);
+ }
+
+###### free exec cases
+ case Xval: free_val(cast(val, e)); break;
+
+###### ast functions
+ // Move all nodes from 'b' to 'rv', reversing their order.
+ // In 'b' 'left' is a list, and 'right' is the last node.
+ // In 'rv', left' is the first node and 'right' is a list.
+ static struct binode *reorder_bilist(struct binode *b)
+ {
+ struct binode *rv = NULL;
+
+ while (b) {
+ struct exec *t = b->right;
+ b->right = rv;
+ rv = b;
+ if (b->left)
+ b = cast(binode, b->left);
+ else
+ b = NULL;
+ rv->left = t;
+ }
+ return rv;
+ }
+
+### Variables
+
+Variables are scoped named values. We store the names in a linked list
+of "bindings" sorted in lexical order, and use sequential search and
+insertion sort.
+
+###### ast
+
+ struct binding {
+ struct text name;
+ struct binding *next; // in lexical order
+ ## binding fields
+ };
+
+This linked list is stored in the parse context so that "reduce"
+functions can find or add variables, and so the analysis phase can
+ensure that every variable gets a type.
+
+###### parse context
+
+ struct binding *varlist; // In lexical order
+
+###### ast functions
+
+ static struct binding *find_binding(struct parse_context *c, struct text s)
+ {
+ struct binding **l = &c->varlist;
+ struct binding *n;
+ int cmp = 1;
+
+ while (*l &&
+ (cmp = text_cmp((*l)->name, s)) < 0)
+ l = & (*l)->next;
+ if (cmp == 0)
+ return *l;
+ n = calloc(1, sizeof(*n));
+ n->name = s;
+ n->next = *l;
+ *l = n;
+ return n;
+ }
+
+Each name can be linked to multiple variables defined in different
+scopes. Each scope starts where the name is declared and continues
+until the end of the containing code block. Scopes of a given name
+cannot nest, so a declaration while a name is in-scope is an error.
+
+###### binding fields
+ struct variable *var;
+
+###### ast
+ struct variable {
+ struct variable *previous;
+ struct type *type;
+ struct binding *name;
+ struct exec *where_decl;// where name was declared
+ struct exec *where_set; // where type was set
+ ## variable fields
+ };
+
+When a scope closes, the values of the variables might need to be freed.
+This happens in the context of some `struct exec` and each `exec` will
+need to know which variables need to be freed when it completes.
+
+####### exec fields
+ struct variable *to_free;
+
+####### variable fields
+ struct exec *cleanup_exec;
+ struct variable *next_free;
+
+####### interp exec cleanup
+ {
+ struct variable *v;
+ for (v = e->to_free; v; v = v->next_free) {
+ struct value *val = var_value(c, v);
+ free_value(v->type, val);
+ }
+ }
+
+###### ast functions
+ static void variable_unlink_exec(struct variable *v)
+ {
+ struct variable **vp;
+ if (!v->cleanup_exec)
+ return;
+ for (vp = &v->cleanup_exec->to_free;
+ *vp; vp = &(*vp)->next_free) {
+ if (*vp != v)
+ continue;
+ *vp = v->next_free;
+ v->cleanup_exec = NULL;
+ break;
+ }
+ }
+
+While the naming seems strange, we include local constants in the
+definition of variables. A name declared `var := value` can
+subsequently be changed, but a name declared `var ::= value` cannot -
+it is constant
+
+###### variable fields
+ int constant;
+
+Scopes in parallel branches can be partially merged. More
+specifically, if a given name is declared in both branches of an
+if/else then its scope is a candidate for merging. Similarly if
+every branch of an exhaustive switch (e.g. has an "else" clause)
+declares a given name, then the scopes from the branches are
+candidates for merging.
+
+Note that names declared inside a loop (which is only parallel to
+itself) are never visible after the loop. Similarly names defined in
+scopes which are not parallel, such as those started by `for` and
+`switch`, are never visible after the scope. Only variables defined in
+both `then` and `else` (including the implicit then after an `if`, and
+excluding `then` used with `for`) and in all `case`s and `else` of a
+`switch` or `while` can be visible beyond the `if`/`switch`/`while`.
+
+Labels, which are a bit like variables, follow different rules.
+Labels are not explicitly declared, but if an undeclared name appears
+in a context where a label is legal, that effectively declares the
+name as a label. The declaration remains in force (or in scope) at
+least to the end of the immediately containing block and conditionally
+in any larger containing block which does not declare the name in some
+other way. Importantly, the conditional scope extension happens even
+if the label is only used in one parallel branch of a conditional --
+when used in one branch it is treated as having been declared in all
+branches.
+
+Merge candidates are tentatively visible beyond the end of the
+branching statement which creates them. If the name is used, the
+merge is affirmed and they become a single variable visible at the
+outer layer. If not - if it is redeclared first - the merge lapses.
+
+To track scopes we have an extra stack, implemented as a linked list,
+which roughly parallels the parse stack and which is used exclusively
+for scoping. When a new scope is opened, a new frame is pushed and
+the child-count of the parent frame is incremented. This child-count
+is used to distinguish between the first of a set of parallel scopes,
+in which declared variables must not be in scope, and subsequent
+branches, whether they may already be conditionally scoped.
+
+We need a total ordering of scopes so we can easily compare to variables
+to see if they are concurrently in scope. To achieve this we record a
+`scope_count` which is actually a count of both beginnings and endings
+of scopes. Then each variable has a record of the scope count where it
+enters scope, and where it leaves.
+
+To push a new frame *before* any code in the frame is parsed, we need a
+grammar reduction. This is most easily achieved with a grammar
+element which derives the empty string, and creates the new scope when
+it is recognised. This can be placed, for example, between a keyword
+like "if" and the code following it.
+
+###### ast
+ struct scope {
+ struct scope *parent;
+ int child_count;
+ };
+
+###### parse context
+ int scope_depth;
+ int scope_count;
+ struct scope *scope_stack;
+
+###### variable fields
+ int scope_start, scope_end;
+
+###### ast functions
+ static void scope_pop(struct parse_context *c)
+ {
+ struct scope *s = c->scope_stack;
+
+ c->scope_stack = s->parent;
+ free(s);
+ c->scope_depth -= 1;
+ c->scope_count += 1;
+ }
+
+ static void scope_push(struct parse_context *c)
+ {
+ struct scope *s = calloc(1, sizeof(*s));
+ if (c->scope_stack)
+ c->scope_stack->child_count += 1;
+ s->parent = c->scope_stack;
+ c->scope_stack = s;
+ c->scope_depth += 1;
+ c->scope_count += 1;
+ }
+
+###### Grammar
+
+ $void
+ OpenScope -> ${ scope_push(c); }$
+
+Each variable records a scope depth and is in one of four states:
+
+- "in scope". This is the case between the declaration of the
+ variable and the end of the containing block, and also between
+ the usage with affirms a merge and the end of that block.
+
+ The scope depth is not greater than the current parse context scope
+ nest depth. When the block of that depth closes, the state will
+ change. To achieve this, all "in scope" variables are linked
+ together as a stack in nesting order.
+
+- "pending". The "in scope" block has closed, but other parallel
+ scopes are still being processed. So far, every parallel block at
+ the same level that has closed has declared the name.
+
+ The scope depth is the depth of the last parallel block that
+ enclosed the declaration, and that has closed.
+
+- "conditionally in scope". The "in scope" block and all parallel
+ scopes have closed, and no further mention of the name has been seen.
+ This state includes a secondary nest depth (`min_depth`) which records
+ the outermost scope seen since the variable became conditionally in
+ scope. If a use of the name is found, the variable becomes "in scope"
+ and that secondary depth becomes the recorded scope depth. If the
+ name is declared as a new variable, the old variable becomes "out of
+ scope" and the recorded scope depth stays unchanged.
+
+- "out of scope". The variable is neither in scope nor conditionally
+ in scope. It is permanently out of scope now and can be removed from
+ the "in scope" stack. When a variable becomes out-of-scope it is
+ moved to a separate list (`out_scope`) of variables which have fully
+ known scope. This will be used at the end of each function to assign
+ each variable a place in the stack frame.
+
+###### variable fields
+ int depth, min_depth;
+ enum { OutScope, PendingScope, CondScope, InScope } scope;
+ struct variable *in_scope;
+
+###### parse context
+
+ struct variable *in_scope;
+ struct variable *out_scope;
+
+All variables with the same name are linked together using the
+'previous' link. Those variable that have been affirmatively merged all
+have a 'merged' pointer that points to one primary variable - the most
+recently declared instance. When merging variables, we need to also
+adjust the 'merged' pointer on any other variables that had previously
+been merged with the one that will no longer be primary.
+
+A variable that is no longer the most recent instance of a name may
+still have "pending" scope, if it might still be merged with most
+recent instance. These variables don't really belong in the
+"in_scope" list, but are not immediately removed when a new instance
+is found. Instead, they are detected and ignored when considering the
+list of in_scope names.
+
+The storage of the value of a variable will be described later. For now
+we just need to know that when a variable goes out of scope, it might
+need to be freed. For this we need to be able to find it, so assume that
+`var_value()` will provide that.
+
+###### variable fields
+ struct variable *merged;
+
+###### ast functions
+
+ static void variable_merge(struct variable *primary, struct variable *secondary)
+ {
+ struct variable *v;
+
+ primary = primary->merged;
+
+ for (v = primary->previous; v; v=v->previous)
+ if (v == secondary || v == secondary->merged ||
+ v->merged == secondary ||
+ v->merged == secondary->merged) {
+ v->scope = OutScope;
+ v->merged = primary;
+ if (v->scope_start < primary->scope_start)
+ primary->scope_start = v->scope_start;
+ if (v->scope_end > primary->scope_end)
+ primary->scope_end = v->scope_end; // NOTEST
+ variable_unlink_exec(v);
+ }
+ }
+
+###### forward decls
+ static struct value *var_value(struct parse_context *c, struct variable *v);
+
+###### free global vars
+
+ while (context.varlist) {
+ struct binding *b = context.varlist;
+ struct variable *v = b->var;
+ context.varlist = b->next;
+ free(b);
+ while (v) {
+ struct variable *next = v->previous;
+
+ if (v->global) {
+ free_value(v->type, var_value(&context, v));
+ if (v->depth == 0)
+ // This is a global constant
+ free_exec(v->where_decl);
+ }
+ free(v);
+ v = next;
+ }
+ }
+
+#### Manipulating Bindings
+
+When a name is conditionally visible, a new declaration discards the old
+binding - the condition lapses. Similarly when we reach the end of a
+function (outermost non-global scope) any conditional scope must lapse.
+Conversely a usage of the name affirms the visibility and extends it to
+the end of the containing block - i.e. the block that contains both the
+original declaration and the latest usage. This is determined from
+`min_depth`. When a conditionally visible variable gets affirmed like
+this, it is also merged with other conditionally visible variables with
+the same name.
+
+When we parse a variable declaration we either report an error if the
+name is currently bound, or create a new variable at the current nest