+#### Base Types
+
+Values of the base types can be numbers, which we represent as
+multi-precision fractions, strings, Booleans and labels. When
+analysing the program we also need to allow for places where no value
+is meaningful (type `Tnone`) and where we don't know what type to
+expect yet (type is `NULL`).
+
+Values are never shared, they are always copied when used, and freed
+when no longer needed.
+
+When propagating type information around the program, we need to
+determine if two types are compatible, where type `NULL` is compatible
+with anything. There are two special cases with type compatibility,
+both related to the Conditional Statement which will be described
+later. In some cases a Boolean can be accepted as well as some other
+primary type, and in others any type is acceptable except a label (`Vlabel`).
+A separate function encoding these cases will simplify some code later.
+
+###### type functions
+
+ int (*compat)(struct type *this, struct type *other);
+
+###### ast functions
+
+ static int type_compat(struct type *require, struct type *have, int rules)
+ {
+ if ((rules & Rboolok) && have == Tbool)
+ return 1; // NOTEST
+ if ((rules & Rnolabel) && have == Tlabel)
+ return 0; // NOTEST
+ if (!require || !have)
+ return 1;
+
+ if (require->compat)
+ return require->compat(require, have);
+
+ return require == have;
+ }
+
+###### includes
+ #include <gmp.h>
+ #include "parse_string.h"
+ #include "parse_number.h"
+
+###### libs
+ myLDLIBS := libnumber.o libstring.o -lgmp
+ LDLIBS := $(filter-out $(myLDLIBS),$(LDLIBS)) $(myLDLIBS)
+
+###### type union fields
+ enum vtype {Vnone, Vstr, Vnum, Vbool, Vlabel} vtype;
+
+###### value union fields
+ struct text str;
+ mpq_t num;
+ unsigned char bool;
+ void *label;
+
+###### ast functions
+ static void _free_value(struct type *type, struct value *v)
+ {
+ if (!v)
+ return; // NOTEST
+ switch (type->vtype) {
+ case Vnone: break;
+ case Vstr: free(v->str.txt); break;
+ case Vnum: mpq_clear(v->num); break;
+ case Vlabel:
+ case Vbool: break;
+ }
+ }
+
+###### value functions
+
+ static void _val_init(struct type *type, struct value *val)
+ {
+ switch(type->vtype) {
+ case Vnone: // NOTEST
+ break; // NOTEST
+ case Vnum:
+ mpq_init(val->num); break;
+ case Vstr:
+ val->str.txt = malloc(1);
+ val->str.len = 0;
+ break;
+ case Vbool:
+ val->bool = 0;
+ break;
+ case Vlabel:
+ val->label = NULL;
+ break;
+ }
+ }
+
+ static void _dup_value(struct type *type,
+ struct value *vold, struct value *vnew)
+ {
+ switch (type->vtype) {
+ case Vnone: // NOTEST
+ break; // NOTEST
+ case Vlabel:
+ vnew->label = vold->label;
+ break;
+ case Vbool:
+ vnew->bool = vold->bool;
+ break;
+ case Vnum:
+ mpq_init(vnew->num);
+ mpq_set(vnew->num, vold->num);
+ break;
+ case Vstr:
+ vnew->str.len = vold->str.len;
+ vnew->str.txt = malloc(vnew->str.len);
+ memcpy(vnew->str.txt, vold->str.txt, vnew->str.len);
+ break;
+ }
+ }
+
+ static int _value_cmp(struct type *tl, struct type *tr,
+ struct value *left, struct value *right)
+ {
+ int cmp;
+ if (tl != tr)
+ return tl - tr; // NOTEST
+ switch (tl->vtype) {
+ case Vlabel: cmp = left->label == right->label ? 0 : 1; break;
+ case Vnum: cmp = mpq_cmp(left->num, right->num); break;
+ case Vstr: cmp = text_cmp(left->str, right->str); break;
+ case Vbool: cmp = left->bool - right->bool; break;
+ case Vnone: cmp = 0; // NOTEST
+ }
+ return cmp;
+ }
+
+ 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, "%.10Fg", 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("\"");
+ // FIXME how to ensure numbers have same precision.
+ 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;