From 68cd11f31dd4ba7f089d1a15de5a36ec67043da6 Mon Sep 17 00:00:00 2001
From: Cliff Click <cliffc@acm.org>
Date: Wed, 13 Nov 2024 13:41:18 -0800
Subject: Final? pass of finals

Add a least-upper-bound to set Phis to their respective Top while preserving final fields.
Requires a ReadOnly node to "cast-away-writable".
Series of isFinal/makeRO in all Types.
Changes tests to match r/w intent.
---
 .../main/java/com/seaofnodes/simple/Parser.java    | 63 ++++++++++++----------
 .../java/com/seaofnodes/simple/node/LoadNode.java  | 15 +++++-
 .../java/com/seaofnodes/simple/node/PhiNode.java   |  2 +-
 .../com/seaofnodes/simple/node/ReadOnlyNode.java   | 29 ++++++++++
 .../com/seaofnodes/simple/node/ScopeMinNode.java   |  4 +-
 .../java/com/seaofnodes/simple/node/ScopeNode.java |  2 +-
 .../java/com/seaofnodes/simple/node/StoreNode.java |  3 ++
 .../java/com/seaofnodes/simple/type/Field.java     | 22 +++++---
 .../main/java/com/seaofnodes/simple/type/Type.java | 26 ++++++---
 .../java/com/seaofnodes/simple/type/TypeFloat.java |  5 +-
 .../com/seaofnodes/simple/type/TypeInteger.java    |  1 +
 .../java/com/seaofnodes/simple/type/TypeMem.java   |  8 ++-
 .../com/seaofnodes/simple/type/TypeMemPtr.java     |  8 +--
 .../com/seaofnodes/simple/type/TypeStruct.java     | 53 ++++++++++++++----
 14 files changed, 171 insertions(+), 70 deletions(-)
 create mode 100644 chapter17/src/main/java/com/seaofnodes/simple/node/ReadOnlyNode.java

(limited to 'chapter17/src/main/java')

diff --git a/chapter17/src/main/java/com/seaofnodes/simple/Parser.java b/chapter17/src/main/java/com/seaofnodes/simple/Parser.java
index e2f8ad32..09ea21ac 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/Parser.java
@@ -395,7 +395,7 @@ public class Parser {
     }
 
     // Look for an unbalanced `)`, skipping balanced
-    private void skipAsgn() {
+    private Type skipAsgn() {
         int paren=0;
         while( true )
             // Next X char handles skipping complex comments
@@ -403,10 +403,8 @@ public class Parser {
             case Character.MAX_VALUE:
                 throw Utils.TODO();
             case ')':
-                if( --paren<0 ) {
-                    pos(pos()-1); // Leave the `)` behind
-                    return;
-                }
+                if( --paren<0 )
+                    return posT(pos()-1); // Leave the `)` behind
                 break;
             case '(': paren ++; break;
             default: break;
@@ -521,10 +519,12 @@ public class Parser {
         boolean hasType = t!=null && t!=Type.TOP && t!=Type.BOTTOM; // User written type
         boolean hasExpr = !(peek(';') || peek(','));   // Expression follows
         if( hasExpr && !match("=") )                   // Something else
-            { pos(old);  return parseExpression(); }
-        if( !hasExpr && t==Type.BOTTOM )  throw errorSyntax("expression");
+            { pos(old); return parseExpression(); }
+        if( !hasExpr && !hasType )  throw errorSyntax("expression");
         Node expr = hasExpr ? parseExpression() : con(t.makeInit());
-        boolean xfinal = t==Type.TOP || (hasType && hasExpr && !hasBang && _scope.inCon());
+
+        // Final if no Bang AND TMP; primitives are not-final by default
+        boolean xfinal = !hasBang && (t instanceof TypeMemPtr) && hasExpr;
 
         // Defining a new variable vs updating an old one
         if( t==null ) {
@@ -538,11 +538,19 @@ public class Parser {
             if( _scope.in(def._idx)._type!=Type.TOP && def._final && !_scope.inCon() )
                 throw error("Cannot reassign final '"+name+"'");
             t = def.type(); // Declared field type
-        } else if( !hasType && hasExpr ) {
-            // Discovered type from expression
+
+        } else if( !hasType && hasExpr ) { // Either 'val' or 'var'
+            // Either 'var' or 'val'; type comes from expression
+            xfinal = t==Type.TOP; // xfinal === 'val'; otherwise 'var'
             t = expr._type.glb();
         }
 
+        // Final is deep on ptrs
+        if( xfinal && t instanceof TypeMemPtr tmp ) {
+            t = tmp.makeRO();
+            expr = peep(new ReadOnlyNode(expr));
+        }
+
         // Auto-widen int to float
         if( expr._type instanceof TypeInteger && t instanceof TypeFloat )
             expr = peep(new ToFloatNode(expr));
@@ -550,15 +558,13 @@ public class Parser {
         expr = zsMask(expr,t);
         // Auto-deepen forward ref types
         Type e = expr._type;
-        if( e instanceof TypeMemPtr tmp && tmp._obj._fields==null )
+        if( e instanceof TypeMemPtr tmp && tmp.isFRef() )
             e = TYPES.get(tmp._obj._name);
-        // "var" and "val" use TOP and BOTTOM - but just take the expression type.
-        if( t==Type.TOP || t==Type.BOTTOM )
-            t = expr._type.glb();
         // Type is sane
         if( !e.isa(t) )
             throw error("Type " + e.str() + " is not of declared type " + t.str());
 
+        // Define a new name, vs update an old one
         if( isDecl ) {
             if( !_scope.define(name,t,xfinal,expr) )
                 throw error("Redefining name '" + name + "'");
@@ -612,7 +618,7 @@ public class Parser {
         if (_xScopes.size() > 1) throw errorSyntax("struct declarations can only appear in top level scope");
         String typeName = requireId();
         Type t = TYPES.get(typeName);
-        if( t!=null && !(t instanceof TypeMemPtr tmp && tmp._obj._fields==null) )
+        if( t!=null && !(t instanceof TypeMemPtr tmp && tmp.isFRef() ) )
             throw errorSyntax("struct '" + typeName + "' cannot be redefined");
 
         // A Block scope parse, and inspect the scope afterward for fields.
@@ -646,6 +652,8 @@ public class Parser {
     // 'id' which the caller must parse.  This lets us distinguish forward ref
     // types (which ARE valid here) from local vars in an (optional) forward
     // ref type position.
+
+    // t = int|i8|i16|i32|i64|u8|u16|u32|u64|byte|bool | flt|f32|f64 | val | var | struct[?]
     private Type type() {
         int old1 = pos();
         String tname = _lexer.matchId();
@@ -654,7 +662,7 @@ public class Parser {
         Type t0 = TYPES.get(tname);
         // No new types as keywords
         if( t0 == null && KEYWORDS.contains(tname) )
-            { pos(old1); return null; }
+            return posT(old1);
         Type t1 = t0 == null ? TypeMemPtr.make(TypeStruct.makeFRef(tname)) : t0; // Null: assume a forward ref type
         // Nest arrays and '?' as needed
         while( true ) {
@@ -680,10 +688,8 @@ public class Parser {
         int old2 = pos();
         String id = _lexer.matchId();
         pos(old2);              // Reset lexer to reparse
-        if( id==null ) {
-            pos(old1);          // Reset lexer to reparse
-            return null;        // Not a type
-        }
+        if( id==null )
+            return posT(old1);  // Reset lexer to reparse
         // Yes a forward ref, so declare it
         TYPES.put(tname,t1);
         return t1;
@@ -853,7 +859,7 @@ public class Parser {
                 if( n != null ) {
                     if( n._final )
                         throw error("Cannot reassign final '"+n._name+"'");
-                    Node expr = peep(new AddNode(_scope.in(n),con(delta)));
+                    Node expr = zsMask(peep(new AddNode(_scope.in(n),con(delta))),n.type());
                     _scope.update(n,expr);
                     return expr;
                 }
@@ -887,7 +893,7 @@ public class Parser {
         if( matchx("++") || matchx("--") ) {
             if( n._final )
                 throw error("Cannot reassign final '"+n._name+"'");
-            _scope.update(n,peep(new AddNode(rvalue,con( _lexer.peek(-1)=='+' ? 1 : -1))));
+            _scope.update(n,zsMask(peep(new AddNode(rvalue,con( _lexer.peek(-1)=='+' ? 1 : -1))),n.type()));
         }
         return rvalue.unkeep();
     }
@@ -1025,7 +1031,7 @@ public class Parser {
 
         // Sanity check field name for existing
         TypeMemPtr tmp = (TypeMemPtr)TYPES.get(ptr._obj._name);
-        if( tmp == null ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'");
+        if( tmp == null ) throw error("Accessing unknown field '" + name + "' from '" + ptr + "'");
         TypeStruct base = tmp._obj;
         int fidx = base.find(name);
         if( fidx == -1 ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'");
@@ -1053,28 +1059,28 @@ public class Parser {
             return val.unkeep();        // "obj.a = expr" returns the expression while updating memory
         }
 
-        Node load = new LoadNode(name, f._alias, f._type.glb(), memAlias(f._alias), expr, off);
+        Node load = new LoadNode(name, f._alias, f._type.glb(), memAlias(f._alias), expr.keep(), off);
         // Arrays include control, as a proxy for a safety range check
         // Structs don't need this; they only need a NPE check which is
         // done via the type system.
         if( base.isAry() ) load.setDef(0,ctrl());
         load = peep(load);
 
-        // ary[idx]++
+        // ary[idx]++ or ptr.fld++
         if( matchx("++") || matchx("--") ) {
             if( f._final && !f._fname.equals("[]") )
                 throw error("Cannot reassign final '"+f._fname+"'");
             Node inc = peep(new AddNode(load,con( _lexer.peek(-1)=='+' ? 1 : -1)));
             Node val = zsMask(inc,f._type);
-            Node st = new StoreNode(name, f._alias, f._type, memAlias(f._alias), expr, off, val, false);
+            Node st = new StoreNode(name, f._alias, f._type, memAlias(f._alias), expr.unkeep(), off, val, false);
             // Arrays include control, as a proxy for a safety range check.
             // Structs don't need this; they only need a NPE check which is
             // done via the type system.
             if( base.isAry() )  st.setDef(0,ctrl());
             memAlias(f._alias, peep(st));
             // And use the original loaded value as the result
-        }
-        if( off.unkeep().isDead() ) off.kill();
+        } else expr.unkill();
+        off.unkill();
 
         return parsePostfix(load);
     }
@@ -1134,6 +1140,7 @@ public class Parser {
         _lexer._position = pos;
         return old;
     }
+    private Type posT(int pos) { _lexer._position = pos; return null; }
 
     // Require and return an identifier
     private String requireId() {
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/LoadNode.java
index 555b9ae4..1528f2e9 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/node/LoadNode.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/node/LoadNode.java
@@ -63,13 +63,15 @@ public class LoadNode extends MemOpNode {
         // Load-after-Store on same address, but bypassing provably unrelated
         // stores.  This is a more complex superset of the above two peeps.
         // "Provably unrelated" is really weak.
+        if( ptr instanceof ReadOnlyNode ro )
+            ptr = ro.in(1);
         Node mem = mem();
         outer:
         while( true ) {
             switch( mem ) {
             case StoreNode st:
                 if( ptr == st.ptr() && off() == st.off() )
-                    return st.val(); // Proved equal
+                    return castRO(st.val()); // Proved equal
                 // Can we prove unequal?  Offsets do not overlap?
                 if( !off()._type.join(st.off()._type).isHigh() && // Offsets overlap
                     !neverAlias(ptr,st.ptr()) )                   // And might alias
@@ -82,7 +84,7 @@ public class LoadNode extends MemOpNode {
             case ProjNode mproj:
                 if( mproj.in(0) instanceof NewNode nnn1 ) {
                     if( ptr instanceof ProjNode pproj && pproj.in(0) == mproj.in(0) )
-                        return nnn1.in(nnn1.findAlias(_alias)); // Load from New init
+                        return castRO(nnn1.in(nnn1.findAlias(_alias))); // Load from New init
                     if( !(ptr instanceof ProjNode pproj && pproj.in(0) instanceof NewNode nnn2) )
                         break outer; // Cannot tell, ptr not related to New
                     mem = nnn1.in(_alias);// Bypass unrelated New
@@ -120,10 +122,12 @@ public class LoadNode extends MemOpNode {
 
         return null;
     }
+
     private Node ld( int idx ) {
         Node mem = mem(), ptr = ptr();
         return new LoadNode(_name,_alias,_declaredType,mem.in(idx),ptr instanceof PhiNode && ptr.in(0)==mem.in(0) ? ptr.in(idx) : ptr, off()).peephole();
     }
+
     private static boolean neverAlias( Node ptr1, Node ptr2 ) {
         return ptr1.in(0) != ptr2.in(0) &&
             // Unrelated allocations
@@ -158,4 +162,11 @@ public class LoadNode extends MemOpNode {
         if( px instanceof StoreNode st1 && ptr()==st1.ptr() && off()==st1.off() ) { px.addDep(this); return true; }
         return false;
     }
+
+    // Read-Only is a deep property, and cannot be cast-away
+    private Node castRO(Node rez) {
+        if( ptr()._type.isFinal() && !rez._type.isFinal() )
+            return new ReadOnlyNode(rez).peephole();
+        return rez;
+    }
 }
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index 58ce6b47..cb266ca3 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -47,7 +47,7 @@ public class PhiNode extends Node {
         // During parsing Phis have to be computed type pessimistically.
         if( r.inProgress() ) return _declaredType;
         // Set type to local top of the starting type
-        Type t = _declaredType.glb().dual();
+        Type t = _declaredType.lub();
         for (int i = 1; i < nIns(); i++)
             // If the region's control input is live, add this as a dependency
             // to the control because we can be peeped should it become dead.
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/ReadOnlyNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/ReadOnlyNode.java
new file mode 100644
index 00000000..fddcaa67
--- /dev/null
+++ b/chapter17/src/main/java/com/seaofnodes/simple/node/ReadOnlyNode.java
@@ -0,0 +1,29 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeMemPtr;
+
+import java.util.BitSet;
+
+/**
+ * Cast a pointer to read-only
+ */
+public class ReadOnlyNode extends Node {
+    public ReadOnlyNode( Node n ) { super(null,n); }
+    @Override public String label() { return "ReadOnly"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        return in(1)._print0(sb.append("(const)"),visited);
+    }
+    @Override public Type compute() {
+        Type t = in(1)._type;
+        return t instanceof TypeMemPtr tmp ? tmp.makeRO() : t;
+    }
+
+    @Override public Node idealize() {
+        if( in(1)._type instanceof TypeMemPtr tmp && tmp.isFinal() )
+            return in(1);
+        return null;
+    }
+}
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java
index c51349fa..1cff690c 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java
@@ -29,12 +29,12 @@ public class ScopeMinNode extends Node {
             Type def = Parser.TYPES.get(((TypeMemPtr)_type)._obj._name);
             return (_type=_type.meet(def));
         }
-        public Type glb() {
+        public Type lazyGLB() {
             Type t = type();
             return t instanceof TypeMemPtr ? t : t.glb();
         }
         @Override public String toString() {
-            return _type.toString()+(_final ? " !": " ")+_name;
+            return _type.toString()+(_final ? " ": " !")+_name;
         }
     }
 
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
index 5a735515..bfb6eed6 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -167,7 +167,7 @@ public class ScopeNode extends ScopeMinNode {
                 // Set real Phi in the loop head
                 // The phi takes its one input (no backedge yet) from a recursive
                 // lookup, which might have insert a Phi in every loop nest.
-                : loop.setDef(v._idx,new PhiNode(v._name, v.glb(), loop.ctrl(), loop.in(loop.update(v,null)._idx),null).peephole());
+                : loop.setDef(v._idx,new PhiNode(v._name, v.lazyGLB(), loop.ctrl(), loop.in(loop.update(v,null)._idx),null).peephole());
             setDef(v._idx,old);
         }
         if( st!=null ) setDef(v._idx,st); // Set new value
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/StoreNode.java
index 8e3e6693..62b49a1a 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/node/StoreNode.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/node/StoreNode.java
@@ -114,6 +114,9 @@ public class StoreNode extends MemOpNode {
     String err() {
         String err = super.err();
         if( err != null ) return err;
+        TypeMemPtr tmp = (TypeMemPtr)ptr()._type;
+        if( tmp._obj.field(_name)._final )
+            return "Cannot modify final field '"+_name+"'";
         Type t = val()._type;
         return _init || t.isa(_declaredType) ? null : "Cannot store "+t+" into field "+_declaredType+" "+_name;
     }
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/type/Field.java b/chapter17/src/main/java/com/seaofnodes/simple/type/Field.java
index e2c0aa59..349c1fb0 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/type/Field.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/type/Field.java
@@ -31,8 +31,10 @@ public class Field extends Type {
         return new Field(fname,type,alias,xfinal).intern();
     }
     public Field makeFrom( Type type ) {
-        return new Field(_fname,type,_alias,_final).intern();
+        return type == _type ? this : new Field(_fname,type,_alias,_final).intern();
     }
+    @Override public Field makeRO() { return _final ? this : make(_fname,_type.makeRO(),_alias,true);  }
+    @Override public boolean isFinal() { return _final && _type.isFinal(); }
 
     public static final Field TEST = make("test",TypeInteger.ZERO,-2,false);
     public static void gather(ArrayList<Type> ts) { ts.add(TEST); }
@@ -41,16 +43,20 @@ public class Field extends Type {
         Field fld = (Field)that; // Invariant
         assert _fname.equals(fld._fname);
         assert _alias==fld._alias;
-        assert _final==fld._final;
-        return make(_fname,_type.meet(fld._type),_alias,_final);
+        return make(_fname,_type.meet(fld._type),_alias,_final | fld._final);
     }
 
     @Override
-    public Field dual() { return make(_fname,_type.dual(),_alias,_final); }
+    public Field dual() { return make(_fname,_type.dual(),_alias,!_final); }
 
-    @Override
-    public Field glb() {
-        return make(_fname,_type.glb(),_alias,_final);
+    @Override public Field glb() {
+        Type glb = _type.glb();
+        return glb==_type ? this : make(_fname,glb,_alias,_final);
+    }
+
+    @Override public Field lub() {
+        Type lub = _type.lub();
+        return lub==_type ? this : make(_fname,lub,_alias,_final);
     }
 
     // Override in subclasses
@@ -64,7 +70,7 @@ public class Field extends Type {
 
     @Override
     public StringBuilder print( StringBuilder sb ) {
-        return _type.print(sb.append(_final?"!":"").append(_fname).append(":").append(_alias).append(" : "));
+        return _type.print(sb.append(_final?"":"!").append(_fname).append(":").append(_alias).append(" : "));
     }
 
     @Override public String str() { return _fname; }
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter17/src/main/java/com/seaofnodes/simple/type/Type.java
index e454f48f..84b0119a 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/type/Type.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/type/Type.java
@@ -81,9 +81,6 @@ public class Type {
      */
     public StringBuilder typeName( StringBuilder sb) { return print(sb); }
 
-    public Type makeInit() { return null; }
-    public Type makeZero() { return null; }
-    public Type nonZero() { return glb(); }
 
     // ----------------------------------------------------------
 
@@ -175,14 +172,29 @@ public class Type {
     // True if this "isa" t; e.g. 17 isa TypeInteger.BOT
     public boolean isa( Type t ) { return meet(t)==t; }
 
-    /**
-     * Compute greatest lower bound in the lattice
-     */
-    public Type glb() { return _type==TCTRL ? XCONTROL : BOTTOM; }
+    /** Compute greatest lower bound in the lattice */
+    public Type glb() { return _type==TCTRL ? CONTROL : BOTTOM; }
+    /** Compute least upper bound in the lattice */
+    public Type lub() { return _type==TCTRL ? XCONTROL : TOP; }
+
+    // Make an initial/default version of this type.  Typically, 0 for integers
+    // and null for nullable pointers.
+    public Type makeInit() { return null; }
+    // Make a zero version of this type, 0 for integers and null for pointers.
+    public Type makeZero() { return null; }
+    // Make a non-zero version of this type, if possible.  Integers attempt to
+    // exclude zero from their range and pointers become not-null.
+    public Type nonZero() { return glb(); }
 
     // Is forward-reference
     public boolean isFRef() { return false; }
 
+    // All reachable struct Fields are final
+    public boolean isFinal() { return true; }
+
+    // Make all reachable struct Fields final
+    public Type makeRO() { return this; }
+
     // ----------------------------------------------------------
 
     // Size in bits to hold an instance of this type.
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/type/TypeFloat.java b/chapter17/src/main/java/com/seaofnodes/simple/type/TypeFloat.java
index 37f6ce71..f85abbed 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/type/TypeFloat.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/type/TypeFloat.java
@@ -104,9 +104,8 @@ public class TypeFloat extends Type {
         return make((byte)-_sz,0);
     }
 
-    @Override
-    public Type glb() { return BOT; }
-
+    @Override public Type glb() { return BOT; }
+    @Override public Type lub() { return TOP; }
     @Override public TypeFloat makeInit() { return ZERO; }
     @Override public TypeFloat makeZero() { return ZERO; }
 
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter17/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
index 06848dc7..b2979d7b 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
@@ -115,6 +115,7 @@ public class TypeInteger extends Type {
 
     @Override public TypeInteger dual() { return make(_max,_min); }
     @Override public TypeInteger glb() { return BOT; }
+    @Override public TypeInteger lub() { return TOP; }
     @Override public TypeInteger makeInit() { return ZERO; }
     @Override public TypeInteger makeZero() { return ZERO; }
     @Override public TypeInteger nonZero() {
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/chapter17/src/main/java/com/seaofnodes/simple/type/TypeMem.java
index 32491a11..33c6a8ce 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/type/TypeMem.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/type/TypeMem.java
@@ -21,7 +21,7 @@ public class TypeMem extends Type {
     private TypeMem(int alias, Type t) { super(TMEM); _alias = alias; _t = t; }
 
     public static TypeMem make(int alias, Type t) { return new TypeMem(alias,t).intern(); }
-    public static final TypeMem TOP = make( 0, Type.TOP);
+    public static final TypeMem TOP = make(-1, Type.TOP   );
     public static final TypeMem BOT = make(-1, Type.BOTTOM);
 
     public static void gather(ArrayList<Type> ts) { ts.add(make(1,TypeInteger.ZERO)); ts.add(BOT); }
@@ -40,13 +40,11 @@ public class TypeMem extends Type {
 
     @Override
     public Type dual() {
-        if( _alias== 0 ) return BOT;
-        if( _alias==-1 ) return TOP;
         return make(_alias,_t.dual());
     }
 
-    @Override
-    public Type glb() { return make(_alias,_t.glb()); }
+    @Override public Type glb() { return make(_alias,_t.glb()); }
+    @Override public Type lub() { return make(_alias,_t.lub()); }
 
     @Override
     int hash() { return 9876543 + _alias + _t.hashCode(); }
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/chapter17/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java
index cc4b9fcd..08e7db1c 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java
@@ -33,7 +33,9 @@ public class TypeMemPtr extends Type {
     }
     public static TypeMemPtr make(TypeStruct obj, boolean nil) { return new TypeMemPtr(obj, nil).intern(); }
     public static TypeMemPtr make(TypeStruct obj) { return make(obj, false); }
-    public TypeMemPtr makeFrom(TypeStruct obj) { return make(obj, _nil); }
+    public TypeMemPtr makeFrom(TypeStruct obj) { return obj==_obj ? this : make(obj, _nil); }
+    @Override public TypeMemPtr makeRO() { return makeFrom(_obj.makeRO()); }
+    @Override public boolean isFinal() { return _obj.isFinal(); }
 
     // An abstract pointer, pointing to either a Struct or an Array.
     // Can also be null or not.
@@ -55,8 +57,8 @@ public class TypeMemPtr extends Type {
     @Override
     public TypeMemPtr dual() { return TypeMemPtr.make(_obj.dual(), !_nil); }
 
-    @Override
-    public TypeMemPtr glb() { return make(_obj.glb(),true); }
+    @Override public TypeMemPtr glb() { return make(_obj.glb(),true ); }
+    @Override public TypeMemPtr lub() { return make(_obj.lub(),false); }
     // Is forward-reference
     @Override public boolean isFRef() { return _obj.isFRef(); }
     @Override public Type makeInit() { return _nil ? NULLPTR : Type.TOP; }
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/chapter17/src/main/java/com/seaofnodes/simple/type/TypeStruct.java
index 39011ce2..b3dbcad0 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/type/TypeStruct.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/type/TypeStruct.java
@@ -37,20 +37,28 @@ public class TypeStruct extends Type {
     public static final TypeStruct TEST = make("test",new Field[]{Field.TEST});
     // Forward-ref version
     public static TypeStruct makeFRef(String name) { return make(name, (Field[])null); }
+    // Make a read-only version
+    @Override public TypeStruct makeRO() {
+        if( isFinal() ) return this;
+        Field[] flds = new Field[_fields.length];
+        for( int i=0; i<flds.length; i++ )
+            flds[i] = _fields[i].makeRO();
+        return make(_name,flds);
+    }
 
     // Array
     public static TypeStruct makeAry(TypeInteger len, int lenAlias, Type body, int bodyAlias) {
         assert !(body instanceof TypeMemPtr tmp && !tmp._nil);
         return make("[" + body.str() + "]",
-                    Field.make("#" ,len , lenAlias,true),
-                    Field.make("[]",body,bodyAlias,true));
+                    Field.make("#" ,len , lenAlias,true ),
+                    Field.make("[]",body,bodyAlias,false));
     }
 
     // A pair of self-cyclic types
     private static final TypeStruct S1F = makeFRef("S1");
     private static final TypeStruct S2F = makeFRef("S2");
-    public  static final TypeStruct S1  = make("S1", new Field[]{ Field.make("a", TypeInteger.BOT, -1, false), Field.make("s2",TypeMemPtr.make(S2F,false),-2, false) });
-    private static final TypeStruct S2  = make("S2", new Field[]{ Field.make("b", TypeFloat  .BOT, -3, false), Field.make("s1",TypeMemPtr.make(S1F,false),-4, false) });
+    public  static final TypeStruct S1  = make("S1", Field.make("a", TypeInteger.BOT, -1, false), Field.make("s2",TypeMemPtr.make(S2F,false),-2, false) );
+    private static final TypeStruct S2  = make("S2", Field.make("b", TypeFloat  .BOT, -3, false), Field.make("s1",TypeMemPtr.make(S1F,false),-4, false) );
 
     private static final TypeStruct ARY = makeAry(TypeInteger.BOT,-1,TypeFloat.BOT,-2);
 
@@ -63,6 +71,10 @@ public class TypeStruct extends Type {
                 return i;
         return -1;
     }
+    public Field field(String fname) {
+        int idx = find(fname);
+        return idx== -1 ? null : _fields[idx];
+    }
 
     // Find field index by alias
     public int findAlias( int alias ) {
@@ -115,8 +127,7 @@ public class TypeStruct extends Type {
     }
 
     // Keeps the same struct, but lower-bounds all fields.
-    @Override
-    public TypeStruct glb() {
+    @Override public TypeStruct glb() {
         if( _glb() ) return this;
         // Need to glb each field
         Field[] flds = new Field[_fields.length];
@@ -131,9 +142,33 @@ public class TypeStruct extends Type {
                  return false;
         return true;
     }
+    @Override public TypeStruct lub() {
+        if( _lub() ) return this;
+        // Need to glb each field
+        Field[] flds = new Field[_fields.length];
+        for( int i=0; i<_fields.length; i++ )
+            flds[i] = _fields[i].lub();
+        return make(_name,flds);
+    }
+    private boolean _lub() {
+        if( _fields!=null )
+          for( Field f : _fields )
+              if( f.lub() != f )
+                 return false;
+        return true;
+    }
+
 
     // Is forward-reference
     @Override public boolean isFRef() { return _fields==null; }
+    // All fields are final
+    @Override public boolean isFinal() {
+        if( _fields==null ) return true;
+        for( Field fld : _fields )
+            if( !fld.isFinal() )
+                return false;
+        return true;
+    }
 
     @Override
     boolean eq(Type t) {
@@ -164,10 +199,8 @@ public class TypeStruct extends Type {
         sb.append(_name);
         if( _fields == null ) return sb; // Forward reference struct, just print the name
         sb.append(" {");
-        for( Field f : _fields ) {
-            sb.append("  ").append(f._fname).append(" :");
-            f._type.print(sb).append("; ");
-        }
+        for( Field f : _fields )
+            f._type.print(sb).append(f._final ? " " : " !").append(f._fname).append("; ");
         return sb.append("}");
     }
 
-- 
cgit v1.2.3