Chapter 12: Floatslinear-chapter12

Co-authored-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: Robert Obkircher <robert.obkircher@gmail.com>

8 files changed, 175 insertions, 86 deletions

diff --git a/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/src/test/java/com/seaofnodes/simple/Chapter08Test.java
index 98fd181b..6aa74125 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter08Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter08Test.java
@@ -2,7 +2,6 @@ package com.seaofnodes.simple;
 
 import com.seaofnodes.simple.evaluator.Evaluator;
 import com.seaofnodes.simple.node.*;
-import com.seaofnodes.simple.type.TypeInteger;
 import org.junit.Assert;
 import org.junit.Test;
 
diff --git a/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/src/test/java/com/seaofnodes/simple/Chapter09Test.java
index 2abce3cb..64bbf245 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter09Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter09Test.java
@@ -5,7 +5,6 @@ import com.seaofnodes.simple.node.*;
 import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.type.TypeInteger;
 import org.junit.Assert;
-import org.junit.BeforeClass;
 import org.junit.Test;
 import org.junit.Ignore;
 
diff --git a/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/src/test/java/com/seaofnodes/simple/Chapter10Test.java
index 7371ff18..4a9521b9 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter10Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter10Test.java
@@ -1,7 +1,12 @@
 package com.seaofnodes.simple;
 
+import com.seaofnodes.simple.node.Node;
 import com.seaofnodes.simple.node.StopNode;
+import com.seaofnodes.simple.type.*;
 import org.junit.Test;
+
+import java.util.Arrays;
+
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.fail;
 
@@ -259,7 +264,6 @@ while(arg) {
     v0.v0 = arg;
     arg = arg-1;
     if (arg==5) ret=v0;
-
 }
 return ret;
 """);
diff --git a/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/src/test/java/com/seaofnodes/simple/Chapter11Test.java
index fdf56b56..a8b09226 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter11Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter11Test.java
@@ -292,7 +292,7 @@ else {
 }
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("Stop[ return 9; return 0; return 0; ]", stop.toString());
+        assertEquals("Stop[ return 9; return 0; return 0; return 0; return 0; ]", stop.toString());
     }
 
 
@@ -434,7 +434,7 @@ while(1)
   arg = arg+ptr.v;
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return 0;", stop.toString());
+        assertEquals("Stop[ return 0; return 0; ]", stop.toString());
     }
 
     @Test
@@ -496,7 +496,7 @@ return v;
     @Test
     public void testExample2() {
         Parser parser = new Parser(
-                                   """
+                """
 struct S { int f; }
 S v = new S;
 int i = arg;
@@ -507,7 +507,7 @@ while (arg > 0) {
     arg = arg - 1;
 }
 return v;
-""");
+                """);
         StopNode stop = parser.parse().iterate();
         //assertEquals("return new S;", stop.toString());
     }
@@ -528,38 +528,4 @@ return s.f;
         assertEquals(1L, Evaluator.evaluate(stop,  1));
         assertEquals(0L, Evaluator.evaluate(stop,  2));
     }
-
-    @Test
-    public void testScheduleUse() {
-        Parser parser = new Parser(
-"""
-int v0=0;
-while(0>=0) {
-    int v1=0;
-    v1=v0;
-    if(v1*0)
-        v0=-v1;
-}
-return 0;
-""");
-        StopNode stop = parser.parse().iterate();
-        assertEquals("return 0;", stop.toString());
-    }
-
-    @Test
-    public void testLoopCarriedDep() {
-        Parser parser = new Parser(
-"""
-int v0=0;
-{
-    int v1=0;
-    while(v1) {
-        v1=1+(v0!=0);
-        v0=v1/0;
-    }
-}
-""");
-        StopNode stop = parser.parse().iterate();
-        assertEquals("return 0;", stop.toString());
-    }
 }
diff --git a/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/src/test/java/com/seaofnodes/simple/Chapter12Test.java
new file mode 100644
index 00000000..af8fdfe9
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/Chapter12Test.java
@@ -0,0 +1,64 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.evaluator.Evaluator;
+import com.seaofnodes.simple.node.StopNode;
+import org.junit.Test;
+
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.fail;
+
+public class Chapter12Test {
+    @Test
+    public void testJig() {
+        Parser parser = new Parser(
+"""
+return 3.14;
+""");
+        StopNode stop = parser.parse(false).iterate(false);
+        assertEquals("return 3.14;", stop.toString());
+        assertEquals(3.14, Evaluator.evaluate(stop,  0));
+    }
+
+    @Test
+    public void testFloat() {
+        Parser parser = new Parser(
+"""
+return 3.14;
+""");
+        StopNode stop = parser.parse(false).iterate(false);
+        assertEquals("return 3.14;", stop.toString());
+        assertEquals(3.14, Evaluator.evaluate(stop,  0));
+    }
+
+    @Test
+    public void testSquareRoot() {
+        Parser parser = new Parser(
+"""
+flt guess = arg;
+while( 1 ) {
+    flt next = (arg/guess + guess)/2;
+    if( next == guess ) break;
+    guess = next;
+}
+return guess;
+""");
+        StopNode stop = parser.parse(false).iterate(false);
+        assertEquals("return Phi(Loop9,(flt)arg,(((ToFloat/Phi_guess)+Phi_guess)/2.0));", stop.toString());
+        assertEquals(3.0, Evaluator.evaluate(stop,  9));
+        assertEquals(1.414213562373095, Evaluator.evaluate(stop,  2));
+    }
+
+    @Test
+    public void testFPOps() {
+        Parser parser = new Parser(
+"""
+flt x = arg;
+return x+1==x;
+""");
+        StopNode stop = parser.parse(false).iterate(false);
+        assertEquals("return ((flt)arg==(ToFloat+1.0));", stop.toString());
+        assertEquals(0L, Evaluator.evaluate(stop, 1));
+    }
+
+}
diff --git a/src/test/java/com/seaofnodes/simple/SchedulerTest.java b/src/test/java/com/seaofnodes/simple/SchedulerTest.java
index 32c9c0c5..5def2782 100644
--- a/src/test/java/com/seaofnodes/simple/SchedulerTest.java
+++ b/src/test/java/com/seaofnodes/simple/SchedulerTest.java
@@ -46,7 +46,7 @@ S v0=new S;
 if(arg) v0.f=1;
 return v0;
 """);
-        StopNode stop = parser.parse(false).iterate();
+        StopNode stop = parser.parse().iterate();
         var eval = new Evaluator(stop);
         assertObj(eval.evaluate(0, 10), "S", 0L);
         assertObj(eval.evaluate(1, 10), "S", 1L);
@@ -65,7 +65,7 @@ i=v.f;
 if (arg) v.f=1;
 return i;
 """);
-        StopNode stop = parser.parse(false).iterate();
+        StopNode stop = parser.parse().iterate();
         var eval = new Evaluator(stop);
         assertEquals(2L, eval.evaluate(0, 10));
         assertEquals(2L, eval.evaluate(1, 10));
diff --git a/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
index 4a405a3b..3512d2e9 100644
--- a/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
+++ b/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
@@ -2,10 +2,7 @@ package com.seaofnodes.simple.evaluator;
 
 import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.node.*;
-import com.seaofnodes.simple.type.Field;
-import com.seaofnodes.simple.type.TypeInteger;
-import com.seaofnodes.simple.type.TypeMemPtr;
-import com.seaofnodes.simple.type.TypeStruct;
+import com.seaofnodes.simple.type.*;
 
 import java.lang.invoke.MethodHandle;
 import java.lang.invoke.MethodHandles;
@@ -80,6 +77,10 @@ public class Evaluator {
         long in2 = vall(div.in(2));
         return in2 == 0 ? 0 : vall(div.in(1)) / in2;
     }
+    private double div(DivFNode div) {
+        double in2 = vald(div.in(2));
+        return in2 == 0 ? 0 : vald(div.in(1)) / in2;
+    }
 
     private Object alloc(NewNode alloc) {
         var type = ((TypeMemPtr)alloc.compute())._obj;
@@ -115,10 +116,16 @@ public class Evaluator {
         if (v instanceof Number n) return n.longValue();
         throw new AssertionError("Not a long " + v);
     }
+    private double vald(Node node) {
+        var v = val(node);
+        if (v instanceof Number n) return n.doubleValue();
+        throw new AssertionError("Not a double " + v);
+    }
 
     private Object cons(ConstantNode cons) {
         var type = cons.compute();
         if (type instanceof TypeInteger i) return i.value();
+        if (type instanceof TypeFloat i) return i.value();
         assert type instanceof TypeMemPtr;
         return null;
     }
@@ -127,15 +134,24 @@ public class Evaluator {
         return switch (node) {
             case ConstantNode cons  -> cons(cons);
             case AddNode      add   -> vall(add.in(1)) + vall(add.in(2));
+            case AddFNode     add   -> vald(add.in(1)) + vald(add.in(2));
+            case BoolNode.EQF eq    -> vald(eq.in(1)) == vald(eq.in(2)) ? 1L : 0L;
+            case BoolNode.LEF le    -> vald(le.in(1)) <= vald(le.in(2)) ? 1L : 0L;
+            case BoolNode.LTF lt    -> vald(lt.in(1)) <  vald(lt.in(2)) ? 1L : 0L;
             case BoolNode.EQ  eq    -> Objects.equals(val(eq.in(1)), val(eq.in(2))) ? 1L : 0L;
             case BoolNode.LE  le    -> vall(le.in(1)) <= vall(le.in(2)) ? 1L : 0L;
             case BoolNode.LT  lt    -> vall(lt.in(1)) <  vall(lt.in(2)) ? 1L : 0L;
             case DivNode      div   -> div(div);
+            case DivFNode     div   -> div(div);
             case MinusNode    minus -> -vall(minus.in(1));
+            case MinusFNode   minus -> -vald(minus.in(1));
             case MulNode      mul   -> vall(mul.in(1)) * vall(mul.in(2));
+            case MulFNode     mul   -> vald(mul.in(1)) * vald(mul.in(2));
             case NotNode      not   -> isTrue(val(not.in(1))) ? 0L : 1L;
             case SubNode      sub   -> vall(sub.in(1)) - vall(sub.in(2));
+            case SubFNode     sub   -> vald(sub.in(1)) - vald(sub.in(2));
             case CastNode     cast  -> val(cast.in(1));
+            case ToFloatNode  cast  -> (double)vall(cast.in(1));
             case LoadNode     load  -> load(load);
             case StoreNode    store -> store(store);
             case NewNode      alloc -> alloc(alloc);
diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java
index 155063ab..b8437b50 100644
--- a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java
+++ b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java
@@ -22,6 +22,7 @@ public class ScriptGenerator {
     private static final int MAX_NAME_LENGTH = 10;
     private static final int MAX_BLOCK_DEPTH = 4;
     private static final int MAX_EXPRESSION_DEPTH = 10;
+    private static final int MAX_SUFFIX_RECURSIVE_DEPTH = 10;
 
     /**
      * Number of spaces per indentation
@@ -68,7 +69,7 @@ public class ScriptGenerator {
     }
 
     private static class TypeStruct extends Type {
-        record Field (String name, Type type) {}
+        record Field (String name, Type type, TypeStruct struct) {}
         final Field[] fields;
         final TypeNullable nullable = new TypeNullable(this);
         TypeStruct(String name, Field[] fields) {
@@ -89,7 +90,21 @@ public class ScriptGenerator {
 
     }
 
-    private static final Type TYPE_INT = new Type("int");
+    private static final Type TYPE_FLT = new Type("flt");
+
+    private static class TypeInt extends Type {
+
+        TypeInt() {
+            super("int");
+        }
+
+        @Override
+        boolean isa(Type other) {
+            return super.isa(other) || other == TYPE_FLT;
+        }
+    }
+
+    private static final Type TYPE_INT = new TypeInt();
 
 
     private static class Variable {
@@ -343,7 +358,9 @@ public class ScriptGenerator {
      * @return A random type
      */
     private Type getType() {
-        if (structs.isEmpty() || random.nextBoolean()) return TYPE_INT;
+        int t = random.nextInt(10);
+        if( t<5 || structs.isEmpty() ) return TYPE_INT;
+        if( t<7 ) return TYPE_FLT;
         var idx = random.nextInt(structs.size());
         TypeStruct struct = structs.get(idx);
         if (random.nextBoolean()) return struct.nullable;
@@ -411,17 +428,18 @@ public class ScriptGenerator {
     public int genStruct() {
         var name = getStructName();
         var fields = new TypeStruct.Field[generateInvalid() ? 0 : random.nextInt(10)];
+        var struct = new TypeStruct(name, fields);
         sb.append("struct ").append(name).append(" {\n");
         indentation += INDENTATION;
         for (int i=0; i<fields.length; i++) {
             var fieldName = getRandomName();
-            var type = generateInvalid() ? getType() : TYPE_INT;
+            var type = getType();
             printIndentation().append(type.name).append(" ").append(fieldName).append(";\n");
-            fields[i] = new TypeStruct.Field(fieldName.toString(), type);
+            fields[i] = new TypeStruct.Field(fieldName.toString(), type, struct);
         }
         indentation -= INDENTATION;
         printIndentation().append("}");
-        structs.add(new TypeStruct(name, fields));
+        structs.add(struct);
         return 0;
     }
 
@@ -515,7 +533,7 @@ public class ScriptGenerator {
      */
     public int genIf() {
         sb.append("if(");
-        genExpression(TYPE_INT);
+        genExpression(TYPE_INT, true);
         sb.append(") ");
         var stop = genStatementBlock();
         if ((stop & FLAG_IF_WITHOUT_ELSE) == 0 && random.nextInt(10) > 3) {
@@ -561,7 +579,7 @@ public class ScriptGenerator {
      */
     public int genWhile() {
         sb.append("while(");
-        genExpression(TYPE_INT);
+        genExpression(TYPE_INT, true);
         sb.append(") ");
         loopDepth++;
         genStatementBlock();
@@ -587,17 +605,17 @@ public class ScriptGenerator {
         indentation += INDENTATION;
         String name = getVarName();
         printIndentation().append("int ").append(name).append("=");
-        genExpression(TYPE_INT);
+        genExpression(TYPE_INT, true);
         sb.append(";\n");
         addVariable(name, TYPE_INT);
         printIndentation().append("while(").append(name).append("<");
-        genExpression(TYPE_INT);
+        genExpression(TYPE_INT, true);
         sb.append(") {\n");
         indentation += INDENTATION;
         depth--;
         loopDepth++;
         printIndentation().append(name).append("=").append(name).append("+");
-        genExpression(TYPE_INT);
+        genExpression(TYPE_INT, true);
         sb.append(";\n");
         genStatements();
         loopDepth--;
@@ -621,7 +639,7 @@ public class ScriptGenerator {
         sb.append(generateInvalid() ? getRandomName() : type.name).append(" ").append(name);
         if (!(type instanceof TypeNullable) || random.nextBoolean()) {
             sb.append("=");
-            genExpression(type);
+            genExpression(type, true);
         }
         sb.append(";");
         addVariable(name, type);
@@ -656,7 +674,7 @@ public class ScriptGenerator {
             declared = field.type;
         }
         sb.append("=");
-        genExpression(declared);
+        genExpression(declared, true);
         sb.append(";");
         return 0;
     }
@@ -668,7 +686,7 @@ public class ScriptGenerator {
     public int genReturn() {
         var type = getType();
         sb.append("return ");
-        genExpression(type);
+        genExpression(type, true);
         sb.append(";");
         return FLAG_STOP;
     }
@@ -677,70 +695,91 @@ public class ScriptGenerator {
      * Generate a binary expression.
      * This method does not care about operator precedence.
      */
-    public void genExpression(Type type) {
-        if (generateInvalid()) type = getType();
-        if (type != TYPE_INT) {
-            genUnary(type);
+    public void genExpression(Type type, boolean change) {
+        if (change && generateInvalid()) type = getType();
+        if (type != TYPE_INT && type != TYPE_FLT) {
+            genUnary(type, false);
             return;
         }
         var num = randLog(MAX_BINARY_EXPRESSIONS_PER_EXPRESSION);
         while(num-->0) {
-            genUnary(TYPE_INT);
+            genUnary(type, false);
             sb.append(BINARY_OP[random.nextInt(BINARY_OP.length)]);
         }
-        genUnary(TYPE_INT);
+        genUnary(type, false);
     }
 
     /**
      * Generate a unary expression.
      */
-    public void genUnary(Type type) {
-        if (generateInvalid()) type = getType();
-        if (type != TYPE_INT) {
-            genSuffix(type);
+    public void genUnary(Type type, boolean change) {
+        if (change && generateInvalid()) type = getType();
+        if (type != TYPE_INT && type != TYPE_FLT) {
+            genSuffix(type, false);
             return;
         }
         var num = randLog(MAX_UNARY_EXPRESSIONS_PER_EXPRESSION);
         while(num-->0) {
             sb.append(UNARY_OP[random.nextInt(UNARY_OP.length)]);
         }
-        genSuffix(TYPE_INT);
+        genSuffix(type, false);
+    }
+
+    public TypeStruct.Field getField(Type type) {
+        int n=0;
+        for (var s: structs) {
+            for (var f: s.fields) {
+                if (f.type.isa(type)) n++;
+            }
+        }
+        if (n==0) return null;
+        n = random.nextInt(n);
+        for (var s: structs) {
+            for (var f: s.fields) {
+                if (f.type.isa(type)) if (n--==0) return f;
+            }
+        }
+        throw new AssertionError();
     }
 
     /**
      * Generate
      */
-    public void genSuffix(Type type) {
-        if (generateInvalid()) type = getType();
-        if (type == TYPE_INT && random.nextBoolean()) {
-            var t = getType();
+    public void genSuffix(Type type, boolean change) {
+        genSuffixRecursive(type, change, MAX_SUFFIX_RECURSIVE_DEPTH);
+    }
+
+    public void genSuffixRecursive(Type type, boolean change, int depth) {
+        if (change && generateInvalid()) type = getType();
+        if (depth > 0 && random.nextBoolean()) {
             if (generateInvalid()) {
                 var field = getRandomName();
-                genPrimary(t);
+                var t = getType();
+                genSuffixRecursive(t, true, depth-1);
                 sb.append(".").append(field);
                 return;
-            } else if (t instanceof TypeStruct s && s.fields.length > 0) {
-                var field = s.fields[random.nextInt(s.fields.length)];
-                if (field.type == TYPE_INT) {
-                    genPrimary(t);
+            } else {
+                var field = getField(type);
+                if (field != null) {
+                    genSuffixRecursive(field.struct, true, depth-1);
                     sb.append(".").append(field.name);
                     return;
                 }
             }
         }
-        genPrimary(type);
+        genPrimary(type, false);
     }
 
     /**
      * Generate a primary expression.
      */
-    public void genPrimary(Type type) {
-        if (generateInvalid()) type = getType();
+    public void genPrimary(Type type, boolean change) {
+        if (change && generateInvalid()) type = getType();
         var rand = random.nextInt(10);
         if (rand == 0 && exprDepth != 0) {
             sb.append("(");
             exprDepth--;
-            genExpression(type);
+            genExpression(type, false);
             exprDepth++;
             sb.append(")");
         } else if (rand < 6) {
@@ -755,13 +794,15 @@ public class ScriptGenerator {
      */
     public void genConst(Type type) {
         if (generateInvalid()) type = getType();
-        if (type == TYPE_INT) {
+        if (type == TYPE_INT || (type == TYPE_FLT && random.nextBoolean())) {
             var rand = random.nextInt(10);
             switch (rand) {
                 case 0 -> sb.append("true");
                 case 1 -> sb.append("false");
                 default -> sb.append(random.nextInt(1<<(rand-2)));
             }
+        } else if (type == TYPE_FLT) {
+            sb.append(random.nextFloat());
         } else if (type instanceof TypeNullable n) {
             if (random.nextBoolean()) {
                 sb.append("null");