From 3b2e5240eae6a0b7f29a1eb491591dcbd0e9c2d5 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Mon, 14 Oct 2024 16:47:15 -0700 Subject: Constructors Missing arrays yet. Allow constructor syntax in 2 parts; the type description and at the New. must-init fields (final and not-null) have to be initialized in at least one of the two places; finals must be initialized exactly once. Any code is allowed in the constructors. --- .../main/java/com/seaofnodes/simple/Parser.java | 209 ++++++++++++--------- .../java/com/seaofnodes/simple/node/LoadNode.java | 7 +- .../java/com/seaofnodes/simple/node/NewNode.java | 33 +++- .../java/com/seaofnodes/simple/node/ScopeNode.java | 10 +- .../com/seaofnodes/simple/node/StructNode.java | 53 ++++++ .../java/com/seaofnodes/simple/type/Field.java | 3 + .../java/com/seaofnodes/simple/Chapter10Test.java | 16 +- .../java/com/seaofnodes/simple/Chapter11Test.java | 4 +- .../java/com/seaofnodes/simple/Chapter13Test.java | 20 +- .../java/com/seaofnodes/simple/Chapter14Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter16Test.java | 45 ++++- .../com/seaofnodes/simple/evaluator/Evaluator.java | 15 +- 12 files changed, 279 insertions(+), 138 deletions(-) create mode 100644 chapter16/src/main/java/com/seaofnodes/simple/node/StructNode.java (limited to 'chapter16') diff --git a/chapter16/src/main/java/com/seaofnodes/simple/Parser.java b/chapter16/src/main/java/com/seaofnodes/simple/Parser.java index bdd14de6..572c170a 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/Parser.java @@ -7,7 +7,7 @@ import java.util.*; /** * The Parser converts a Simple source program to the Sea of Nodes intermediate - * representation directly in one pass. There is no intermediate Abstract + * representation directly in one pass. There is no intermediate Abstract * Syntax Tree structure. *

* This is a simple recursive descent parser. All lexical analysis is done here as well. @@ -97,6 +97,10 @@ public class Parser { // have C-style '*ptr' references. public static HashMap TYPES = new HashMap<>(); + // Mapping from a type name to the constructor for a Type. + public static HashMap INITS = new HashMap<>(); + + public Parser(String source, TypeInteger arg) { Node.reset(); IterPeeps.reset(); @@ -115,6 +119,7 @@ public class Parser { TYPES.put("u16" ,TypeInteger.U16); TYPES.put("u32" ,TypeInteger.U32); TYPES.put("u8" ,TypeInteger.U8 ); + INITS.clear(); SCHEDULED = false; _lexer = new Lexer(source); _scope = new ScopeNode(); @@ -205,65 +210,6 @@ public class Parser { // to ambiguity else return parseExpressionStatement(); } - - /** - * Parse a struct field. - * 

-     *     type IDENTIFIER ;
-     *
- */ - //private Field parseField() { - // Type t = type(); - // if( t==null ) - // throw errorSyntax("Requires a field type, found '"+_lexer.getAnyNextToken()+"'"); - // boolean xfinal = match("!"); - // return require(Field.make(requireId().intern(),t,ALIAS++,xfinal),";"); - //} - - /** - * Parse a struct declaration, and return the following statement. - * Only allowed in top level scope. - * Structs cannot be redefined. - * - * @return The statement following the struct - */ - private Node parseStruct() { - 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) ) - throw errorSyntax("struct '" + typeName + "' cannot be redefined"); - // A Block scope parse, and inspect the scope afterwards for fields. - _scope.push(); - require("{"); - while (!peek('}') && !_lexer.isEOF()) - parseStatement(); - require("}"); - // Grab the declarations and build fields - HashMap decls = _scope._decls.lastElement(); - HashMap idxs = _scope._idxs.lastElement(); - BitSet finals = _scope._finals; - - Field[] fs = new Field[decls.size()]; int i=0; - for( String fname : decls.keySet() ) { - int idx = idxs.get(fname); - boolean isFinal = finals.get(idx); - Type decl = decls.get(fname); - fs[i++] = Field.make(fname,decl,ALIAS++,isFinal); - if( isFinal ) throw Utils.TODO(); // Track write-once - if( _scope.in(idx)._type != decl.makeInit() ) throw Utils.TODO(); // Track non-zero init - } - // Done with scope - _scope.pop(); - - // Build and install the TypeStruct - TypeStruct ts = TypeStruct.make(typeName, fs); - TYPES.put(typeName, TypeMemPtr.make(ts)); - START.addMemProj(ts, _scope); // Insert memory edges - require(";"); - return null; - } - /** * Parses a while statement * @@ -452,10 +398,17 @@ public class Parser { int old = _lexer._position; String name = requireId(); Node expr; - if( match(";") || peek(',') ) { + if( peek(';') || peek(',') ) { // Bare "name" is not allowed if( t==null ) throw errorSyntax("expression"); - expr = new ConstantNode(t.makeInit()).peephole(); + // Does this declaration need an initializer and not getting one? + Type init = xfinal || t instanceof TypeMemPtr tmp && !tmp._nil + // Must be initialized in the "new" constructor + ? Type.TOP + // Else takes the default + : t.makeInit(); + expr = new ConstantNode(init).peephole(); + } else if( !match("=") ) { // Something else _lexer._position = old; return null; @@ -465,9 +418,13 @@ public class Parser { // Defining a new variable vs updating an old one if( !isDecl ) { // Assigning over an existing name // Lookup - if( _scope.lookup(name)==null ) + Node def = _scope.lookup(name); + if( def==null ) throw error("Undefined name '" + name + "'"); - if( _scope.lookupFinal(name) ) + // TOP fields are for late-initialized fields; these have never + // been written to, and this must be the final write. Other writes + // need to check the final bit. + if( def._type!=Type.TOP && _scope.lookupFinal(name) ) throw error("Cannot reassign final '"+name+"'"); t = _scope.lookupDeclaredType(name); } @@ -485,9 +442,8 @@ public class Parser { if( !e.isa(t) ) throw error("Type " + e.str() + " is not of declared type " + t.str()); - if( isDecl ) { - if( _scope.define(name,t,expr,xfinal) == null ) + if( !_scope.define(name,t,expr,xfinal) ) throw error("Redefining name '" + name + "'"); } else _scope.update(name,expr); @@ -530,6 +486,60 @@ public class Parser { return require(n,";"); } + + /** + * Parse a struct declaration, and return the following statement. + * Only allowed in top level scope. + * Structs cannot be redefined. + * + * @return The statement following the struct + */ + private Node parseStruct() { + 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) ) + throw errorSyntax("struct '" + typeName + "' cannot be redefined"); + + // A Block scope parse, and inspect the scope afterwards for fields. + _scope.push(); + require("{"); + while (!peek('}') && !_lexer.isEOF()) + parseStatement(); + + // Grab the declarations and build fields and a Struct + HashMap decls = _scope._decls.lastElement(); + HashMap idxs = _scope._idxs.lastElement(); + BitSet finals = _scope._finals; + + StructNode s = new StructNode().keep(); + Field[] fs = new Field[decls.size()]; int i=0; + for( String fname : decls.keySet() ) { + int idx = idxs.get(fname); + boolean isFinal = finals.get(idx); + Type decl = decls.get(fname); + fs[i++] = Field.make(fname,decl,ALIAS++,isFinal); + s.addDef(_scope.in(idx)); + } + // Done with struct/block scope + require("}"); + _scope.pop(); + + // Build and install the TypeStruct + TypeStruct ts = TypeStruct.make(typeName, fs); + TYPES.put(typeName, TypeMemPtr.make(ts)); + require(";"); + // Save initial constructor + s._ts = ts; + INITS.put(typeName,(StructNode)s.peephole()); + + // Insert memory edges + START.addMemProj(ts, _scope); + + return null; + } + + // Parse and return a type or null. Valid types always are followed by an // 'id' which the caller must parse. This lets us distinguish forward ref // types (which ARE valid here) from local vars in an (optional) forward @@ -756,12 +766,32 @@ public class Parser { return newArray(tmp._obj,len); } if( t instanceof TypeMemPtr tmp ) { - TypeStruct obj = tmp._obj; - if( obj._fields==null ) - throw error("Unknown struct type '" + obj._name + "'"); - if( obj.isAry() ) - throw Utils.TODO(); // Missing array length - return newStruct(obj,con(obj.offset(obj._fields.length))); + StructNode s = INITS.get(tmp._obj._name); + if( s==null ) throw error("Unknown struct type '" + tmp._obj._name + "'"); + Field[] fs = s._ts._fields; + // if the object is fully initialized, we can skip a block here. + // Check for constructor block: + boolean hasConstructor = match("{"); + Node init=s; int idx=0; + if( hasConstructor ) { + init = _scope; + idx = _scope.nIns(); + // Push a scope, and pre-assign all struct fields. + _scope.push(); + for( int i=0; i syms = _idxs.lastElement(); _decls.lastElement().put(name,declaredType); if( syms.put(name,nIns()) != null ) - return null; // Double define + return false; // Double define if( xfinal ) _finals.set(nIns()); // track finals - return addDef(n); + addDef(n); + return true; } /** diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/StructNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/StructNode.java new file mode 100644 index 00000000..69e9f444 --- /dev/null +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/StructNode.java @@ -0,0 +1,53 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.*; +import java.util.BitSet; + +/** + * Build a compound object + */ +public class StructNode extends Node { + + public TypeStruct _ts; + + @Override public String label() { return _ts==null ? "STRUCT?" : _ts.str(); } + + @Override + StringBuilder _print1(StringBuilder sb, BitSet visited) { + if( _ts==null ) return sb.append("STRUCT?"); + sb.append(_ts._name).append(" {"); + for( int i=0; i ts) { ts.add(TEST); } diff --git a/chapter16/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter16/src/test/java/com/seaofnodes/simple/Chapter10Test.java index ec6a0bb4..0b3e4110 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -103,7 +103,7 @@ while (arg) { return bar.a; """); StopNode stop = parser.parse(false).iterate(); - assertEquals("return Phi(Loop14,0,(Phi_a+2));", stop.toString()); + assertEquals("return Phi(Loop15,0,(Phi_a+2));", stop.toString()); } @Test @@ -155,7 +155,7 @@ if( bar ) bar.a = 1; return bar; """); StopNode stop = parser.parse(false).iterate(); - assertEquals("return Phi(Region34,(*void)Phi(Region21,null,Bar),null);", stop.toString()); + assertEquals("return Phi(Region35,(*void)Phi(Region22,null,Bar),null);", stop.toString()); } @Test @@ -171,7 +171,7 @@ else bar.a = 1; return rez; """); StopNode stop = parser.parse(false).iterate(); - assertEquals("return Phi(Region40,4,3);", stop.toString()); + assertEquals("return Phi(Region41,4,3);", stop.toString()); } @Test @@ -225,12 +225,10 @@ while( i.x < i.len ) { return sum; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop20,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", stop.toString()); + assertEquals("return Phi(Loop21,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", stop.toString()); } - - @Test public void test1() { Parser parser = new Parser(""" @@ -246,7 +244,7 @@ while(arg) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop14,s0,Phi(Region38,s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop15,s0,Phi(Region39,s0,Phi_ret));", stop.toString()); } @Test @@ -264,7 +262,7 @@ while(arg) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop18,s0,Phi(Region39,s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop19,s0,Phi(Region40,s0,Phi_ret));", stop.toString()); } @@ -281,7 +279,7 @@ while(arg < 10) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop14,s0,Phi(Region36,s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop15,s0,Phi(Region37,s0,Phi_ret));", stop.toString()); } @Test diff --git a/chapter16/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter16/src/test/java/com/seaofnodes/simple/Chapter11Test.java index 4998d78f..90198098 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -369,7 +369,7 @@ if (arg) { return i; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region41,.f,0);", stop.toString()); + assertEquals("return Phi(Region42,.f,0);", stop.toString()); } @Test @@ -476,7 +476,7 @@ while(arg) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop18,arg,Phi(Region43,.f,0));", stop.toString()); + assertEquals("return Phi(Loop19,arg,Phi(Region44,.f,0));", stop.toString()); } @Test diff --git a/chapter16/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/chapter16/src/test/java/com/seaofnodes/simple/Chapter13Test.java index a95a6155..750fe3d3 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/Chapter13Test.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/Chapter13Test.java @@ -95,33 +95,33 @@ return n.next; public void testNullRef1() { Parser parser = new Parser( """ -struct N { N next; int i; }; -N n = new N; -n.next = new N; +struct M { int m; }; +struct N { M next; int i; }; +N n = new N { next = new M; }; return n.next; """); StopNode stop = parser.parse().iterate(); - assertEquals("return N;", stop.toString()); + assertEquals("return M;", stop.toString()); } @Test public void testNullRef2() { Parser parser = new Parser( """ -struct N { N next; int i; }; -N n = new N; -n.next = null; +struct M { int m; }; +struct N { M next; int i; }; +N n = new N { next = null; } return n.next; """); try { parser.parse().iterate(); fail(); } - catch( Exception e ) { assertEquals("Cannot store null into field *N next",e.getMessage()); } + catch( Exception e ) { assertEquals("Type null is not of declared type *M",e.getMessage()); } } @Test public void testNullRef3() { Parser parser = new Parser( """ -struct N { N next; int i; }; +struct N { N? next; int i; }; N n = new N; n.i = 3.14; return n.i; @@ -169,7 +169,7 @@ return new S1.s=new S2; Parser parser = new Parser( """ struct I {int i;}; -struct P {I pi;}; +struct P { I? pi; }; P p1 = new P; P p2 = new P; p2.pi = new I; diff --git a/chapter16/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/chapter16/src/test/java/com/seaofnodes/simple/Chapter14Test.java index 048cb93a..674196ee 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/Chapter14Test.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/Chapter14Test.java @@ -93,7 +93,7 @@ return b; public void testRefLoad() { Parser parser = new Parser( """ -struct Foo { u1 b; } +struct Foo { u1 b; }; Foo f = new Foo; f.b = 123; return f.b; diff --git a/chapter16/src/test/java/com/seaofnodes/simple/Chapter16Test.java b/chapter16/src/test/java/com/seaofnodes/simple/Chapter16Test.java index 7adc5b10..9a56bc94 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/Chapter16Test.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/Chapter16Test.java @@ -5,6 +5,7 @@ import com.seaofnodes.simple.node.StopNode; import org.junit.Test; import org.junit.Ignore; +import java.awt.*; import java.nio.charset.StandardCharsets; import static org.junit.Assert.assertEquals; @@ -83,17 +84,53 @@ return y; assertEquals(9L, Evaluator.evaluate(stop, 1)); } + @Test + public void testConstruct0() { + Parser parser = new Parser(""" +struct X { int x=3; }; +X z = new X; +return z.x; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 3;", stop.toString()); + assertEquals(3L, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testConstruct1() { + Parser parser = new Parser(""" +struct X { int !x; }; +X z = new X { x=3; }; +return z.x; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 3;", stop.toString()); + assertEquals(3L, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testConstruct2() { + Parser parser = new Parser(""" +struct X { int x=3; }; +X z = new X { x = 4; }; +return z.x; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 4;", stop.toString()); + assertEquals(4L, Evaluator.evaluate(stop, 0)); + } + @Test public void testStructFinal() { Parser parser = new Parser(""" -struct Point { int !x, !y; } -Point p = new Point { x=3; y=4; } +struct Point { int !x, !y; }; +Point p = new Point { x=3; y=4; }; return p; """); StopNode stop = parser.parse().iterate(); - assertEquals("return P;", stop.toString()); - assertEquals(3.14, Evaluator.evaluate(stop, 0)); + assertEquals("return Point;", stop.toString()); + assertEquals("Obj{x=3,y=4}", Evaluator.evaluate(stop, 0).toString()); } } diff --git a/chapter16/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/chapter16/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java index 34921b94..fccec969 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -202,19 +202,10 @@ public class Evaluator { } num = type._fields.length-1; } else { - body = new Object[type._fields.length]; - num = type._fields.length; - } - for (int i=0; i