bug fix widen

Failed lattice law tests mixing constants and have wide type ints; or mixing wide ints and constant arrays.

7 files changed, 84 insertions, 69 deletions

diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index 81af208c..cfeb1404 100644
--- a/chapter24/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/chapter24/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -81,12 +81,13 @@ public class PhiNode extends Node {
         }
         Type newt = t.join( _minType );
 
-        // phi loop widening part
+        // Above-center ranges may still fall to unwidened constants.
+        // Widen only below-center ranges to preserve monotonicity.
         if( region() instanceof LoopNode && // Only around loops
             newt  instanceof TypeInteger newi &&
             // Types changed and are falling (the optimistic case, expected to fall forever)
             newi != _type ) {
-            if( !newi.isConstant() && (!(_type instanceof TypeInteger oldi) || newi._widen <= oldi._widen) )
+            if( !newi.isHigh() && !newi.isConstant() && (!(_type instanceof TypeInteger oldi) || newi._widen <= oldi._widen) )
                 return newi.same_but_slightly_wider_than(_minType);
         }
 
diff --git a/chapter24/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter24/src/main/java/com/seaofnodes/simple/type/Type.java
index fd474a84..b47de0a4 100644
--- a/chapter24/src/main/java/com/seaofnodes/simple/type/Type.java
+++ b/chapter24/src/main/java/com/seaofnodes/simple/type/Type.java
@@ -264,6 +264,9 @@ public class Type /*implements Cloneable*/ {
         // Reverse; xmeet 2nd arg is never "is_simple" and never equal to "this".
         if(   is_simple() ) return this.xmeet(t   );
         if( t.is_simple() ) return t   .xmeet(this);
+        // Constant arrays meet their integer element types.
+        if( this instanceof TypeConAry tcon && t    instanceof TypeInteger ti ) return tcon.ymeet(ti);
+        if( t    instanceof TypeConAry tcon && this instanceof TypeInteger ti ) return tcon.ymeet(ti);
         return Type.BOTTOM;     // Mixing 2 unrelated types
     }
 
diff --git a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAry.java b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAry.java
index c5543030..0bc264fc 100644
--- a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAry.java
+++ b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAry.java
@@ -1,53 +1,57 @@
 package com.seaofnodes.simple.type;
 
-import com.seaofnodes.simple.util.SB;
-import com.seaofnodes.simple.util.Utils;
 import java.io.ByteArrayOutputStream;
+import com.seaofnodes.simple.util.Utils;
 import java.util.ArrayList;
 
 /**
  * Represents a constant array of primitives
  */
-public class TypeConAry<A> extends Type {
+public abstract class TypeConAry<A> extends Type {
     boolean _any;
-    // One of byte,short,int,long,float,double array
+    byte _widen;
+    // One of byte or int array
     public final A _ary;
 
-    TypeConAry( boolean any, byte type, A ary ) { super(type); _any = any; _ary = ary; }
-    public static final TypeConAry BOT = new TypeConAry(false, TINT, null).intern();
+    TypeConAry( boolean any, byte widen, A ary ) { super(TCONARY); _any = any; _widen = widen; _ary = ary; }
     public static void gather(ArrayList<Type> ts) {
-        ts.add(BOT);
-        TypeConAryB.gather(ts);
-        TypeConAryI.gather(ts);
+        ts.add(TypeConAryB.ABC);
+        ts.add(TypeConAryB.ABCD);
+        ts.add(TypeConAryI.I123);
     }
+    // Fresh, uninterned type sharing this array; xdual must not intern.
+    abstract TypeConAry<A> _make(boolean any, byte widen);
 
-    @Override public String str() { return (_any?"~":"") + "[]"; }
-    @Override TypeConAry xdual() {
-        if( _ary==null )
-            return new TypeConAry(!_any,_type,null);
-        return this;
-    }
+    @Override TypeConAry<A> xdual() { return _make( !_any, (byte)(3-_widen) ); }
 
     @Override Type xmeet(Type t) {
-        if( t instanceof TypeInteger ti ) return imeet(ti);
         TypeConAry ary = (TypeConAry)t; // Invariant
-        if( this==BOT ) return BOT;
-        if( ary ==BOT ) return BOT;
-        if( this==BOT.dual() ) return ary ;
-        if( ary ==BOT.dual() ) return this;
-        assert _ary!=ary._ary;  // Already interned and this!=t
+        // Same base array but different?
+        if( _equals(ary) )
+            // Return array with larger widen
+            return _widen >= ary._widen ? this : ary;
+        // Unrelated constant arrays, falls to some int range
         return elem().meet(ary.elem());
     }
-    Type imeet( TypeInteger ti ) {
-        if( this==BOT.dual() ) return ti;
-        if( this==BOT        ) return BOT;
-        Type elem = elem();
-        if( !(elem instanceof TypeInteger) ) return BOTTOM;
-        if( ti.isHigh() && elem.isa(ti.dual()) )
-            return this;
-        return elem.meet(ti);
+
+    Type ymeet( TypeInteger ti ) {
+        // if i can isa *each* element, then maybe can keep.
+        // no good to i.isa(elem()) because fails the dual
+        for( int j=0; j<len(); j++ )
+            if( !ti.isa(TypeInteger.make(at8(j),at8(j),ti._widen)) )
+                return ti.meet(elem());
+        byte widen = (byte)Math.max(_widen,ti._widen);
+        return widen==_widen ? this : _make(_any,widen).intern();
     }
 
+    private boolean _equals(TypeConAry ary) {
+        int len = len();
+        if( len != ary.len() ) return false;
+        for( int i=0; i<len; i++ )
+            if( at8(i) != ary.at8(i) )
+                return false;
+        return true;
+    }
 
     @Override public boolean isHigh() { return this==TOP; }
     @Override boolean _isConstant() { return true; }
@@ -65,20 +69,11 @@ public class TypeConAry<A> extends Type {
             min = Math.min(min,at8(i));
             max = Math.max(max,at8(i));
         }
-        return TypeInteger.make(min,max);
-    }
-    public long at8(int idx) { throw Utils.TODO(); }
-    public int len() { throw Utils.TODO(); }
-    @Override public int log_size() { throw Utils.TODO(); }
-    public void write( ByteArrayOutputStream baos ) { throw Utils.TODO(); }
-
-    @Override boolean eq(Type t) {
-        return t instanceof TypeConAry ary && _any==ary._any && ary._ary==null;
-    }
-
-    @Override int hash() {
-        assert _ary==null;
-        return _any ? 1024 : 0;
+        return TypeInteger.make(min,max,_widen);
     }
+    public abstract long at8(int idx);
+    public abstract int len();
+    @Override public abstract int log_size();
+    public void write( ByteArrayOutputStream baos ) { throw Utils.TODO("Should not reach here: abstract constant array cannot be written"); }
 
 }
diff --git a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java
index 9e5f0a2d..095cdeca 100644
--- a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java
+++ b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java
@@ -1,21 +1,20 @@
 package com.seaofnodes.simple.type;
 
-import java.util.ArrayList;
-import java.util.Arrays;
 import java.io.ByteArrayOutputStream;
+import java.util.Arrays;
 
 public class TypeConAryB extends TypeConAry<byte[]> {
-    private TypeConAryB(byte[] bs) { super(false,TINT,bs); }
-    public static TypeConAryB make( byte[] bs ) { return new TypeConAryB(bs).intern(); }
+    private TypeConAryB(boolean any, byte widen, byte[] bs) { super(any,widen,bs); }
+    @Override TypeConAryB _make( boolean any, byte widen ) { return new TypeConAryB(any,widen,_ary); }
+    public static TypeConAryB make( byte[] bs ) { return new TypeConAryB(false,(byte)0,bs).intern(); }
     public static TypeConAryB make( String s ) { return make(s.getBytes()); }
     static final TypeConAryB ABC  = make("abc");
     static final TypeConAryB ABCD = make("abcd");
-    public static void gather(ArrayList<Type> ts) { ts.add(ABC); ts.add(ABCD); }
     @Override public long at8(int idx) { return _ary[idx]; }
     @Override public int len() { return _ary.length; }
     @Override public int log_size() { return 0; }
     @Override public String str() { return "[\""+new String(_ary)+"\"]"; }
-    @Override boolean eq(Type t) { return t instanceof TypeConAryB ary && Arrays.equals(_ary,ary._ary); }
+    @Override boolean eq(Type t) { return t instanceof TypeConAryB ary && _widen==ary._widen && Arrays.equals(_ary,ary._ary); }
     @Override int hash() { return Arrays.hashCode(_ary); }
     @Override public void write( ByteArrayOutputStream baos ) { baos.write(_ary,0,_ary.length); }
 }
diff --git a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java
index 8228887e..b1b061de 100644
--- a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java
+++ b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java
@@ -1,17 +1,16 @@
 package com.seaofnodes.simple.type;
 
-import java.util.ArrayList;
 import java.util.Arrays;
 
 public class TypeConAryI extends TypeConAry<int[]> {
-    private TypeConAryI(int[] bs) { super(false,TINT,bs); }
-    public static TypeConAryI make( int[] bs ) { return new TypeConAryI(bs).intern(); }
-    private static final TypeConAryI I123  = make(new int[]{1,2,3});
-    public static void gather(ArrayList<Type> ts) { ts.add(I123); }
+    private TypeConAryI(boolean any, byte widen, int[] bs) { super(any,widen,bs); }
+    public static TypeConAryI make( int[] bs ) { return new TypeConAryI(false,(byte)0,bs).intern(); }
+    @Override TypeConAryI _make( boolean any, byte widen ) { return new TypeConAryI(any,widen,_ary); }
+    static final TypeConAryI I123 = make(new int[]{1,2,3});
     @Override public long at8(int idx) { return _ary[idx]; }
     @Override public int len() { return _ary.length; }
     @Override public int log_size() { return 2; }
     @Override public String str() { return "[i32]"; }
-    @Override boolean eq(Type t) { return t instanceof TypeConAryI ary && Arrays.equals(_ary,ary._ary); }
+    @Override boolean eq(Type t) { return t instanceof TypeConAryI ary && _widen==ary._widen && Arrays.equals(_ary,ary._ary); }
     @Override int hash() { return Arrays.hashCode(_ary); }
 }
diff --git a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
index a0cb12cb..74fbfb9f 100644
--- a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
+++ b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
@@ -23,17 +23,13 @@ public class TypeInteger extends Type {
     private static final Ary<TypeInteger> FREE = new Ary<>(TypeInteger.class);
     private TypeInteger(long min, long max, byte widen) { super(TINT); init(min,max,widen); }
     private TypeInteger init(long min, long max, byte widen) {
-        // Constants must always have a widen value of zero.  Widening is only
-        // meaningful for ranges of values - which otherwide can increase in
-        // range size indefinitely.
-        assert min!=max || widen==0; // Constants always zero widen
         _min = min; _max = max; _widen=widen;
         return this;
     }
     public static TypeInteger malloc(long lo, long hi, byte widen) { return FREE.isEmpty() ? new TypeInteger(lo,hi,widen) : FREE.pop().init(lo,hi,widen); }
     public static TypeInteger make(long lo, long hi) { return make(lo,hi,(byte)0); }
     public static TypeInteger make(long lo, long hi, byte widen) {
-        TypeInteger i = malloc(lo,hi,lo==hi ? 0 : widen);
+        TypeInteger i = malloc(lo,hi,widen);
         TypeInteger t2 = i.intern();
         return t2==i ? i : t2.free(i);
     }
@@ -83,7 +79,16 @@ public class TypeInteger extends Type {
 
     public final static TypeInteger FATBOOL = make(0,1,(byte)2);
 
-    public static void gather(ArrayList<Type> ts) { ts.add(I32); ts.add(BOT); ts.add(U1); ts.add(I1); ts.add(U8); ts.add(ZERO); ts.add(FATBOOL); }
+    public static void gather(ArrayList<Type> ts) {
+        ts.add(I32); ts.add(BOT); ts.add(U1); ts.add(I1); ts.add(U8); ts.add(ZERO); ts.add(FATBOOL);
+        // Ranges before and after excluding zero, at each widening level.
+        for( byte widen=0; widen<=3; widen++ ) {
+            ts.add(make(0,255,widen));
+            ts.add(make(1,255,widen));
+            ts.add(make(-255,0,widen));
+            ts.add(make(-255,-1,widen));
+        }
+    }
 
     @Override public String str() {
         if( _isConstant() ) return ""+_min;
@@ -147,21 +152,18 @@ public class TypeInteger extends Type {
 
     @Override
     public Type xmeet(Type other) {
-        if( other instanceof TypeConAry ary ) return ary.imeet(this);
         // Invariant from caller: 'this' != 'other' and same class (TypeInteger)
         TypeInteger i = (TypeInteger)other; // Contract
         return make(Math.min(_min,i._min), Math.max(_max,i._max), (byte)Math.max(_widen,i._widen));
     }
 
-    @Override TypeInteger xdual() {
-        return _min==_max ? this : malloc(_max,_min,(byte)(-_widen));
-    }
+    @Override TypeInteger xdual() { return malloc(_max,_min,(byte)(3-_widen)); }
 
     @Override public TypeInteger nonZero() {
         if( isHigh() ) return this;
         if( this==ZERO ) return null;                  // No sane answer
-        if( _min==0 ) return make(1,Math.max(_max,1)); // specifically good on BOOL
-        if( _max==0 ) return make(_min,-1);
+        if( _min==0 ) return make(1,Math.max(_max,1),_widen); // specifically good on BOOL
+        if( _max==0 ) return make(_min,-1,_widen);
         return this;
     }
     @Override public Type makeZero() { return ZERO; }
diff --git a/chapter24/src/test/java/com/seaofnodes/simple/TypeTest.java b/chapter24/src/test/java/com/seaofnodes/simple/TypeTest.java
index 40264d1d..ba7d2a1e 100644
--- a/chapter24/src/test/java/com/seaofnodes/simple/TypeTest.java
+++ b/chapter24/src/test/java/com/seaofnodes/simple/TypeTest.java
@@ -7,6 +7,22 @@ import static org.junit.Assert.assertSame;
 
 public class TypeTest {
 
+    // Removing zero must not reset the widening history of a remaining range.
+    @Test public void testNonZeroWidening() {
+        for( byte widen=0; widen<=3; widen++ ) {
+            TypeInteger pos = TypeInteger.make(0,255,widen).nonZero();
+            TypeInteger neg = TypeInteger.make(-255,0,widen).nonZero();
+            Assert.assertEquals("positive range widening",widen,pos._widen);
+            Assert.assertEquals("negative range widening",widen,neg._widen);
+            assertSame(TypeInteger.make(1,255,widen),pos);
+            assertSame(TypeInteger.make(-255,-1,widen),neg);
+            // Singleton ranges retain their widening level too.
+            assertSame(TypeInteger.make(1,1,widen),TypeInteger.make(0,1,widen).nonZero());
+            assertSame(TypeInteger.make(-1,-1,widen),TypeInteger.make(-1,0,widen).nonZero());
+        }
+        Assert.assertNull(TypeInteger.ZERO.nonZero());
+    }
+
     // Struct hashes omit field types, so interning compares unlike leaf kinds.
     @Test
     public void testCyclicLeafKinds() {