Allow C-style for loops

4 files changed, 199 insertions, 47 deletions

diff --git a/chapter17/README.md b/chapter17/README.md
index 95cc397e..b9733873 100644
--- a/chapter17/README.md
+++ b/chapter17/README.md
@@ -108,21 +108,39 @@ Allow `pred ? e_true : e_false`.  Also allow `pred ? e_true`, where the false re
 is the zero type version of the true result.
 
 
+## For Loops
 
+Allow C/C++ style `for` loops:
+
+`for( init; test; next ) body`
+
+```cpp
+int sum=0;
+for( int i=0; i<arg; i++ )
+    sum = sum + i;
+return sum;
+```
+
+Any of `init`, `test` and `next` can be empty.
+`init` allows for declaration of a new variable, with scope limited to the `for` expression.
+
+```cpp
+int sum=0;
+for( int i=0; i<arg; i++ )
+    sum = sum + i;
+return sum;
+```
 
 
 
 
-C++-style for-loop
 for-interator
-trinary
 switch
 
 
 
 
 
-
 # Chapter 18: Functions
 
 Some thinking on function syntax:
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/Parser.java b/chapter17/src/main/java/com/seaofnodes/simple/Parser.java
index 799e0629..a4f7462e 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/Parser.java
@@ -212,6 +212,7 @@ public class Parser {
         else if (match ("{")       ) return require(parseBlock(false),"}");
         else if (matchx("if")      ) return parseIf();
         else if (matchx("while")   ) return parseWhile();
+        else if (matchx("for")     ) return parseFor();
         else if (matchx("break")   ) return parseBreak();
         else if (matchx("continue")) return parseContinue();
         else if (matchx("struct")  ) return parseStruct();
@@ -221,6 +222,7 @@ public class Parser {
         // to ambiguity
         else return parseExpressionStatement();
     }
+
     /**
      * Parses a while statement
      *
@@ -230,11 +232,40 @@ public class Parser {
      * @return a {@link Node}, never {@code null}
      */
     private Node parseWhile() {
+        require("(");
+        return parseLooping(false);
+    }
 
-        var savedContinueScope = _continueScope;
-        var savedBreakScope    = _breakScope;
 
+    /**
+     * Parses a for statement
+     *
+     * <pre>
+     *     for( var x=init; test; incr ) body
+     * </pre>
+     * @return a {@link Node}, never {@code null}
+     */
+    private Node parseFor() {
+        // {   var x=init,y=init,...;
+        //     while( pred ) {
+        //         body;
+        //         next;
+        //     }
+        // }
         require("(");
+        _scope.push();          // Scope for the index variables
+        if( !match(";") )       // Can be empty init "for(;test;next) body"
+            parseExpressionStatement(); // Non-empty init
+        Node rez = parseLooping(true);
+        _scope.pop();           // Exit index variable scope
+        return rez;
+    }
+
+    // Shared by `for` and `while`
+    private Node parseLooping( boolean doFor ) {
+
+        var savedContinueScope = _continueScope;
+        var savedBreakScope    = _breakScope;
 
         // Loop region has two control inputs, the first is the entry
         // point, and second is back edge that is set after loop is parsed
@@ -255,13 +286,25 @@ public class Parser {
         _xScopes.push(_scope = _scope.dup(true)); // The true argument triggers creating phis
 
         // Parse predicate
-        var pred = require(parseExpression(), ")");
+        var pred = peek(';') ? con(1) : parseExpression();
+        require( doFor ? ";" : ")" );
+
         // IfNode takes current control and predicate
-        Node ifNode = new IfNode(ctrl(), pred).peephole();
+        Node ifNode = new IfNode(ctrl(), pred.keep()).peephole();
         // Setup projection nodes
         Node ifT = new CProjNode(ifNode.  keep(), 0, "True" ).peephole().keep();
         Node ifF = new CProjNode(ifNode.unkeep(), 1, "False").peephole();
 
+        // for( ;;next ) body
+        int nextPos = -1, nextEnd = -1;
+        if( doFor ) {
+            // Skip the next expression and parse it later
+            nextPos = pos();
+            skipAsgn();
+            nextEnd = pos();
+            require(")");
+        }
+
         // Clone the body Scope to create the break/exit Scope which accounts for any
         // side effects in the predicate.  The break/exit Scope will be the final
         // scope after the loop, and its control input is the False branch of
@@ -276,7 +319,7 @@ public class Parser {
         // Parse the true side, which corresponds to loop body
         // Our current scope is the body Scope
         ctrl(ifT.unkeep());     // set ctrl token to ifTrue projection
-        _scope.addGuards(ifT,pred,false); // Up-cast predicate
+        _scope.addGuards(ifT,pred.unkeep(),false); // Up-cast predicate
         parseStatement();       // Parse loop body
         _scope.removeGuards(ifT);
 
@@ -287,6 +330,15 @@ public class Parser {
             _scope = _continueScope;
         }
 
+        // Now append the next code onto the body code
+        if( doFor ) {
+            int old = pos(nextPos);
+            if( !peek(')') )
+              parseAsgn(null,false);
+            assert pos() == nextEnd;
+            pos(old);
+        }
+
         // The true branch loops back, so whatever is current _scope.ctrl gets
         // added to head loop as input.  endLoop() updates the head scope, and
         // goes through all the phis that were created earlier.  For each phi,
@@ -342,6 +394,26 @@ public class Parser {
         return _breakScope;
     }
 
+    // Look for an unbalanced `)`, skipping balanced
+    private void skipAsgn() {
+        int paren=0;
+        while( true )
+            // Next X char handles skipping complex comments
+            switch( _lexer.nextXChar() ) {
+            case Character.MAX_VALUE:
+                throw Utils.TODO();
+            case ')':
+                if( --paren<0 ) {
+                    pos(pos()-1); // Leave the `)` behind
+                    return;
+                }
+                break;
+            case '(': paren ++; break;
+            default: break;
+            }
+    }
+
+
     /**
      * Parses a statement
      *
@@ -443,13 +515,13 @@ public class Parser {
     // t==type &&  expr ==>> declaratn:  final=inCon && noBang, expr=parse() ; t:=type;
     private Node parseAsgn(Type t, boolean hasBang) {
         boolean isDecl = t!=null;
-        int old = _lexer._position;
+        int old = pos();
         String name = requireId();
 
         boolean hasType = t!=null && t!=Type.TOP && t!=Type.BOTTOM; // User written type
         boolean hasExpr = !(peek(';') || peek(','));   // Expression follows
         if( hasExpr && !match("=") )                   // Something else
-            { _lexer._position = old;  return null; }
+            { pos(old);  return parseExpression(); }
         if( !hasExpr && t==Type.BOTTOM )  throw errorSyntax("expression");
         Node expr = hasExpr ? parseExpression() : con(t.makeInit());
         boolean xfinal = t==Type.TOP || (hasType && hasExpr && !hasBang && _scope.inCon());
@@ -523,10 +595,8 @@ public class Parser {
                 n = parseFinal(t);
 
             // Parse "asgn;" which is just "name = expr;"
-        } else if( ( n = parseAsgn(null,false)) == null ) {
-            // Something else
-            n = parseExpression();
-        }
+        } else
+            n = parseAsgn(null,false);
         return require(n,";");
     }
 
@@ -577,14 +647,14 @@ public class Parser {
     // types (which ARE valid here) from local vars in an (optional) forward
     // ref type position.
     private Type type() {
-        int old1 = _lexer._position;
+        int old1 = pos();
         String tname = _lexer.matchId();
         if( tname==null ) return null;
         // Convert the type name to a type.
         Type t0 = TYPES.get(tname);
         // No new types as keywords
         if( t0 == null && KEYWORDS.contains(tname) )
-          { _lexer._position = old1; return null; }
+            { pos(old1); return null; }
         Type t1 = t0 == null ? TypeMemPtr.make(TypeStruct.makeFRef(tname)) : t0; // Null: assume a forward ref type
         // Nest arrays and '?' as needed
         while( true ) {
@@ -607,11 +677,11 @@ public class Parser {
         if( t0 != null ) return t1;
         // Check valid forward ref, after parsing all the type extra bits.
         // Cannot check earlier, because cannot find required 'id' until after "[]?" syntax
-        int old2 = _lexer._position;
+        int old2 = pos();
         String id = _lexer.matchId();
-        _lexer._position = old2; // Reset lexer to reparse
+        pos(old2);              // Reset lexer to reparse
         if( id==null ) {
-            _lexer._position = old1; // Reset lexer to reparse
+            pos(old1);          // Reset lexer to reparse
             return null;        // Not a type
         }
         // Yes a forward ref, so declare it
@@ -1040,6 +1110,13 @@ public class Parser {
     private boolean peek(char ch) { return _lexer.peek(ch); }
     private boolean peekIsId() { return _lexer.peekIsId(); }
 
+    private int pos() { return _lexer._position; }
+    private int pos(int pos) {
+        int old = _lexer._position;
+        _lexer._position = pos;
+        return old;
+    }
+
     // Require and return an identifier
     private String requireId() {
         String id = _lexer.matchId();
@@ -1134,6 +1211,8 @@ public class Parser {
             }
         }
 
+        // Next non-white-space character, or EOF
+        public char nextXChar() { skipWhiteSpace(); return nextChar(); }
 
         // Return true, if we find "syntax" after skipping white space; also
         // then advance the cursor past syntax.
diff --git a/chapter17/src/test/java/com/seaofnodes/simple/BrainFuckTest.java b/chapter17/src/test/java/com/seaofnodes/simple/BrainFuckTest.java
index de6852c7..28c3477c 100644
--- a/chapter17/src/test/java/com/seaofnodes/simple/BrainFuckTest.java
+++ b/chapter17/src/test/java/com/seaofnodes/simple/BrainFuckTest.java
@@ -23,11 +23,11 @@ public class BrainFuckTest {
 
         Parser parser = new Parser(
                 encoded + """
-var pc = 0, d = 0;
+var d = 0;
 u8[] !output = new u8[0];
 val data = new u8[100];
 
-while (pc < program#) {
+for( int pc = 0; pc < program#; pc++ ) {
     var command = program[pc];
     if (command == 62) {
         d++;
@@ -40,16 +40,14 @@ while (pc < program#) {
     } else if (command == 46) {
         var old = output;
         output = new u8[output# + 1];
-        var i = 0;
-        while (i < old#)
-            output[i] = old[i++];
-        output[i] = data[d];
+        for( var i = 0; i < old#; i++ )
+            output[i] = old[i];
+        output[old#] = data[d];
     } else if (command == 44) {
         data[d] = 42;
     } else if (command == 91) {
         if (data[d] == 0) {
-            var d = 1;
-            while (d > 0) {
+            for( var d = 1; d > 0; ) {
                 pc++;
                 command = program[pc];
                 if (command == 91) d++;
@@ -58,8 +56,7 @@ while (pc < program#) {
         }
     } else if (command == 93) {
         if (data[d]) {
-            var d = 1;
-            while (d > 0) {
+            for( var d = 1; d > 0; ) {
                 pc--;
                 command = program[pc];
                 if (command == 93) d++;
@@ -67,7 +64,6 @@ while (pc < program#) {
             }
         }
     }
-    pc++;
 }
 return output;
                 """);
diff --git a/chapter17/src/test/java/com/seaofnodes/simple/Chapter17Test.java b/chapter17/src/test/java/com/seaofnodes/simple/Chapter17Test.java
index fe275ee9..d39cee2d 100644
--- a/chapter17/src/test/java/com/seaofnodes/simple/Chapter17Test.java
+++ b/chapter17/src/test/java/com/seaofnodes/simple/Chapter17Test.java
@@ -2,7 +2,6 @@ package com.seaofnodes.simple;
 
 import com.seaofnodes.simple.evaluator.Evaluator;
 import com.seaofnodes.simple.node.StopNode;
-import org.junit.Ignore;
 import org.junit.Test;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.fail;
@@ -162,6 +161,72 @@ return b ? b.next ? b.next.x : b.x; // parses "b ? (b.next ? b.next.x : b.x) : 0
     }
 
 
+    @Test
+    public void testFor0() {
+        Parser parser = new Parser("""
+int sum=0;
+for( int i=0; i<arg; i++ )
+    sum = sum + i;
+return sum;
+""");
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return Phi(Loop,0,(Phi_sum+Phi(Loop,0,(Phi_i+1))));", stop.toString());
+        assertEquals(3L, Evaluator.evaluate(stop, 3));
+        assertEquals(45L, Evaluator.evaluate(stop, 10));
+    }
+    @Test
+    public void testFor1() {
+        Parser parser = new Parser("""
+int sum=0, i=0;
+for( ; i<arg; i++ )
+    sum = sum + i;
+return sum;
+""");
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return Phi(Loop,0,(Phi_sum+Phi(Loop,0,(Phi_i+1))));", stop.toString());
+        assertEquals(3L, Evaluator.evaluate(stop, 3));
+        assertEquals(45L, Evaluator.evaluate(stop, 10));
+    }
+    @Test
+    public void testFor2() {
+        Parser parser = new Parser("""
+int sum=0;
+for( int i=0; ; i++ ) {
+    if( i>=arg ) break;
+    sum = sum + i;
+}
+return sum;
+""");
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return Phi(Loop,0,(Phi_sum+Phi(Loop,0,(Phi_i+1))));", stop.toString());
+        assertEquals(3L, Evaluator.evaluate(stop, 3));
+        assertEquals(45L, Evaluator.evaluate(stop, 10));
+    }
+    @Test
+    public void testFor3() {
+        Parser parser = new Parser("""
+int sum=0;
+for( int i=0; i<arg; )
+    sum = sum + i++;
+return sum;
+""");
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return Phi(Loop,0,(Phi_sum+Phi(Loop,0,(Phi_i+1))));", stop.toString());
+        assertEquals(3L, Evaluator.evaluate(stop, 3));
+        assertEquals(45L, Evaluator.evaluate(stop, 10));
+    }
+    @Test
+    public void testFor4() {
+        Parser parser = new Parser("""
+int sum=0;
+for( int i=0; i<arg; i++ )
+    sum = sum + i;
+return i;
+""");
+        try { parser.parse().iterate(); fail(); }
+        catch( Exception e ) { assertEquals("Undefined name 'i'",e.getMessage()); }
+    }
+
 
     @Test
     public void testLinkedList2() {
@@ -171,10 +236,8 @@ LLI? head = null;
 while( arg-- )
     head = new LLI { next=head; i=arg; };
 int sum=0;
-while( head ) {
+for( ; head; head = head.next )
     sum = sum + head.i;
-    head = head.next;
-}
 return sum;
 """);
         StopNode stop = parser.parse().iterate();
@@ -187,29 +250,25 @@ return sum;
         Parser parser = new Parser(
 """
 val ary = new bool[arg], primes = new int[arg];
-var nprimes=0, p=2;
+var nprimes=0, p=0;
 // Find primes while p^2 < arg
-while( p*p < arg ) {
+for( p=2; p*p < arg; p++ ) {
     // skip marked non-primes
     while( ary[p] ) p++;
     // p is now a prime
     primes[nprimes++] = p;
     // Mark out the rest non-primes
-    int i = p + p;
-    while( i < ary# ) {
+    for( int i = p + p; i < ary#; i = i + p )
         ary[i] = true;
-        i = i + p;
-    }
-    p++;
 }
 // Now just collect the remaining primes, no more marking
-while( p++ < arg )
-    if( !ary[p-1] )
-        primes[nprimes++] = p-1;
+for( ; p < arg; p++ )
+    if( !ary[p] )
+        primes[nprimes++] = p;
 // Copy/shrink the result array
-var rez = new int[nprimes], j = 0;
-while( j < nprimes )
-    rez[j] = primes[j++];
+var rez = new int[nprimes];
+for( int j=0; j<nprimes; j++ )
+    rez[j] = primes[j];
 return rez;
 """);
         StopNode stop = parser.parse().iterate();