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 <neil@brown.name>

diff --git a/csrc/oceani.mdc b/csrc/oceani.mdc
index 460e75ed103b1648c0c3947432cec801be07a1fa..9abd338e0d92db27cc181e280788f54dd179dde8 100644 (file)
--- 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.
 
 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.
 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;
                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.
 
 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
 
 
 ###### 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;
 
        {
                enum vtype t;
 


@@ -1191,7 +1199,7 @@ an executable.
                case Xval:
                {
                        struct val *val = cast(val, prog);
                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;
                }
                                *ok = 0;
                        return val->val.vtype;
                }


@@ -1308,7 +1316,7 @@ link to find the primary instance.
                        }
                        return type;
                }
                        }
                        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;
                        *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 */
        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;
                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 */
        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)
                if (t > Vunknown)

-                       propagate_types(b->right, t, ok);
+                       propagate_types(b->right, ok, t, 0);

                else {
                else {

-                       t = propagate_types(b->right, Vnolabel, ok);
+                       t = propagate_types(b->right, ok, Vnolabel, 0);

                        if (t > Vunknown)
                        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;
 
                        *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 */
        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 */
                        *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:
                        *ok = 0;
                return Vstr;
 
        case Bracket:

-               return propagate_types(b->right, type, ok);
+               return propagate_types(b->right, ok, type, 0);

 
 ###### interp binode cases
 
 
 ###### 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
                 * 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)) {
                 */
                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;
                        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 */
 
        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
                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 */
        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)
                if (t > Vunknown)

-                       propagate_types(b->right, t, ok);
+                       propagate_types(b->right, ok, t, 0);

                else {
                else {

-                       t = propagate_types(b->right, Vnolabel, ok);
+                       t = propagate_types(b->right, ok, Vnolabel, 0);

                        if (t > Vunknown)
                        if (t > Vunknown)

-                               t = propagate_types(b->left, t, ok);
+                               t = propagate_types(b->left, ok, t, 0);

                }
                return Vnone;
 
                }
                return Vnone;
 


@@ -2080,7 +2091,7 @@ function.
 
        case Use:
                /* result matches value */
 
        case Use:
                /* result matches value */

-               return propagate_types(b->right, type, ok);
+               return propagate_types(b->right, ok, type, 0);

 
 ###### interp binode cases
 
 
 ###### interp binode cases
 


@@ -2090,16 +2101,28 @@ function.
 
 ### The Conditional Statement
 
 
 ### 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
 
 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
 
 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.
 
 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.
 
 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
        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;
 
                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;
                        *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;
                        *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)
                if (cs->casepart == NULL)

-                       propagate_types(cs->condpart, Vbool, ok);
+                       propagate_types(cs->condpart, ok, Vbool, 0);

                else {
                else {

+                       /* Condpart must match case values, with bool permitted */

                        t = Vunknown;
                        for (c = cs->casepart;
                             c && (t == Vunknown); c = c->next)
                        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)
                        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)
                        // 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;
                for (c = cs->casepart;

-                    c && (type == Vunknown || type == Vnone);
+                    c && type == Vunknown;

                     c = c->next)
                     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)
                        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;
                        return type;
                } else
                        return Vunknown;


@@ -2598,7 +2646,7 @@ analysis is a bit more interesting at this level.
 
                do {
                        ok = 1;
 
                do {
                        ok = 1;

-                       propagate_types(b->right, Vnone, &ok);
+                       propagate_types(b->right, &ok, Vnone, 0);

                } while (ok == 2);
                if (!ok)
                        return 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;
                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 */
                } 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;
        }
 
                return !!ok;
        }
 


@@ -2722,7 +2770,7 @@ Fibonacci, and performs a binary search for a number.
                                hi = mid
                        if hi - lo < 1:
                                use GiveUp
                                hi = mid
                        if hi - lo < 1:
                                use GiveUp

-
+                       use True

                do: pass
                case Found:
                        print "Yay, I found", target
                do: pass
                case Found:
                        print "Yay, I found", target