Canonicalize aggregate memory duals and preserve field finalitymain

6 files changed, 90 insertions, 18 deletions

diff --git a/chapter28a/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/chapter28a/src/main/java/com/seaofnodes/simple/type/TypeMem.java
index 4234a5e5..a0079eae 100644
--- a/chapter28a/src/main/java/com/seaofnodes/simple/type/TypeMem.java
+++ b/chapter28a/src/main/java/com/seaofnodes/simple/type/TypeMem.java
@@ -37,11 +37,10 @@ public class TypeMem extends Type {
         _t = t;
         _one = one;
         _clz = clz;
-        // Public bulk memory is an aggregate of otherwise-unsplit aliases;
-        // a single final bit cannot describe it.  Keep the lattice-dual high
-        // form distinct, and retain finality for private singleton memory and
-        // precise alias slices.
-        _final = t!=null && alias==1 && !one && !t.isHigh() ? false : xfinal;
+        // Alias 1 represents an aggregate, including a private object's fields.
+        // Its fields carry finality individually. Canonicalize the unused bit
+        // with _one so normalization commutes with dual, including named structs.
+        _final = alias==1 ? one : xfinal;
 
         assert _escFs == null && _escAs == null;
         _escFs = XInt.intern(fidxs);
@@ -126,9 +125,10 @@ public class TypeMem extends Type {
         int[] fidxs  = XInt.meet( _escFs, that._escFs );
         int[] aliases= XInt.meet( _escAs, that._escAs );
         // Singleton and class facts are kept only when both sides agree.
-        // Finality is a low-side fact, and flips on the dual side.
-        boolean highAlias1 = (this._alias==1 && this._t.isHigh()) || (that._alias==1 && that._t.isHigh());
-        boolean xfinal = highAlias1 ? (_final & that._final) : (_final | that._final);
+        // An aggregate has no field-wide finality. If meeting with it selects
+        // a precise alias, retain that slice's finality without mixing in the
+        // aggregate's canonical placeholder bit.
+        boolean xfinal = _alias==1 ? that._final : that._alias==1 ? _final : (_final | that._final);
         return make(alias, mt, _one & that._one, _clz & that._clz, xfinal, fidxs, aliases);
     }
 
@@ -141,7 +141,6 @@ public class TypeMem extends Type {
         TypeMem d = malloc(_alias,null,!_one,!_clz,!_final, XInt.dual(_escFs), XInt.dual(_escAs));
         (_dual = d)._dual = this; // Cross link duals
         d._t = _t._terned ? _t.dual() : _t.rdual();
-        if( d._alias==1 && !d._one ) { assert !d._t.isHigh(); d._final = false; }
         return d;
     }
 
@@ -166,6 +165,7 @@ public class TypeMem extends Type {
     }
 
     @Override boolean cycle_eq(Type t) {
+        if( t._type!=TMEM ) return false;
         TypeMem that = (TypeMem) t; // Invariant
         return _alias == that._alias && _one == that._one && _clz == that._clz && _final == that._final && _escFs == that._escFs && _escAs == that._escAs && _t.cycle_eq(that._t);
     }
diff --git a/chapter28a/src/test/java/com/seaofnodes/simple/BoundaryTest.java b/chapter28a/src/test/java/com/seaofnodes/simple/BoundaryTest.java
index 68d8175f..4e3fbb1b 100644
--- a/chapter28a/src/test/java/com/seaofnodes/simple/BoundaryTest.java
+++ b/chapter28a/src/test/java/com/seaofnodes/simple/BoundaryTest.java
@@ -9,6 +9,16 @@ import static org.junit.Assert.*;
 // The new module boundary must preserve the preceding chapters' examples.
 public class BoundaryTest {
     @Test public void testLocalConstruction() throws java.io.IOException {
+        // Nested factories must preserve memory duals during construction,
+        // for both direct fields and getters on the returned instance.
+        for( String body : new String[]{"int x=7;", "int _x=7; val get={ -> _x; };" } )
+            for( long seed : new long[]{1,13,123} ) {
+                String src = "struct Outer { struct _Hidden { "+body+
+                    " }; val make={ -> new _Hidden(); }; }; return new Outer().make().";
+                CodeGen factory = new CodeGen(src+(body.startsWith("int x") ? "x;" : "get();"),seed,true)
+                    .driver(CodeGen.Phase.TypeCheck);
+                assertEquals("7",Eval2.eval(factory,0));
+            }
         String src="struct Counter { int x; int y; int z; new Counter={int n -> while(x<n) { int old=x; y=x+1; x=y+1; z=old; }}; }; val c=new Counter(arg); return c.x*100+c.z;";
         CodeGen code=new CodeGen(src).driver(CodeGen.Phase.LocalSched);
         assertEquals("2018",Eval2.eval(code,19));
diff --git a/chapter28a/src/test/java/com/seaofnodes/simple/TypeTest.java b/chapter28a/src/test/java/com/seaofnodes/simple/TypeTest.java
index f6099607..4090bde3 100644
--- a/chapter28a/src/test/java/com/seaofnodes/simple/TypeTest.java
+++ b/chapter28a/src/test/java/com/seaofnodes/simple/TypeTest.java
@@ -7,6 +7,32 @@ import static org.junit.Assert.assertSame;
 
 public class TypeTest {
 
+    // Aggregate finality is carried by its fields. Canonicalizing the unused
+    // aggregate bit must commute with dual, even for named (non-high) structs.
+    @Test public void testAggregateMemoryDual() {
+        TypeStruct obj = TypeStruct.make("AggregateDual",false,
+            Field.make("x",TypeInteger.BOT,2,false),
+            Field.make("y",TypeInteger.ZERO,3,true));
+        for( Type t : new Type[]{Type.BOTTOM,Type.TOP,TypeStruct.BOT,TypeStruct.TOP,obj,obj.dual()} )
+            for( boolean one : new boolean[]{false,true} ) {
+                TypeMem mem = TypeMem.make(1,t,one,false,false,XInt.EMPTY,XInt.EMPTY);
+                assertSame(mem,TypeMem.make(1,t,one,false,true,XInt.EMPTY,XInt.EMPTY));
+                assertSame(mem,mem.dual().dual());
+                assertSame(mem.dual(),TypeMem.make(1,t.dual(),!one,true,true,XInt.FULL,XInt.FULL));
+            }
+        // Precise field slices still distinguish final and mutable storage.
+        Assert.assertNotEquals(TypeMem.make(2,TypeInteger.BOT,false,false,false,XInt.EMPTY,XInt.EMPTY),
+                               TypeMem.make(2,TypeInteger.BOT,false,false,true ,XInt.EMPTY,XInt.EMPTY));
+        for( boolean one : new boolean[]{false,true} )
+            for( boolean fin : new boolean[]{false,true} ) {
+                TypeMem bulk = TypeMem.make(1,Type.TOP,one,false,false,XInt.EMPTY,XInt.EMPTY);
+                TypeMem slice = TypeMem.make(2,TypeInteger.BOT,false,false,fin,XInt.EMPTY,XInt.EMPTY);
+                assertSame(slice,bulk.meet(slice));
+                check_symmetric(bulk,slice);
+                check_symmetric(bulk.dual(),slice.dual());
+            }
+    }
+
     // Removing zero must not reset the widening history of a remaining range.
     @Test public void testNonZeroWidening() {
         for( byte widen=0; widen<=3; widen++ ) {
diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/chapter28b/src/main/java/com/seaofnodes/simple/type/TypeMem.java
index d0fc3ee9..278a3ea0 100644
--- a/chapter28b/src/main/java/com/seaofnodes/simple/type/TypeMem.java
+++ b/chapter28b/src/main/java/com/seaofnodes/simple/type/TypeMem.java
@@ -37,11 +37,10 @@ public class TypeMem extends Type {
         _t = t;
         _one = one;
         _clz = clz;
-        // Public bulk memory is an aggregate of otherwise-unsplit aliases;
-        // a single final bit cannot describe it.  Keep the lattice-dual high
-        // form distinct, and retain finality for private singleton memory and
-        // precise alias slices.
-        _final = t!=null && alias==1 && !one && !t.isHigh() ? false : xfinal;
+        // Alias 1 represents an aggregate, including a private object's fields.
+        // Its fields carry finality individually. Canonicalize the unused bit
+        // with _one so normalization commutes with dual, including named structs.
+        _final = alias==1 ? one : xfinal;
 
         assert _escFs == null && _escAs == null;
         _escFs = XInt.intern(fidxs);
@@ -126,9 +125,10 @@ public class TypeMem extends Type {
         int[] fidxs  = XInt.meet( _escFs, that._escFs );
         int[] aliases= XInt.meet( _escAs, that._escAs );
         // Singleton and class facts are kept only when both sides agree.
-        // Finality is a low-side fact, and flips on the dual side.
-        boolean highAlias1 = (this._alias==1 && this._t.isHigh()) || (that._alias==1 && that._t.isHigh());
-        boolean xfinal = highAlias1 ? (_final & that._final) : (_final | that._final);
+        // An aggregate has no field-wide finality. If meeting with it selects
+        // a precise alias, retain that slice's finality without mixing in the
+        // aggregate's canonical placeholder bit.
+        boolean xfinal = _alias==1 ? that._final : that._alias==1 ? _final : (_final | that._final);
         return make(alias, mt, _one & that._one, _clz & that._clz, xfinal, fidxs, aliases);
     }
 
@@ -141,7 +141,6 @@ public class TypeMem extends Type {
         TypeMem d = malloc(_alias,null,!_one,!_clz,!_final, XInt.dual(_escFs), XInt.dual(_escAs));
         (_dual = d)._dual = this; // Cross link duals
         d._t = _t._terned ? _t.dual() : _t.rdual();
-        if( d._alias==1 && !d._one ) { assert !d._t.isHigh(); d._final = false; }
         return d;
     }
 
@@ -166,6 +165,7 @@ public class TypeMem extends Type {
     }
 
     @Override boolean cycle_eq(Type t) {
+        if( t._type!=TMEM ) return false;
         TypeMem that = (TypeMem) t; // Invariant
         return _alias == that._alias && _one == that._one && _clz == that._clz && _final == that._final && _escFs == that._escFs && _escAs == that._escAs && _t.cycle_eq(that._t);
     }
diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/BoundaryTest.java b/chapter28b/src/test/java/com/seaofnodes/simple/BoundaryTest.java
index b736ccb3..e196b93f 100644
--- a/chapter28b/src/test/java/com/seaofnodes/simple/BoundaryTest.java
+++ b/chapter28b/src/test/java/com/seaofnodes/simple/BoundaryTest.java
@@ -9,6 +9,16 @@ import static org.junit.Assert.*;
 // The new module boundary must preserve the preceding chapters' examples.
 public class BoundaryTest {
     @Test public void testLocalConstruction() throws java.io.IOException {
+        // Nested factories must preserve memory duals during construction,
+        // for both direct fields and getters on the returned instance.
+        for( String body : new String[]{"int x=7;", "int _x=7; val get={ -> _x; };" } )
+            for( long seed : new long[]{1,13,123} ) {
+                String src = "struct Outer { struct _Hidden { "+body+
+                    " }; val make={ -> new _Hidden(); }; }; return new Outer().make().";
+                CodeGen factory = new CodeGen(src+(body.startsWith("int x") ? "x;" : "get();"),seed,true)
+                    .driver(CodeGen.Phase.TypeCheck);
+                assertEquals("7",Eval2.eval(factory,0));
+            }
         String src="struct Counter { int x; int y; int z; new Counter={int n -> while(x<n) { int old=x; y=x+1; x=y+1; z=old; }}; }; val c=new Counter(arg); return c.x*100+c.z;";
         CodeGen code=new CodeGen(src).driver(CodeGen.Phase.LocalSched);
         assertEquals("2018",Eval2.eval(code,19));
diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/TypeTest.java b/chapter28b/src/test/java/com/seaofnodes/simple/TypeTest.java
index bb08b5ac..b4055eef 100644
--- a/chapter28b/src/test/java/com/seaofnodes/simple/TypeTest.java
+++ b/chapter28b/src/test/java/com/seaofnodes/simple/TypeTest.java
@@ -7,6 +7,32 @@ import static org.junit.Assert.assertSame;
 
 public class TypeTest {
 
+    // Aggregate finality is carried by its fields. Canonicalizing the unused
+    // aggregate bit must commute with dual, even for named (non-high) structs.
+    @Test public void testAggregateMemoryDual() {
+        TypeStruct obj = TypeStruct.make("AggregateDual",false,
+            Field.make("x",TypeInteger.BOT,2,false),
+            Field.make("y",TypeInteger.ZERO,3,true));
+        for( Type t : new Type[]{Type.BOTTOM,Type.TOP,TypeStruct.BOT,TypeStruct.TOP,obj,obj.dual()} )
+            for( boolean one : new boolean[]{false,true} ) {
+                TypeMem mem = TypeMem.make(1,t,one,false,false,XInt.EMPTY,XInt.EMPTY);
+                assertSame(mem,TypeMem.make(1,t,one,false,true,XInt.EMPTY,XInt.EMPTY));
+                assertSame(mem,mem.dual().dual());
+                assertSame(mem.dual(),TypeMem.make(1,t.dual(),!one,true,true,XInt.FULL,XInt.FULL));
+            }
+        // Precise field slices still distinguish final and mutable storage.
+        Assert.assertNotEquals(TypeMem.make(2,TypeInteger.BOT,false,false,false,XInt.EMPTY,XInt.EMPTY),
+                               TypeMem.make(2,TypeInteger.BOT,false,false,true ,XInt.EMPTY,XInt.EMPTY));
+        for( boolean one : new boolean[]{false,true} )
+            for( boolean fin : new boolean[]{false,true} ) {
+                TypeMem bulk = TypeMem.make(1,Type.TOP,one,false,false,XInt.EMPTY,XInt.EMPTY);
+                TypeMem slice = TypeMem.make(2,TypeInteger.BOT,false,false,fin,XInt.EMPTY,XInt.EMPTY);
+                assertSame(slice,bulk.meet(slice));
+                check_symmetric(bulk,slice);
+                check_symmetric(bulk.dual(),slice.dual());
+            }
+    }
+
     // Refining an unknown pointer must remove possible escapes, not add them.
     // Inlining can expose the abstract self pointer before its concrete class.
     @Test public void testAbstractPointerEscapes() {