Chapter 12: References

Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: tannal <tannal2409@gmail.com>
Co-authored-by: hadha <helsgithub15@gmail.com>
Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
Co-authored-by: Symious <14933944+symious@users.noreply.github.com>
Co-authored-by: RobertObkircher <robert.obkircher@gmail.com>
Co-authored-by: Robert Obkircher <robert.obkircher@gmail.com>
Co-authored-by: Claude Opus 5 <noreply@anthropic.com>

12 files changed, 155 insertions, 111 deletions

diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java
index df8d0b1c..a25edeb1 100644
--- a/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/src/main/java/com/seaofnodes/simple/Parser.java
@@ -82,14 +82,15 @@ public class Parser {
     ScopeNode _continueScope;
     ScopeNode _breakScope;
 
-    // Mapping from a Struct name to a Struct.
-    public static Map<String, TypeStruct> OBJS = new HashMap<>();
+    // Authoritative declarations, indexed by type name.
+    public static HashMap<String, Type> TYPES = new HashMap<>();
 
     public Parser(String source, TypeInteger arg) {
         PARSER = this;
         Node.reset();
         IterPeeps.reset();
-        OBJS.clear();
+        TYPES.clear();
+        TYPES.put("int",TypeInteger.BOT);
         _lexer = new Lexer(source);
         _scope = new ScopeNode();
         _continueScope = _breakScope = null;
@@ -121,6 +122,8 @@ public class Parser {
         _scope.define(ScopeNode.ARG0, TypeInteger.BOT, new ProjNode(START, 2, ScopeNode.ARG0).peephole());
         _scope.define("$mem", TypeMem.BOT, new ProjNode(START, 1, "$mem").peephole());
         parseBlock();
+        if( ctrl()._type==Type.CONTROL )
+            STOP.addReturn(new ReturnNode(ctrl(), new ConstantNode(TypeInteger.constant(0)).peephole(), _scope).peephole());
         _scope.pop();
         _xScopes.pop();
         if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken());
@@ -158,7 +161,6 @@ public class Parser {
     private Node parseStatement() {
         if( false ) return null;
         else if (matchx("return")  ) return parseReturn();
-        else if (matchx("int")     ) return parseDecl(TypeInteger.BOT);
         else if (match ("{")       ) return require(parseBlock(),"}");
         else if (matchx("if")      ) return parseIf();
         else if (matchx("while")   ) return parseWhile();
@@ -174,40 +176,42 @@ public class Parser {
     /**
      * Parse a struct field.
      * <pre>
-     *     int IDENTIFIER ;
+     *     type IDENTIFIER ;
      * </pre>
      */
-    private Field parseField(String sname) {
-        if( matchx("int") )     // Currently only parsing "int" type fields
-            return require(Field.make(requireId().intern(),TypeInteger.BOT),";");
-        throw errorSyntax("A field type is expected, only type 'int' is supported at present");
+    private Field parseField() {
+        Type t = type();
+        if( t==null )
+            throw errorSyntax("Requires a field type, found '"+_lexer.getAnyNextToken()+"'");
+        return require(Field.make(requireId().intern(),t),";");
     }
 
     /**
-     * Parse a struct declaration, and return the following statement.
+     * Parse a complete struct declaration.
      * Only allowed in top level scope.
      * Structs cannot be redefined.
      *
-     * @return The statement following the struct
+     * @return null
      */
     private Node parseStruct() {
         if (_xScopes.size() > 1) throw errorSyntax("struct declarations can only appear in top level scope");
         String typeName = requireId();
-        if ( OBJS.containsKey(typeName)) throw errorSyntax("struct '" + typeName + "' cannot be redefined");
+        Type t = TYPES.get(typeName);
+        if( t!=null && !(t instanceof TypeStruct ts && ts._fields==null) ) throw errorSyntax("struct '" + typeName + "' cannot be redefined");
         ArrayList<Field> fields = new ArrayList<>();
         require("{");
         while (!peek('}') && !_lexer.isEOF()) {
-            Field field = parseField(typeName);
+            Field field = parseField();
             if (fields.contains(field)) throw errorSyntax("Field '" + field + "' already defined in struct '" + typeName + "'");
             fields.add(field);
         }
         require("}");
         // Build and install the TypeStruct
         TypeStruct ts = TypeStruct.make(typeName, fields);
+        TYPES.put(typeName, ts); // Insert the struct name in the collection of all struct names
         _aliases.put(typeName,_alias);
         _alias += ts._fields.length;
-        OBJS.put(typeName, ts); // Insert the struct name in the collection of all struct names
-        return parseStatement();
+        return null;
     }
 
     /**
@@ -349,8 +353,8 @@ public class Parser {
         // Parse the false side
         _scope = fScope;        // Restore scope, then parse else block if any
         ifF.unkeep();           // fScope already owns the false control
+        _scope.upcast(ifF,pred,true); // Up-cast predicate, also without an else
         if (matchx("else")) {
-            _scope.upcast(ifF,pred,true); // Up-cast predicate
             parseStatement();
             fScope = _scope;
         }
@@ -418,15 +422,18 @@ public class Parser {
             if( _scope.define(name,t,expr) == null )
                 throw error("Redefining name '" + name + "'");
         } else {
-            Node n = _scope.lookup(name);
-            t = _scope.lookupDeclaredType(name);
-            if( n==null )
+            if( _scope.lookup(name)==null )
                 throw error("Undefined name '" + name + "'");
-            _scope.update(name,expr);
+            t = _scope.lookupDeclaredType(name);
         }
-        if( !expr._type.isa(t) )
-            throw error("Type " + expr._type.str() + " is not of declared type " + t.str());
-        return expr;
+        // Auto-deepen forward ref types
+        Type e = expr._type;
+        if( e instanceof TypeMemPtr tmp && tmp._obj._fields==null )
+            e = tmp.make_from((TypeStruct)TYPES.get(tmp._obj._name));
+        // Type is sane
+        if( !e.isa(t) )
+            throw error("Type " + e.str() + " is not of declared type " + t.str());
+        return _scope.update(name,expr);
     }
 
     // Parse a type-or-null
@@ -434,38 +441,22 @@ public class Parser {
         int old = _lexer._position;
         String tname = _lexer.matchId();
         if( tname==null ) return null;
-        if( tname.equals("int") ) return TypeInteger.BOT;
-        TypeStruct obj = OBJS.get(tname);
-        if( obj != null )
-            return TypeMemPtr.make(obj,match("?"));
-        // Not a type; unwind the parse
-        _lexer._position = old;
-        return null;
-    }
-
-    /**
-     * Parses a declStatement
-     *
-     * <pre>
-     *     type name = expression ';'
-     * </pre>
-     * @return an expression {@link Node}
-     */
-    private Node parseDecl(Type t) {
-        var name = requireId();
-        var expr = match(";")
-            // Assign a null value
-            ? new ConstantNode(t.makeInit()).peephole()
-            // Assign "= expr;"
-            : require(require("=").parseExpression(), ";");
-        if( !expr._type.isa(t) )
-            throw error("Type " + expr._type.str() + " is not of declared type " + t.str());
-        if( _scope.define(name,t,expr) == null )
-            throw error("Redefining name '" + name + "'");
-        return expr;
+        boolean nullable = match("?");
+        Type t = TYPES.get(tname);
+        // Assume a forward-reference type
+        if( t == null ) {
+            int old2 = _lexer._position;
+            String id = _lexer.matchId();
+            if( id==null ) {
+                _lexer._position = old;
+                return null;
+            }
+            TYPES.put(tname,t = TypeStruct.make(tname));
+            _lexer._position = old2; // Reparse ID in caller
+        }
+        return t instanceof TypeStruct obj ? TypeMemPtr.make(obj,nullable) : t;
     }
 
-
     /**
      * Parse an expression of the form:
      *
@@ -571,15 +562,16 @@ public class Parser {
      * @return a primary {@link Node}, never {@code null}
      */
     private Node parsePrimary() {
-        if( _lexer.isNumber() ) return parseIntegerLiteral();
+        if( _lexer.isNumber(_lexer.peek()) ) return parseIntegerLiteral();
         if( match("(") ) return require(parseExpression(), ")");
         if( matchx("true" ) ) return new ConstantNode(TypeInteger.constant(1)).peephole();
-        if( matchx("false") ) return new ConstantNode(TypeInteger.constant(0)).peephole();
+        if( matchx("false") ) return new ConstantNode(TypeInteger.ZERO).peephole();
         if( matchx("null" ) ) return new ConstantNode(TypeMemPtr.NULLPTR).peephole();
         if( matchx("new") ) {
             String structName = requireId();
-            TypeStruct obj = OBJS.get(structName);
-            if( obj == null) throw errorSyntax("Unknown struct type '" + structName + "'");
+            Type t = TYPES.get(structName);
+            if( !(t instanceof TypeStruct obj) || obj._fields==null )
+                throw error("Unknown struct type '" + structName + "'");
             return newStruct(obj);
         }
         String name = _lexer.matchId();
@@ -592,12 +584,11 @@ public class Parser {
     /**
      * Return a NewNode but also generate instructions to initialize it.
      */
-    private Node newStruct( TypeStruct obj ) {
+    private Node newStruct(TypeStruct obj) {
         Node n = new NewNode(TypeMemPtr.make(obj), ctrl()).peephole().keep();
-        Node initValue = new ConstantNode(TypeInteger.constant(0)).peephole();
         int alias = _aliases.get(obj._name);
         for( Field field : obj._fields ) {
-            store(field._fname,alias,n,initValue);
+            store(field._fname,alias,field._type,n,new ConstantNode(field._type.makeInit()).peephole(),true);
             alias++;
         }
         return n.unkeep();
@@ -607,9 +598,9 @@ public class Parser {
     private Node mem() { return _scope.lookup("$mem"); }
     private Node mem(Node n) { return _scope.update("$mem",n); }
 
-    private void store(String name, int alias, Node ptr, Node val) {
+    private void store(String name, int alias, Type glb, Node ptr, Node val, boolean init) {
         Node prior = mem().keep();
-        Node st = new StoreNode(name,alias,prior,ptr,val).peephole();
+        Node st = new StoreNode(name,alias,glb,null,prior,ptr,val,init).peephole();
         mem(new MemMergeNode(prior,alias,st).peephole());
         if( prior.unkeep().isUnused() ) prior.kill();
     }
@@ -629,7 +620,10 @@ public class Parser {
             throw error("Expected struct reference but got " + expr._type.str());
 
         String name = requireId().intern();
-        int idx = ptr._obj==null ? -1 : ptr._obj.find(name);
+        if( expr._type == TypeMemPtr.TOP ) throw error("Accessing field '" + name + "' from null");
+        if( ptr._obj == null ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'");
+        TypeStruct base = (TypeStruct)TYPES.get(ptr._obj._name);
+        int idx = base==null ? -1 : base.find(name);
         if( idx == -1 ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'");
         int alias = _aliases.get(ptr._obj._name)+idx;
 
@@ -638,13 +632,14 @@ public class Parser {
             if( peek('=') ) _lexer._position--;
             else {
                 Node val = parseExpression();
-                store(name,alias,expr,val);
+                Type glb = base._fields[idx]._type;
+                store(name,alias,glb,expr,val,false);
                 return expr;        // "obj.a = expr" returns the expression while updating memory
             }
         }
 
-        Type declaredType = ptr._obj._fields[idx]._type;
-        return parsePostfix(new LoadNode(name, alias, declaredType, mem(), expr).peephole());
+        Type declaredType = base._fields[idx]._type;
+        return parsePostfix(new LoadNode(name, alias, declaredType.glb(), mem(), expr).peephole());
     }
 
     /**
diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java
index e235d288..e993a20e 100644
--- a/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -168,4 +168,9 @@ public class AddNode extends Node {
     }
 
     @Override Node copy(Node lhs, Node rhs) { return new AddNode(lhs,rhs); }
+    @Override public String err() {
+        if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(1)._type;
+        if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(2)._type;
+        return null;
+    }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java
index 9bf36459..b2ee6939 100644
--- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java
@@ -14,7 +14,6 @@ import com.seaofnodes.simple.type.Field;
  */
 public class LoadNode extends MemOpNode {
 
-    Type _declaredType;
     /**
      * Load a value from a ptr.field.
      *
@@ -23,12 +22,11 @@ public class LoadNode extends MemOpNode {
      * @param memPtr The ptr to the struct from where we load a field
      */
     public LoadNode(String name, int alias, Type glb, Node memSlice, Node memPtr) {
-        super(name, alias, memSlice, memPtr, null);
-        _declaredType = glb;
+        super(name, alias, glb, null, memSlice, memPtr);
     }
 
     @Override boolean canDrop(MemOpNode other, Node dep) {
-        return super.canDrop(other,dep) && _declaredType==((LoadNode)other)._declaredType && !clobbered(dep);
+        return super.canDrop(other,dep) && !clobbered(dep);
     }
 
     // Check only immediate memory users. Stores clobber memory; Phis and
diff --git a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
index 44304bcb..7c6afb0c 100644
--- a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
@@ -11,11 +11,14 @@ public abstract class MemOpNode extends Node {
 
     public final String _name;
     public final int _alias;
+    public final Type _declaredType;
 
-    public MemOpNode(String name, int alias, Node memSlice, Node memPtr, Node value) {
-        super(null, memSlice, memPtr, value);
+
+    public MemOpNode(String name, int alias, Type glb, Node... nodes ) {
+        super(nodes);
         _name  = name;
         _alias = alias;
+        _declaredType = glb;
     }
 
     public Node mem() { return in(1); }
@@ -25,7 +28,7 @@ public abstract class MemOpNode extends Node {
     // The caller has already checked the opcode, input shape and control.
     boolean canDrop(MemOpNode other, Node dep) {
         ptr().addDep(dep);
-        return _alias==other._alias && err()==null;
+        return _alias==other._alias && _declaredType==other._declaredType && err()==null;
     }
 
     @Override
diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java
index 5592c52d..b0359a52 100644
--- a/src/main/java/com/seaofnodes/simple/node/MulNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java
@@ -51,4 +51,9 @@ public class MulNode extends Node {
         return null;
     }
     @Override Node copy(Node lhs, Node rhs) { return new MulNode(lhs,rhs); }
+    @Override public String err() {
+        if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(1)._type;
+        if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(2)._type;
+        return null;
+    }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java
index 1d8e23f8..999e38fd 100644
--- a/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -190,6 +190,7 @@ public abstract class Node extends BaseNode<Node> implements Cloneable {
      */
     public void kill( ) {
         unlock();
+        moveDepsToWorklist();
         assert isUnused();      // Has no uses, so it is dead
         _type=null;             // Flag as dead
         while( nIns()>0 ) { // Set all inputs to null, recursively killing unused Nodes
diff --git a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/src/main/java/com/seaofnodes/simple/node/StoreNode.java
index 026d5c50..e9eaaf2e 100644
--- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java
@@ -13,20 +13,26 @@ import com.seaofnodes.simple.type.*;
  */
 public class StoreNode extends MemOpNode {
 
+    private final boolean _init; // Initializing writes are allowed to write null
+
     /**
      * @param name The struct field we are assigning to
      * @param memSlice The memory alias node - this is updated after a Store
      * @param memPtr The ptr to the struct where we will store a value
      * @param value Value to be stored
      */
-    public StoreNode(String name, int alias, Node memSlice, Node memPtr, Node value) {
-        super(name, alias, memSlice, memPtr, value);
+    public StoreNode(String name, int alias, Type glb, Node ctrl, Node memSlice, Node memPtr, Node value, boolean init) {
+        super(name, alias, glb, ctrl, memSlice, memPtr, value);
+        _init = init;
     }
 
-    @Override
-    public String label() { return "Store"; }
-    @Override
-    public boolean isMem() { return true; }
+    @Override boolean canDrop(MemOpNode other, Node dep) {
+        return super.canDrop(other,dep) && _init==((StoreNode)other)._init;
+    }
+
+    @Override public String  label() { return "." +_name+"="; }
+    @Override public boolean isMem() { return true; }
+
     public Node val() { return in(3); }
 
     @Override
@@ -53,7 +59,7 @@ public class StoreNode extends MemOpNode {
             // Must have exactly one use of "this" or you get weird
             // non-serializable memory effects in the worse case.
             st.checkNoUseBeyond(this) ) {
-            assert Utils.eq(_name,st._name); // Equiv class aliasing is perfect
+            assert _name.equals(st._name); // Equiv class aliasing is perfect
             setDef(1,st.mem());
             return this;
         }
@@ -72,4 +78,11 @@ public class StoreNode extends MemOpNode {
         return false;
     }
 
+    @Override
+    String err() {
+        String err = super.err();
+        if( err != null ) return err;
+        Type ptr = val()._type;
+        return _init || ptr.isa(_declaredType) ? null : "Cannot store "+ptr+" into field "+_declaredType+" "+_name;
+    }
 }
diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java
index feb9e90f..5c852f94 100644
--- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java
+++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java
@@ -7,7 +7,7 @@ import com.seaofnodes.simple.node.Node;
 import java.util.ArrayList;
 import java.io.IOException;
 
-/** Chapter 11's compilation context; capture and event bookkeeping are shared. */
+/** Chapter 12's compilation context; capture and event bookkeeping are shared. */
 public class SimpleGraphObserver extends GraphCapture<Node> {
     private Parser _parser;
     private Node _ret;
diff --git a/src/main/java/com/seaofnodes/simple/type/Field.java b/src/main/java/com/seaofnodes/simple/type/Field.java
index cdc58215..b2c006dd 100644
--- a/src/main/java/com/seaofnodes/simple/type/Field.java
+++ b/src/main/java/com/seaofnodes/simple/type/Field.java
@@ -20,6 +20,7 @@ public class Field extends Type {
         _fname = fname;
         _type  = type;
     }
+    // Make with existing alias
     public static Field make( String fname, Type type ) {
         return new Field(fname,type).intern();
     }
@@ -46,13 +47,13 @@ public class Field extends Type {
 
     boolean eq(Type t) {
         Field f = (Field)t;
-        return Utils.eq(_fname,f._fname) && _type==f._type;
+        return _fname.equals(f._fname) && _type==f._type;
     }
 
 
     @Override
     public StringBuilder print( StringBuilder sb ) {
-        return _type.print(sb.append(_fname).append(":"));
+        return _type.print(sb.append(_fname).append(" :"));
     }
 
     @Override public String str() { return _fname; }
diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/src/main/java/com/seaofnodes/simple/type/TypeMem.java
index b6fc8824..38b3635a 100644
--- a/src/main/java/com/seaofnodes/simple/type/TypeMem.java
+++ b/src/main/java/com/seaofnodes/simple/type/TypeMem.java
@@ -15,7 +15,7 @@ public class TypeMem extends Type {
     //  0 means TOP, no slice.
     // -1 means BOT, all memory.
     //  N means slice#N.
-    private final int _alias;
+    public final int _alias;
 
     private TypeMem(int alias) { super(TMEM); _alias = alias; }
 
@@ -23,7 +23,6 @@ public class TypeMem extends Type {
     public static final TypeMem TOP = make( 0);
     public static final TypeMem BOT = make(-1);
 
-
     public static void gather(ArrayList<Type> ts) { ts.add(make(1)); ts.add(BOT); }
 
     @Override
@@ -40,7 +39,7 @@ public class TypeMem extends Type {
     }
 
     @Override
-    public Type glb() { return TypeMem.BOT; }
+    public Type glb() { return make(_alias); }
 
     @Override
     int hash() { return 9876543 + _alias; }
@@ -62,5 +61,5 @@ public class TypeMem extends Type {
             });
     }
 
-    @Override public String str() { return print(new StringBuilder()).toString(); }
+    @Override public String str() { return toString(); }
 }
diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java
index 6c874a93..5caa816d 100644
--- a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java
+++ b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java
@@ -13,21 +13,27 @@ import java.util.ArrayList;
  */
 public class TypeMemPtr extends Type {
     // A TypeMemPtr is pair (obj,nil)
-    // where obj is one of
-    //    (null,TypeStruct).
-    // where nil is one of
-    //    (true,false) meaning an explicit null is allowed or not
+    // where obj is a TypeStruct, possibly TypeStruct.BOT
+    // where nil is an explicit null is allowed or not
 
-    public final TypeStruct _obj; // null, a TypeStruct, or sentinel TypeStruct.MANY
+    // Examples:
+    // (Person,false) - a not-nil Person
+    // (Person,true ) - a Person or a nil
+    // (BOT   ,false) - a not-nil void* (unspecified struct)
+    // (TOP   ,true ) - a nil
+
+    public final TypeStruct _obj;
     public final boolean _nil;
 
     private TypeMemPtr(TypeStruct obj, boolean nil) {
         super(TMEMPTR);
+        assert obj!=null;
         _obj = obj;
         _nil = nil;
     }
     public static TypeMemPtr make(TypeStruct obj, boolean nil) { return new TypeMemPtr(obj, nil).intern(); }
-    public static TypeMemPtr make(TypeStruct obj) { return TypeMemPtr.make(obj, false); }
+    public static TypeMemPtr make(TypeStruct obj) { return make(obj, false); }
+    public TypeMemPtr make_from(TypeStruct obj) { return make(obj, _nil); }
 
     public static final TypeMemPtr BOT = make(TypeStruct.BOT,true);
     public static final TypeMemPtr TOP = BOT.dual();
@@ -43,17 +49,14 @@ public class TypeMemPtr extends Type {
     }
 
     @Override
-    public TypeMemPtr dual() { return TypeMemPtr.make(_obj==null ? null : _obj.dual(), !_nil); }
+    public TypeMemPtr dual() { return TypeMemPtr.make(_obj.dual(), !_nil); }
 
     @Override
-    public Type glb() {
-        if( _obj==null ) return BOT;
-        return make(_obj.glb(),true);
-    }
+    public Type glb() { return make(_obj.glb(),true); }
     @Override public TypeMemPtr makeInit() { return NULLPTR; }
 
     @Override
-    int hash() { return (_obj==null ? 0xDEADBEEF : _obj.hashCode()) ^ (_nil ? 1024 : 0); }
+    int hash() { return _obj.hashCode() ^ (_nil ? 1024 : 0); }
 
     @Override
     boolean eq(Type t) {
diff --git a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java
index 44741def..02de7cc8 100644
--- a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java
+++ b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java
@@ -8,9 +8,12 @@ import java.util.ArrayList;
  */
 public class TypeStruct extends Type {
 
-    // For now in terms of the lattice
-    // a struct type just stays as is
-
+    // Immutable shallow references, resolved by name in Parser.TYPES when needed.
+    // A name-only struct has _fields == null, even after its definition is known.
+    // For LLI { LLI? next; int i; }, L0 is name-only and L1.next points to L0;
+    // TYPES["LLI"] holds L1. We deliberately stop recursive type expansion here,
+    // keeping interning and lattice operations finite and acyclic. Never patch
+    // L0 into L1: field access looks up the complete declaration by name instead.
     public final String _name;
     public final Field[] _fields;
 
@@ -20,13 +23,23 @@ public class TypeStruct extends Type {
         _fields = fields;
     }
 
+    // Forward-ref version
+    public static TypeStruct make(String name) { return new TypeStruct(name, null).intern(); }
+    // All fields directly listed
     public static TypeStruct make(String name, Field[] fields) { return new TypeStruct(name, fields).intern(); }
+    // Parser uses an ArrayList to gather the fields
     public static TypeStruct make(String name, ArrayList<Field> fields) { return make(name,fields.toArray(new Field[fields.size()])); }
 
     public static final TypeStruct TOP = make("$TOP",new Field [0]);
     public static final TypeStruct BOT = make("$BOT",new Field [0]);
     public static final TypeStruct TEST = make("test",new Field[]{Field.TEST});
-    public static void gather(ArrayList<Type> ts) { ts.add(TEST); ts.add(BOT); }
+
+    // A pair of self-cyclic types
+    private static final TypeStruct S1F = make("S1");
+    private static final TypeStruct S2F = make("S2");
+    public  static final TypeStruct S1  = make("S1", new Field[]{ Field.make("a", TypeInteger.BOT), Field.make("s2",TypeMemPtr.make(S2F,false)) });
+    private static final TypeStruct S2  = make("S2", new Field[]{ Field.make("b", TypeInteger.BOT), Field.make("s1",TypeMemPtr.make(S1F,false)) });
+    public static void gather(ArrayList<Type> ts) { ts.add(TEST); ts.add(BOT); ts.add(S1); ts.add(S2); }
 
     public int find(String fname) {
         for( int i=0; i<_fields.length; i++ )
@@ -51,6 +64,8 @@ public class TypeStruct extends Type {
         // And the answer is: "don't ask".
         if( !_name.equals(that._name) )
             return BOT;         // It's a struct; that's about all we know
+        if( this._fields==null ) return this;
+        if( that._fields==null ) return that;
         // Now all fields should be the same, so just do field meets
         assert _fields.length == that._fields.length;
         Field[] flds = new Field[_fields.length];
@@ -63,6 +78,7 @@ public class TypeStruct extends Type {
     public TypeStruct dual() {
         if( this==TOP ) return BOT;
         if( this==BOT ) return TOP;
+        if( _fields == null ) return this;
         Field[] flds = new Field[_fields.length];
         for( int i=0; i<_fields.length; i++ )
             flds[i] = _fields[i].dual();
@@ -80,9 +96,10 @@ public class TypeStruct extends Type {
         return make(_name,flds);
     }
     private boolean _glb() {
-        for( Field f : _fields )
-            if( f.glb() != f )
-                return false;
+        if( _fields!=null )
+          for( Field f : _fields )
+              if( f.glb() != f )
+                 return false;
         return true;
     }
 
@@ -91,6 +108,7 @@ public class TypeStruct extends Type {
         TypeStruct ts = (TypeStruct)t; // Invariant
         if( !_name.equals(ts._name) )
             return false;
+        if( _fields == ts._fields ) return true;
         if( _fields.length!=ts._fields.length )
             return false;
         for( int i = 0; i < _fields.length; i++ )
@@ -102,7 +120,9 @@ public class TypeStruct extends Type {
     @Override
     int hash() {
         long hash = _name.hashCode();
-        for( Field f : _fields ) hash = Utils.rot(hash,13) ^ f.hashCode();
+        if( _fields != null )
+            for( Field f : _fields )
+                hash = Utils.rot(hash,13) ^ f.hashCode();
         return Utils.fold(hash);
     }
 
@@ -110,11 +130,12 @@ public class TypeStruct extends Type {
     public StringBuilder print(StringBuilder sb) {
         if( this==BOT ) return sb.append("StructBot");
         if( this==TOP ) return sb.append("StructTop");
-        sb.append(_name).append(" {\n");
+        sb.append(_name);
+        if( _fields == null ) return sb; // Forward reference struct, just print the name
+        sb.append(" {\n");
         for( Field f : _fields ) {
-            sb.append("  ").append(f._fname).append(":");
-            f._type.print(sb);
-            sb.append(";\n");
+            sb.append("  ").append(f._fname).append(" :");
+            f._type.print(sb).append(";\n");
         }
         return sb.append("}");
     }