Chapter 14: Narrow types

Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
Co-authored-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Co-authored-by: tannal <tannal2409@gmail.com>
Co-authored-by: hadha <helsgithub15@gmail.com>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: RobertObkircher <robert.obkircher@gmail.com>
Co-authored-by: Robert Obkircher <robert.obkircher@gmail.com>

9 files changed, 366 insertions, 26 deletions

diff --git a/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/src/test/java/com/seaofnodes/simple/Chapter06Test.java
index 633b25e0..99ce8fa5 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter06Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter06Test.java
@@ -27,10 +27,10 @@ return 1;
 int a = 1;
 if (arg)
     a = 2;
-return (arg < a) < 3;
+return (arg < a) < 3; // Because (arg < a) is a bool/uint1/[0-1], its always less than 3
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return ((arg<Phi(Region16,2,1))<3);", stop.toString());
+        assertEquals("return 1;", stop.toString());
     }
 
     @Test
@@ -65,7 +65,7 @@ else
     b=5;
 return b;""", TypeInteger.BOT);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Region39,42,5);", stop.toString());
+        assertEquals("return Phi(Region34,42,5);", stop.toString());
     }
 
     @Test
diff --git a/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/src/test/java/com/seaofnodes/simple/Chapter07Test.java
index e604937c..e6e0560b 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter07Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter07Test.java
@@ -1,7 +1,6 @@
 package com.seaofnodes.simple;
 
 import com.seaofnodes.simple.node.*;
-import com.seaofnodes.simple.type.TypeInteger;
 import org.junit.Test;
 
 import static org.junit.Assert.*;
diff --git a/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/src/test/java/com/seaofnodes/simple/Chapter10Test.java
index c9f695c9..fb324fd9 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter10Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter10Test.java
@@ -28,7 +28,7 @@ if( (arg/13)==0 ) {
 int r = g+h;
 return p-r;
 """);
-        StopNode stop = parser.parse().iterate(false);
+        StopNode stop = parser.parse(false).iterate(false);
         assertEquals("return 0;", stop.toString());
     }
 
@@ -48,7 +48,7 @@ bar.a = 1;
 bar.a = 2;
 return bar.a;
 """);
-        StopNode stop = parser.parse().iterate();
+        StopNode stop = parser.parse(false).iterate();
         assertEquals("return 2;", stop.toString());
     }
 
@@ -102,7 +102,7 @@ while (arg) {
 }
 return bar.a;
 """);
-        StopNode stop = parser.parse().iterate();
+        StopNode stop = parser.parse(false).iterate();
         assertEquals("return Phi(Loop12,0,(Phi_a+2));", stop.toString());
     }
 
@@ -154,7 +154,7 @@ if (arg) bar = null;
 if( bar ) bar.a = 1;
 return bar;
 """);
-        StopNode stop = parser.parse().iterate();
+        StopNode stop = parser.parse(false).iterate();
         assertEquals("return Phi(Region31,(*void)Phi(Region19,null,new Bar),null);", stop.toString());
     }
 
@@ -170,7 +170,7 @@ if( !bar ) rez=4;
 else bar.a = 1;
 return rez;
 """);
-        StopNode stop = parser.parse().iterate();
+        StopNode stop = parser.parse(false).iterate();
         assertEquals("return Phi(Region37,4,3);", stop.toString());
     }
 
diff --git a/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/src/test/java/com/seaofnodes/simple/Chapter11Test.java
index da0bc087..63cd511a 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(false);
-        assertEquals("Stop[ return 9; return 0; return 0; return 0; return 0; ]", stop.toString());
+        assertEquals("Stop[ return 9; return 0; return 0; return 0; ]", stop.toString());
     }
 
 
diff --git a/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/src/test/java/com/seaofnodes/simple/Chapter12Test.java
index 62dce12b..972118be 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter12Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter12Test.java
@@ -59,5 +59,4 @@ return x+1==x;
         assertEquals("return ((flt)arg==(ToFloat+1.0));", stop.toString());
         assertEquals(0L, Evaluator.evaluate(stop, 1));
     }
-
 }
diff --git a/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/src/test/java/com/seaofnodes/simple/Chapter13Test.java
index 59f08963..807badd5 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter13Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter13Test.java
@@ -127,7 +127,7 @@ n.i = 3.14;
 return n.i;
 """);
         try { parser.parse().iterate(); fail(); }
-        catch( Exception e ) { assertEquals("Cannot store 3.14 into field IntBot i",e.getMessage()); }
+        catch( Exception e ) { assertEquals("Cannot store 3.14 into field int i",e.getMessage()); }
     }
 
     @Test
diff --git a/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/src/test/java/com/seaofnodes/simple/Chapter14Test.java
new file mode 100644
index 00000000..fcb7fa24
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/Chapter14Test.java
@@ -0,0 +1,317 @@
+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 Chapter14Test {
+
+    @Test
+    public void testJig() {
+        Parser parser = new Parser(
+"""
+return 3.14;
+""");
+        StopNode stop = parser.parse(false).iterate();
+        assertEquals("return 3.14;", stop.toString());
+        assertEquals(3.14, Evaluator.evaluate(stop,  0));
+    }
+
+    @Test
+    public void testRange() {
+        Parser parser = new Parser(
+"""
+int b;
+if( arg ) b=1; else b=0;
+int c = 99;
+if( b < 0 ) c = -1;
+if( b > 2 ) c =  1;
+return c;
+""");
+        StopNode stop = parser.parse(false).iterate(false);
+        assertEquals("return 99;", stop.toString());
+        assertEquals(99L, Evaluator.evaluate(stop,  0));
+    }
+
+    @Test
+    public void testU8() {
+        Parser parser = new Parser(
+"""
+u8 b = 123;
+b = b + 456;// Truncate
+return b;
+""");
+        StopNode stop = parser.parse(false).iterate(false);
+        assertEquals("return 67;", stop.toString());
+        assertEquals(67L, Evaluator.evaluate(stop,  0));
+    }
+
+
+    @Test
+    public void testU8While() {
+        Parser parser = new Parser(
+"""
+u8 b = 123;
+while( b ) b = b + 456;// Truncate
+return b;
+""");
+        StopNode stop = parser.parse(false).iterate(false);
+        assertEquals("return Phi(Loop9,123,((Phi_b+456)&255));", stop.toString());
+    }
+
+    @Test
+    public void testU1() {
+        Parser parser = new Parser(
+"""
+bool b = 123;
+b = b + 456;// Truncate
+u1 c = b;   // No more truncate needed
+return c;
+""");
+        StopNode stop = parser.parse(false).iterate(false);
+        assertEquals("return 1;", stop.toString());
+        assertEquals(1L, Evaluator.evaluate(stop,  0));
+    }
+
+    @Test
+    public void testAnd() {
+        Parser parser = new Parser(
+"""
+int b = 123;
+b = b+456 & 31;                 // Precedence
+return b;
+""");
+        StopNode stop = parser.parse(false).iterate(false);
+        assertEquals("return 3;", stop.toString());
+        assertEquals(3L, Evaluator.evaluate(stop,  0));
+    }
+
+    @Test
+    public void testRefLoad() {
+        Parser parser = new Parser(
+"""
+struct Foo { u1 b; }
+Foo f = new Foo;
+f.b = 123;
+return f.b;
+""");
+        StopNode stop = parser.parse(false).iterate(false);
+        assertEquals("return 1;", stop.toString());
+        assertEquals(1L, Evaluator.evaluate(stop,  0));
+    }
+
+    @Test
+    public void testSigned() {
+        Parser parser = new Parser(
+"""
+i8 b = 255;                     // Chopped
+return b;                       // Sign extend
+""");
+        StopNode stop = parser.parse(false).iterate(false);
+        assertEquals("return -1;", stop.toString());
+        assertEquals(-1L, Evaluator.evaluate(stop,  0));
+    }
+
+    @Test
+    public void testI8() {
+        Parser parser = new Parser(
+"""
+i8 b = arg;
+b = b + 1;// Truncate
+return b;
+""");
+        StopNode stop = parser.parse(false).iterate(false);
+        assertEquals("return (((((arg<<56)>>56)+1)<<56)>>56);", stop.toString());
+        assertEquals(1L, Evaluator.evaluate(stop,  0));
+    }
+
+    @Test
+    public void testMask() {
+        Parser parser = new Parser(
+"""
+u16 mask = (1<<16)-1;           // AND mask
+int c = 123456789 & mask;
+return c;                       //
+""");
+        StopNode stop = parser.parse(false).iterate(false);
+        assertEquals("return 52501;", stop.toString());
+        assertEquals(52501L, Evaluator.evaluate(stop,  0));
+    }
+
+    @Test
+    public void testWrapMinus() {
+        Parser parser = new Parser(
+"""
+int MAX = 9223372036854775807; //0x7FFFFFFFFFFFFFFF;
+int i = (arg&MAX) + -MAX + -1; // Basically (e0) + Long.MIN_VALUE
+int j = -i; // Negating Long.MIN_VALUE wraps, cannot constant fold
+if (arg) j = 1;
+return j;
+""");
+        StopNode stop = parser.parse(false).iterate();
+        assertEquals("return Phi(Region28,1,(-((arg&9223372036854775807)+-9223372036854775808)));", stop.toString());
+        assertEquals(-9223372036854775808L, Evaluator.evaluate(stop,  0));
+        assertEquals(1L, Evaluator.evaluate(stop,  1));
+    }
+
+    @Test
+    public void testWrapShr() {
+        Parser parser = new Parser(
+"""
+return (arg >>> 1)==0;
+""");
+        StopNode stop = parser.parse(false).iterate();
+        assertEquals("return (!(arg>>>1));", stop.toString());
+        assertEquals(1L, Evaluator.evaluate(stop, 0));
+        assertEquals(1L, Evaluator.evaluate(stop, 1));
+        assertEquals(0L, Evaluator.evaluate(stop, 2));
+    }
+
+    @Test
+    public void testOr() {
+        Parser parser = new Parser(
+"""
+return (arg | 123 ^ 456) >>> 1;
+""");
+        StopNode stop = parser.parse(false).iterate(false);
+        assertEquals("return (((arg|123)^456)>>>1);", stop.toString());
+        assertEquals(217L, Evaluator.evaluate(stop,  0));
+    }
+
+    @Test
+    public void testMaskFloat() {
+        Parser parser = new Parser(
+"""
+flt f = arg;
+arg = f & 0;
+return arg;
+""");
+        try { parser.parse().iterate(); fail(); }
+        catch( Exception e ) { assertEquals("Cannot '&' FltBot",e.getMessage()); }
+    }
+
+    @Test
+    public void testLoadBug() {
+        Parser parser = new Parser(
+"""
+struct A { int i; }
+struct B { int i; }
+A a = new A;
+A t1 = new A;
+B b = new B;
+B t2 = new B;
+int i;
+if (arg) i = a.i;
+else     i = b.i;
+return i;
+""");
+        StopNode stop = parser.parse(false).iterate(false);
+        assertEquals("return Phi(Region31,.i,.i);", stop.toString());
+        assertEquals(0L, Evaluator.evaluate(stop, 0));
+    }
+
+    @Test
+    public void testBug2() {
+        Parser parser = new Parser(
+"""
+int z = 0;
+while (1) {
+    int j;
+    if (arg&3) {
+        j = arg >> 2;
+    } else {
+        j = (arg >> 3)+z;
+    }
+    return j+1;
+}
+""");
+        StopNode stop = parser.parse(false).iterate(false);
+        assertEquals("return ((arg>>Phi(Region32,2,3))+1);", stop.toString());
+        assertEquals(1L, Evaluator.evaluate(stop, 0));
+        assertEquals(1L, Evaluator.evaluate(stop, 1));
+        assertEquals(2L, Evaluator.evaluate(stop, 7));
+        assertEquals(2L, Evaluator.evaluate(stop, 8));
+    }
+
+    @Test
+    public void testBug3() {
+        Parser parser = new Parser(
+"""
+flt f = arg;
+bool b;
+if (arg&3) b = f == 1.0;
+else       b = f == 2.0;
+if (arg&5) b = arg == 1;
+return b;
+""");
+        StopNode stop = parser.parse(false).iterate(false);
+        assertEquals("return Phi(Region37,(arg==1),((flt)arg==Phi(Region23,1.0,2.0)));", stop.toString());
+        assertEquals(1L, Evaluator.evaluate(stop, 1));
+        assertEquals(0L, Evaluator.evaluate(stop, 2));
+        assertEquals(0L, Evaluator.evaluate(stop, 3));
+    }
+
+    @Test
+    public void testBug4() {
+        Parser parser = new Parser(
+"""
+int i;
+if (arg&7) i=3;
+else       i=2;
+return (arg == i) == 1;
+""");
+        StopNode stop = parser.parse(false).iterate();
+        assertEquals("return (arg==Phi(Region18,3,2));", stop.toString());
+        assertEquals(0L, Evaluator.evaluate(stop,  0));
+        assertEquals(0L, Evaluator.evaluate(stop,  1));
+        assertEquals(0L, Evaluator.evaluate(stop,  2));
+        assertEquals(1L, Evaluator.evaluate(stop,  3));
+    }
+
+    @Test
+    public void testBug5() {
+        Parser parser = new Parser(
+"""
+int d = -1;
+while (1) {
+    int i = (arg & 7) + (9223372036854775807 - 7);
+    if (arg & 1) i = ((arg&3) + (9223372036854775807 - 3)) & d;
+    return i + -1;
+}
+""");
+        StopNode stop = parser.parse(false).iterate();
+        assertEquals("return (Phi(Region43,((arg&3)+9223372036854775804),((arg&7)+9223372036854775800))+-1);", stop.toString());
+        assertEquals(0x7FFFFFFFFFFFFFF7L, Evaluator.evaluate(stop,  0));
+        assertEquals(0x7FFFFFFFFFFFFFFCL, Evaluator.evaluate(stop,  1));
+    }
+
+    @Test
+    public void testTypes() {
+        Parser parser = new Parser(
+"""
+i8  xi8  = 123456789;  if( xi8  !=        21 ) return -8;
+i16 xi16 = 123456789;  if( xi16 !=    -13035 ) return -16;
+i32 xi32 = 123456789;  if( xi32 != 123456789 ) return -32;
+i64 xi64 = 123456789;  if( xi64 != 123456789 ) return -64;
+int xint = 123456789;  if( xint != 123456789 ) return -64;
+
+u1  ui1  = 123456789;  if( ui1  !=         1 ) return 1;
+u8  ui8  = 123456789;  if( ui8  !=        21 ) return 8;
+u16 ui16 = 123456789;  if( ui16 !=     52501 ) return 16;
+u32 ui32 = 123456789;  if( ui32 != 123456789 ) return 32;
+
+flt fflt = 3.141592653589793;  if( fflt != 3.141592653589793 ) return 3;
+f64 ff64 = 3.141592653589793;  if( ff64 != 3.141592653589793 ) return 3;
+f32 ff32 = 3.141592653589793;  if( ff32 != 3.1415927410125732) return 5;
+
+return 0;
+""");
+        StopNode stop = parser.parse().iterate(false);
+        assertEquals("return 0;", stop.toString());
+        assertEquals(0L, Evaluator.evaluate(stop,  0));
+    }
+
+}
diff --git a/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
index 3512d2e9..31a14c05 100644
--- a/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
+++ b/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
@@ -150,6 +150,12 @@ public class Evaluator {
             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 ShlNode      shl   -> vall(shl.in(1)) << vall(shl.in(2));
+            case ShrNode      shr   -> vall(shr.in(1)) >>> vall(shr.in(2));
+            case SarNode      sar   -> vall(sar.in(1)) >> vall(sar.in(2));
+            case AndNode      and   -> vall(and.in(1)) & vall(and.in(2));
+            case  OrNode      or    -> vall(or .in(1)) | vall(or .in(2));
+            case XorNode      xor   -> vall(xor.in(1)) ^ vall(xor.in(2));
             case CastNode     cast  -> val(cast.in(1));
             case ToFloatNode  cast  -> (double)vall(cast.in(1));
             case LoadNode     load  -> load(load);
diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java
index 94929241..ec6e7816 100644
--- a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java
+++ b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java
@@ -2,8 +2,12 @@ package com.seaofnodes.simple.fuzzer;
 
 import com.seaofnodes.simple.Parser;
 import com.seaofnodes.simple.node.ScopeNode;
+import com.seaofnodes.simple.type.TypeInteger;
 
-import java.util.*;
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Random;
 import java.util.function.Predicate;
 
 /**
@@ -21,7 +25,7 @@ public class ScriptGenerator {
     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
      */
@@ -54,7 +58,7 @@ public class ScriptGenerator {
     /**
      * Binary operators.
      */
-    private static final String[] BINARY_OP = {"==", "!=", "<", "<=", ">", ">=", "+", "-", "*", "/"};
+    private static final String[] BINARY_OP = {"==", "!=", "<", "<=", ">", ">=", "+", "-", "*", "/", "&", ">>", ">>>", "<<"};
     /**
      * Unary operators.
      */
@@ -91,18 +95,29 @@ public class ScriptGenerator {
 
     private static class TypeInt extends Type {
 
-        TypeInt() {
-            super("int");
+        TypeInt(String name) {
+            super(name);
         }
 
         @Override
         boolean isa(Type other) {
-            return super.isa(other) || other == TYPE_FLT;
+            return super.isa(other) || other == TYPE_FLT || other instanceof TypeInt;
         }
     }
 
-    private static final Type TYPE_INT = new TypeInt();
+    private static final List<TypeInt> INTTYPES = new ArrayList<>();
+
+    static {
+        new Parser("", TypeInteger.BOT);
+        for(var e:Parser.TYPES.entrySet()) {
+            if (e.getValue() instanceof TypeInteger) {
+                INTTYPES.add(new TypeInt(e.getKey()));
+            }
+        }
+    }
 
+    private static final Type TYPE_INT = INTTYPES.stream().filter(t->t.name.equals("int")).findAny().get();
+    private static final Type TYPE_BOOL = INTTYPES.stream().filter(t->t.name.equals("bool")).findAny().get();
 
     private static class Variable {
         final String name;
@@ -361,13 +376,17 @@ public class ScriptGenerator {
         return v;
     }
 
+    public TypeInt getIntType() {
+        return randFromList(INTTYPES);
+    }
+
     /**
      * Get a random type
      * @return A random type
      */
     private Type getType(boolean allowForward) {
         int t = random.nextInt(10);
-        if( t<5 || structs.isEmpty() ) return TYPE_INT;
+        if( t<5 || structs.isEmpty() ) return getIntType();
         if( t<7 ) return TYPE_FLT;
         if (allowForward && random.nextInt(10)==0) {
             int i=random.nextInt(forwardStructs.size()+1);
@@ -448,7 +467,7 @@ public class ScriptGenerator {
         int idx = random.nextInt(forwardStructs.size()+10);
         TypeStruct struct;
         if (idx < 10) {
-            var name = getStructName();
+        var name = getStructName();
             struct = new TypeStruct(name);
             forwardStructs.add(struct);
         } else {
@@ -561,7 +580,7 @@ public class ScriptGenerator {
      */
     public int genIf() {
         sb.append("if(");
-        genExpression(TYPE_INT, true);
+        genExpression(TYPE_BOOL, true);
         sb.append(") ");
         var stop = genStatementBlock();
         if ((stop & FLAG_IF_WITHOUT_ELSE) == 0 && random.nextInt(10) > 3) {
@@ -607,7 +626,7 @@ public class ScriptGenerator {
      */
     public int genWhile() {
         sb.append("while(");
-        genExpression(TYPE_INT, true);
+        genExpression(TYPE_BOOL, true);
         sb.append(") ");
         loopDepth++;
         genStatementBlock();
@@ -725,7 +744,7 @@ public class ScriptGenerator {
      */
     public void genExpression(Type type, boolean change) {
         if (change && generateInvalid()) type = getType();
-        if (type != TYPE_INT && type != TYPE_FLT) {
+        if (!(type instanceof TypeInt) && type != TYPE_FLT) {
             genUnary(type, false);
             return;
         }
@@ -742,7 +761,7 @@ public class ScriptGenerator {
      */
     public void genUnary(Type type, boolean change) {
         if (change && generateInvalid()) type = getType();
-        if (type != TYPE_INT && type != TYPE_FLT) {
+        if (!(type instanceof TypeInt) && type != TYPE_FLT) {
             genSuffix(type, false);
             return;
         }
@@ -822,7 +841,7 @@ public class ScriptGenerator {
      */
     public void genConst(Type type) {
         if (generateInvalid()) type = getType();
-        if (type == TYPE_INT || (type == TYPE_FLT && random.nextBoolean())) {
+        if (type instanceof TypeInt || (type == TYPE_FLT && random.nextBoolean())) {
             var rand = random.nextInt(10);
             switch (rand) {
                 case 0 -> sb.append("true");