From ddff055f268cb0c10510155c0fbb600ee903e5da Mon Sep 17 00:00:00 2001 From: NeilBrown Date: Sat, 17 Feb 2018 12:01:08 +1100 Subject: [PATCH] oceani: fix type analysis for 'while' condition. The condition in a 'while' can always return Bool, or may return some other consistent type. This requires extra subtlety in analysis. Signed-off-by: NeilBrown --- csrc/oceani.mdc | 176 ++++++++++++++++++++++++++++++------------------ 1 file changed, 112 insertions(+), 64 deletions(-) diff --git a/csrc/oceani.mdc b/csrc/oceani.mdc index 460e75e..9abd338 100644 --- a/csrc/oceani.mdc +++ b/csrc/oceani.mdc @@ -290,6 +290,11 @@ These names are given a type of "label" and a unique value. This allows them to fill the role of a name in an enumerated type, which is useful for testing the `switch` statement. +As we will see, the condition part of a `while` statement can return +either a Boolean or some other type. This requires that the expect +type that gets passed around comprises a type (`enum vtype`) and a +flag to indicate that `Vbool` is also permitted. + As there are, as yet, no distinct types that are compatible, there isn't much subtlety in the analysis. When we hav distinct number types, this will become more interesting. @@ -364,8 +369,10 @@ to parse each type from a string. } } - static int vtype_compat(enum vtype require, enum vtype have) + static int vtype_compat(enum vtype require, enum vtype have, int bool_permitted) { + if (bool_permitted && have == Vbool) + return 1; switch (require) { case Vnolabel: return have != Vlabel; @@ -1057,16 +1064,17 @@ also want to know what sort of bracketing to use. As discussed, analysis involves propagating type requirements around the program and looking for errors. -So `propagate_types` is passed a type that the `exec` is expected to return, -and returns the type that it does return, either of which can be `Vunknown`. -An `ok` flag is passed by reference. It is set to `0` when an error is -found, and `2` when any change is made. If it remains unchanged at -`1`, then no more propagation is needed. +So `propagate_types` is passed an expected type (being a `vtype` +together with a `bool_permitted` flag) that the `exec` is expected to +return, and returns the type that it does return, either of which can +be `Vunknown`. An `ok` flag is passed by reference. It is set to `0` +when an error is found, and `2` when any change is made. If it +remains unchanged at `1`, then no more propagation is needed. ###### core functions - static enum vtype propagate_types(struct exec *prog, enum vtype type, - int *ok) + static enum vtype propagate_types(struct exec *prog, int *ok, + enum vtype type, int bool_permitted) { enum vtype t; @@ -1191,7 +1199,7 @@ an executable. case Xval: { struct val *val = cast(val, prog); - if (!vtype_compat(type, val->val.vtype)) + if (!vtype_compat(type, val->val.vtype, bool_permitted)) *ok = 0; return val->val.vtype; } @@ -1308,7 +1316,7 @@ link to find the primary instance. } return type; } - if (!vtype_compat(type, v->val.vtype)) + if (!vtype_compat(type, v->val.vtype, bool_permitted)) *ok = 0; if (type <= Vunknown) return v->val.vtype; @@ -1397,8 +1405,8 @@ and `BFact`s. case Or: case Not: /* both must be Vbool, result is Vbool */ - propagate_types(b->left, Vbool, ok); - propagate_types(b->right, Vbool, ok); + propagate_types(b->left, ok, Vbool, 0); + propagate_types(b->right, ok, Vbool, 0); if (type != Vbool && type > Vunknown) *ok = 0; return Vbool; @@ -1497,15 +1505,15 @@ expression operator. case Eql: case NEql: /* Both must match but not labels, result is Vbool */ - t = propagate_types(b->left, Vnolabel, ok); + t = propagate_types(b->left, ok, Vnolabel, 0); if (t > Vunknown) - propagate_types(b->right, t, ok); + propagate_types(b->right, ok, t, 0); else { - t = propagate_types(b->right, Vnolabel, ok); + t = propagate_types(b->right, ok, Vnolabel, 0); if (t > Vunknown) - t = propagate_types(b->left, t, ok); + t = propagate_types(b->left, ok, t, 0); } - if (!vtype_compat(type, Vbool)) + if (!vtype_compat(type, Vbool, 0)) *ok = 0; return Vbool; @@ -1639,22 +1647,22 @@ precedence is handled better I might be able to discard this. case Negate: /* as propagate_types ignores a NULL, * unary ops fit here too */ - propagate_types(b->left, Vnum, ok); - propagate_types(b->right, Vnum, ok); - if (!vtype_compat(type, Vnum)) + propagate_types(b->left, ok, Vnum, 0); + propagate_types(b->right, ok, Vnum, 0); + if (!vtype_compat(type, Vnum, 0)) *ok = 0; return Vnum; case Concat: /* both must be Vstr, result is Vstr */ - propagate_types(b->left, Vstr, ok); - propagate_types(b->right, Vstr, ok); - if (!vtype_compat(type, Vstr)) + propagate_types(b->left, ok, Vstr, 0); + propagate_types(b->right, ok, Vstr, 0); + if (!vtype_compat(type, Vstr, 0)) *ok = 0; return Vstr; case Bracket: - return propagate_types(b->right, type, ok); + return propagate_types(b->right, ok, type, 0); ###### interp binode cases @@ -1842,12 +1850,15 @@ list. * then all such must return same type. * As each statement may be Vnone or something else, * we must always pass Vunknown down, otherwise an incorrect - * error might occur. + * error might occur. We never return Vnone unless it is + * passed in. */ struct binode *e; for (e = b; e; e = cast(binode, e->right)) { - t = propagate_types(e->left, Vunknown, ok); + t = propagate_types(e->left, ok, Vunknown, bool_permitted); + if (bool_permitted && t == Vbool) + t = Vunknown; if (t != Vunknown && t != Vnone) { if (type == Vunknown) type = t; @@ -1935,8 +1946,8 @@ same solution. case Print: /* don't care but all must be consistent */ - propagate_types(b->left, Vnolabel, ok); - propagate_types(b->right, Vnolabel, ok); + propagate_types(b->left, ok, Vnolabel, 0); + propagate_types(b->right, ok, Vnolabel, 0); break; ###### interp binode cases @@ -2023,13 +2034,13 @@ it is declared, and error will be raised as the name is created as case Assign: case Declare: /* Both must match and not be labels, result is Vnone */ - t = propagate_types(b->left, Vnolabel, ok); + t = propagate_types(b->left, ok, Vnolabel, 0); if (t > Vunknown) - propagate_types(b->right, t, ok); + propagate_types(b->right, ok, t, 0); else { - t = propagate_types(b->right, Vnolabel, ok); + t = propagate_types(b->right, ok, Vnolabel, 0); if (t > Vunknown) - t = propagate_types(b->left, t, ok); + t = propagate_types(b->left, ok, t, 0); } return Vnone; @@ -2080,7 +2091,7 @@ function. case Use: /* result matches value */ - return propagate_types(b->right, type, ok); + return propagate_types(b->right, ok, type, 0); ###### interp binode cases @@ -2090,16 +2101,28 @@ function. ### The Conditional Statement -This is the biggy and currently the only complex statement. -This subsumes `if`, `while`, `do/while`, `switch`, and some parts of -`for`. It is comprised of a number of parts, all of which are -optional though set combinations apply. +This is the biggy and currently the only complex statement. This +subsumes `if`, `while`, `do/while`, `switch`, and some parts of `for`. +It is comprised of a number of parts, all of which are optional though +set combinations apply. Each part is (usually) a key word (`then` is +sometimes optional) followed by either an expression of a code block, +except the `casepart` which is a "key word and an expression" followed +by a code block. The code-block option is valid for all parts and, +where an expression is also allowed, the code block can use the `use` +statement to report a value. If the code block does no report a value +the effect is similar to reporting `False`. + +The `else` and `case` parts, as well as `then` when combined with +`if`, can contain a `use` statement which will apply to some +containing conditional statement. `for` parts, `do` parts and `then` +parts used with `for` can never contain a `use`, except in some +subordinate conditional statement. If there is a `forpart`, it is executed first, only once. If there is a `dopart`, then it is executed repeatedly providing always that the `condpart` or `cond`, if present, does not return a non-True value. `condpart` can fail to return any value if it simply executes -to completion. This is treated the same as returning True. +to completion. This is treated the same as returning `True`. If there is a `thenpart` it will be executed whenever the `condpart` or `cond` returns True (or does not return any value), but this will happen @@ -2126,6 +2149,17 @@ condition following "`while`" is in a scope the covers the body extension. Code following "`then`" (both looping and non-looping), "`else`" and "`case`" each get their own local scope. +The type requirements on the code block in a `whilepart` are quite +unusal. It is allowed to return a value of some identifiable type, in +which case the loop abort and an appropriate `casepart` is run, or it +can return a Boolean, in which case the loop either continues to the +`dopart` (on `True`) or aborts and runs the `elsepart` (on `False`). +This is different both from the `ifpart` code block which is expected to +return a Boolean, or the `switchpart` code block which is expected to +return the same type as the casepart values. The correct analysis of +the type of the `whilepart` code block is the reason for the +`bool_permitted` flag which is passed to `propagate_types()`. + The `cond_statement` cannot fit into a `binode` so a new `exec` is defined. @@ -2435,47 +2469,61 @@ defined. case Xcond_statement: { // forpart and dopart must return Vnone - // condpart must be bool or match casepart->values - // thenpart, elsepart, casepart->action must match - // or be Vnone + // thenpart must return Vnone if there is a dopart, + // otherwise it is like elsepart. + // condpart must: + // be bool if there is not casepart + // match casepart->values if there is a switchpart + // either be bool or match casepart->value if there + // is a whilepart + // elsepart, casepart->action must match there return type + // expected of this statement. struct cond_statement *cs = cast(cond_statement, prog); struct casepart *c; - t = propagate_types(cs->forpart, Vnone, ok); - if (!vtype_compat(Vnone, t)) + t = propagate_types(cs->forpart, ok, Vnone, 0); + if (!vtype_compat(Vnone, t, 0)) *ok = 0; - t = propagate_types(cs->dopart, Vnone, ok); - if (!vtype_compat(Vnone, t)) + t = propagate_types(cs->dopart, ok, Vnone, 0); + if (!vtype_compat(Vnone, t, 0)) *ok = 0; + if (cs->dopart) { + t = propagate_types(cs->thenpart, ok, Vnone, 0); + if (!vtype_compat(Vnone, t, 0)) + *ok = 0; + } if (cs->casepart == NULL) - propagate_types(cs->condpart, Vbool, ok); + propagate_types(cs->condpart, ok, Vbool, 0); else { + /* Condpart must match case values, with bool permitted */ t = Vunknown; for (c = cs->casepart; c && (t == Vunknown); c = c->next) - t = propagate_types(c->value, Vunknown, ok); + t = propagate_types(c->value, ok, Vunknown, 0); if (t == Vunknown && cs->condpart) - t = propagate_types(cs->condpart, Vunknown, ok); + t = propagate_types(cs->condpart, ok, Vunknown, 1); // Now we have a type (I hope) push it down if (t != Vunknown) { for (c = cs->casepart; c; c = c->next) - propagate_types(c->value, t, ok); - propagate_types(cs->condpart, t, ok); + propagate_types(c->value, ok, t, 0); + propagate_types(cs->condpart, ok, t, 1); } } - if (type == Vunknown || type == Vnone) - type = propagate_types(cs->thenpart, Vunknown, ok); - if (type == Vunknown || type == Vnone) - type = propagate_types(cs->elsepart, Vunknown, ok); + // (if)then, else, and case parts must return expected type. + if (!cs->dopart && type == Vunknown) + type = propagate_types(cs->thenpart, ok, Vunknown, bool_permitted); + if (type == Vunknown) + type = propagate_types(cs->elsepart, ok, Vunknown, bool_permitted); for (c = cs->casepart; - c && (type == Vunknown || type == Vnone); + c && type == Vunknown; c = c->next) - type = propagate_types(c->action, Vunknown, ok); - if (type != Vunknown && type != Vnone) { - propagate_types(cs->thenpart, type, ok); - propagate_types(cs->elsepart, type, ok); + type = propagate_types(c->action, ok, Vunknown, bool_permitted); + if (type > Vunknown) { + if (!cs->dopart) + propagate_types(cs->thenpart, ok, type, bool_permitted); + propagate_types(cs->elsepart, ok, type, bool_permitted); for (c = cs->casepart; c ; c = c->next) - propagate_types(c->action, type, ok); + propagate_types(c->action, ok, type, bool_permitted); return type; } else return Vunknown; @@ -2598,7 +2646,7 @@ analysis is a bit more interesting at this level. do { ok = 1; - propagate_types(b->right, Vnone, &ok); + propagate_types(b->right, &ok, Vnone, 0); } while (ok == 2); if (!ok) return 0; @@ -2611,13 +2659,13 @@ analysis is a bit more interesting at this level. b = cast(binode, prog); do { ok = 1; - propagate_types(b->right, Vnone, &ok); + propagate_types(b->right, &ok, Vnone, 0); } while (ok == 2); if (!ok) return 0; /* Make sure everything is still consistent */ - propagate_types(b->right, Vnone, &ok); + propagate_types(b->right, &ok, Vnone, 0); return !!ok; } @@ -2722,7 +2770,7 @@ Fibonacci, and performs a binary search for a number. hi = mid if hi - lo < 1: use GiveUp - + use True do: pass case Found: print "Yay, I found", target -- 2.43.0