From 67dc6202dee2ce983778ba3143cc3f00196aeb7c Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Thu, 12 Sep 2024 11:13:31 -0700 Subject: Chapter 15: Arrays Co-authored-by: XmiliaH Co-authored-by: Thalia Archibald Co-authored-by: Robert Obkircher --- src/main/java/com/seaofnodes/simple/Parser.java | 230 +++++++++++++++++------- 1 file changed, 170 insertions(+), 60 deletions(-) (limited to 'src/main/java/com/seaofnodes/simple/Parser.java') diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index 9e4b9eb6..4bb18d6b 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -23,8 +23,11 @@ public class Parser { */ public static StartNode START; - public static ConstantNode ZERO; - public static XCtrlNode XCTRL; + public static ConstantNode ZERO; // Very common node, cached here + public static XCtrlNode XCTRL; // Very common node, cached here + + // Next available memory alias number + static int ALIAS; public StopNode STOP; @@ -89,7 +92,9 @@ public class Parser { ScopeNode _continueScope; ScopeNode _breakScope; - // Mapping from a type name to a Type. + // Mapping from a type name to a Type. The string name matches + // `type.str()` call. No TypeMemPtrs are in here, because Simple does not + // have C-style '*ptr' references. public static HashMap TYPES = new HashMap<>(); public Parser(String source, TypeInteger arg) { @@ -116,8 +121,9 @@ public class Parser { _continueScope = _breakScope = null; START = new StartNode(new Type[]{ Type.CONTROL, arg }); STOP = new StopNode(source); - ZERO = new ConstantNode(TypeInteger.constant(0)).peephole().keep(); + ZERO = con(0).keep(); XCTRL= new XCtrlNode().peephole().keep(); + ALIAS = 2; // alias 0 for the control, 1 for memory } public Parser(String source) { @@ -143,9 +149,12 @@ public class Parser { _scope.push(); _scope.define(ScopeNode.CTRL, Type.CONTROL , new CProjNode(START, 0, ScopeNode.CTRL).peephole()); _scope.define(ScopeNode.ARG0, TypeInteger.BOT, new ProjNode(START, 1, ScopeNode.ARG0).peephole()); + + // Parse whole program parseBlock(); + if( ctrl()._type==Type.CONTROL ) - STOP.addReturn(new ReturnNode(ctrl(), new ConstantNode(TypeInteger.constant(0)).peephole(), _scope).peephole()); + STOP.addReturn(new ReturnNode(ctrl(), ZERO, _scope).peephole()); _scope.pop(); _xScopes.pop(); if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); @@ -207,7 +216,7 @@ public class Parser { Type t = type(); if( t==null ) throw errorSyntax("Requires a field type, found '"+_lexer.getAnyNextToken()+"'"); - return require(Field.make(requireId().intern(),t),";"); + return require(Field.make(requireId().intern(),ALIAS++,t),";"); } /** @@ -221,7 +230,9 @@ 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 TypeStruct ts && ts._fields==null) ) throw errorSyntax("struct '" + typeName + "' cannot be redefined"); + if( t!=null && !(t instanceof TypeMemPtr tmp && tmp._obj._fields==null) ) + throw errorSyntax("struct '" + typeName + "' cannot be redefined"); + // Parse a collection of fields ArrayList fields = new ArrayList<>(); require("{"); while (!peek('}') && !_lexer.isEOF()) { @@ -231,8 +242,8 @@ public class Parser { } require("}"); // Build and install the TypeStruct - TypeStruct ts = TypeStruct.make(typeName, fields); - TYPES.put(typeName, ts); + TypeStruct ts = TypeStruct.make(typeName, fields.toArray(new Field[fields.size()])); + TYPES.put(typeName, TypeMemPtr.make(ts)); START.addMemProj(ts, _scope); // Insert memory edges return parseStatement(); } @@ -325,7 +336,7 @@ public class Parser { ctrl(XCTRL); // Kill current scope // Prune nested lexical scopes that have depth > than the loop head // We use _breakScope as a proxy for the loop head scope to obtain the depth - while( cur._scopes.size() > _breakScope._scopes.size() ) + while( cur._idxs.size() > _breakScope._idxs.size() ) cur.pop(); // If this is a continue then first time the target is null // So we just use the pruned current scope as the base for the @@ -333,7 +344,7 @@ public class Parser { if (toScope == null) return cur; // toScope is either the break scope, or a scope that was created here - assert toScope._scopes.size() <= _breakScope._scopes.size(); + assert toScope._idxs.size() <= _breakScope._idxs.size(); toScope.ctrl(toScope.mergeScopes(cur)); return toScope; } @@ -463,33 +474,70 @@ public class Parser { // 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)); + e = 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 id" and return "type" (and re-parse "id" in caller) or - // 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 + // ref type position. private Type type() { - int old = _lexer._position; + int old1 = _lexer._position; String tname = _lexer.matchId(); if( tname==null ) return null; - 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; + // Convert the type name to a type. + Type t0 = TYPES.get(tname); + Type t1 = t0 == null ? TypeMemPtr.make(TypeStruct.make(tname)) : t0; // Null: assume a forward ref type + // Nest arrays and '?' as needed + while( true ) { + assert !(t1 instanceof TypeStruct); + if( match("?") ) { + if( !(t1 instanceof TypeMemPtr tmp) ) + throw error("Type "+t0+" cannot be null"); + if( tmp._nil ) throw error("Type "+t1+" already allows null"); + t1 = TypeMemPtr.make(tmp._obj,true); + continue; + } + if( match("[]") ) { + t1 = typeAry(t1); + continue; } - TYPES.put(tname,t = TypeStruct.make(tname)); - _lexer._position = old2; // Reparse ID in caller + break; } - return t instanceof TypeStruct obj ? TypeMemPtr.make(obj,nullable) : t; + + // Check no forward ref + if( t0 != null ) return t1; + // Check valid forward ref, after parsing all the type extra bits. + // Cannot check earlier, because cannot find required 'id' until after "[]?" syntax + int old2 = _lexer._position; + String id = _lexer.matchId(); + _lexer._position = old2; // Reset lexer to reparse + if( id==null ) { + _lexer._position = old1; // Reset lexer to reparse + return null; // Not a type + } + // Yes a forward ref, so declare it + TYPES.put(tname,t1); + return t1; + } + + // Make an array type of t + private TypeMemPtr typeAry( Type t ) { + if( t instanceof TypeMemPtr tmp && !tmp._nil ) + throw error("Arrays of reference types must always be nullable"); + String tname = t.str()+"[]"; + Type ta = TYPES.get(tname); + if( ta != null ) return (TypeMemPtr)ta; + // Need make an array type. + TypeStruct ts = TypeStruct.makeAry(TypeInteger.BOT,ALIAS++,t,ALIAS++); + TypeMemPtr tary = TypeMemPtr.make(ts); + TYPES.put(tname,tary); + START.addMemProj(ts, _scope); // Insert memory alias edges + return tary; } @@ -637,22 +685,36 @@ public class Parser { * Parse a primary expression: * * 
-     *     primaryExpr : integerLiteral | Identifier | true | false | null | new Identifier | '(' expression ')'
+     *     primaryExpr : integerLiteral | Identifier | true | false | null | new Type | '(' expression ')'
      *
* @return a primary {@link Node}, never {@code null} */ private Node parsePrimary() { if( _lexer.isNumber(_lexer.peek()) ) return parseLiteral(); if( match("(") ) return require(parseExpression(), ")"); - if( matchx("true" ) ) return new ConstantNode(TypeInteger.constant(1)).peephole(); + if( matchx("true" ) ) return con(1); if( matchx("false") ) return ZERO; if( matchx("null" ) ) return new ConstantNode(TypeMemPtr.NULLPTR).peephole(); if( matchx("new") ) { - String structName = requireId(); - Type t = TYPES.get(structName); - if( !(t instanceof TypeStruct obj) || obj._fields==null ) - throw error("Unknown struct type '" + structName + "'"); - return newStruct(obj); + Type t = type(); + if( t==null ) throw error("Expected a type"); + if( match("[") ) { + Node len = parseExpression().keep(); + if( !(len._type instanceof TypeInteger) ) + throw error("Cannot allocate an array with length "+len._type); + require("]"); + TypeMemPtr tmp = typeAry(t); + 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))); + } + throw error("Cannot allocate a "+t.str()); } String name = _lexer.matchId(); if( name == null) throw errorSyntax("an identifier or expression"); @@ -662,16 +724,29 @@ public class Parser { } /** - * Return a NewNode but also generate instructions to initialize it. + * Return a NewNode with pre-zeroed memory */ - private Node newStruct(TypeStruct obj) { - Node n = new NewNode(TypeMemPtr.make(obj), ctrl()).peephole().keep(); - int alias = START._aliasStarts.get(obj._name); - for( Field field : obj._fields ) { - memAlias(alias, new StoreNode(field._fname, alias, field._type, ctrl(), memAlias(alias), n, new ConstantNode(field._type.makeInit()).peephole(),true).peephole()); - alias++; - } - return n.unkeep(); + private Node newStruct(TypeStruct obj, Node size) { + Field[] fs = obj._fields; + Node[] ns = new Node[2+fs.length]; + ns[0] = ctrl(); + ns[1] = size; + for( int i = 0; i < fs.length; i++ ) + ns[i+2] = memAlias(fs[i]._alias); + Node nnn = new NewNode(TypeMemPtr.make(obj), ns).peephole(); + for( int i = 0; i < fs.length; i++ ) + memAlias(fs[i]._alias, new ProjNode(nnn,i+2,memName(fs[i]._alias)).peephole()); + return new ProjNode(nnn,1,obj._name).peephole(); + } + + private Node newArray(TypeStruct ary, Node len) { + int base = ary.aryBase (); + int scale= ary.aryScale(); + Node size = new AddNode(con(base),new ShlNode(len,con(scale)).peephole()).peephole(); + Node ptr = newStruct(ary,size); + int alias = ary._fields[0]._alias; // Length alias + memAlias(alias,new StoreNode("#",alias,TypeInteger.BOT,memAlias(alias),ptr,con( ary.offset(0) ), len.unkeep(), true ).peephole()); + return ptr; } // We set up memory aliases by inserting special vars in the scope these @@ -688,39 +763,70 @@ public class Parser { * * 
      *     expr ('.' IDENTIFIER)* [ = expr ]
+     *     expr #
+     *     expr ('[' expr ']')* = [ = expr ]
      *
*/ private Node parsePostfix(Node expr) { - if( !match(".") ) return expr; + String name = null; + if( match(".") ) name = requireId().intern(); + else if( match("#") ) name = "#"; + else if( match("[") ) name = "[]"; + else return expr; // No postfix + // Sanity check expr for being a reference if( !(expr._type instanceof TypeMemPtr ptr) ) - throw error("Expected struct reference but got " + expr._type.str()); - - String name = requireId().intern(); - if( expr._type == TypeMemPtr.TOP ) throw error("Accessing field '" + name + "' from null"); + throw error("Expected reference but got " + expr._type.str()); + if( ptr == 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 = START._aliasStarts.get(ptr._obj._name)+idx; + // 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() + "'"); + TypeStruct base = tmp._obj; + int fidx = base.find(name); + if( fidx == -1 ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); + expr.keep(); + + // Get field type and layout offset from base type and field index fidx + Field f = base._fields[fidx]; // Field from field index + Node off; + if( name.equals("[]") ) { // If field is an array body + // Array index math + Node idx = require(parseExpression(),"]"); + Node shl = new ShlNode(idx,con(base.aryScale())).peephole(); + off = new AddNode(con(base.aryBase()),shl).peephole(); + } else { // Else normal struct field + // Hardwired field offset + off = con(base.offset(fidx)); + } if( match("=") ) { // Disambiguate "obj.fld==x" boolean test from "obj.fld=x" field assignment if( peek('=') ) _lexer._position--; else { + off.keep(); Node val = parseExpression(); - Type glb = base._fields[idx]._type; // Auto-truncate when storing to narrow fields - val = zsMask(val,glb); - memAlias(alias, new StoreNode(name, alias,glb, ctrl(), memAlias(alias), expr, val, false).peephole()); - return expr; // "obj.a = expr" returns the expression while updating memory + val = zsMask(val,f._type).keep(); + Node st = new StoreNode(name, f._alias, f._type, memAlias(f._alias), expr.unkeep(), off.unkeep(), 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, st.peephole()); + return val.unkeep(); // "obj.a = expr" returns the expression while updating memory } } - Type declaredType = base._fields[idx]._type; - return parsePostfix(new LoadNode(name, alias, declaredType.glb(), memAlias(alias), expr).peephole()); + Node load = new LoadNode(name, f._alias, f._type.glb(), memAlias(f._alias), expr.unkeep(), 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()); + return parsePostfix(load.peephole()); } + // zero/sign extend. "i" is limited to either classic unsigned (min==0) or // classic signed (min=minus-power-of-2); max=power-of-2-minus-1. private Node zsMask(Node val, Type t ) { @@ -731,10 +837,10 @@ public class Parser { return new RoundF32Node(val).peephole(); } if( t0._min==0 ) // Unsigned - return new AndNode(val,new ConstantNode(TypeInteger.constant(t0._max)).peephole()).peephole(); + return new AndNode(val,con(t0._max)).peephole(); // Signed extension int shift = Long.numberOfLeadingZeros(t0._max)-1; - Node shf = new ConstantNode(TypeInteger.constant(shift)).peephole(); + Node shf = con(shift); if( shf._type==TypeInteger.ZERO ) return val; return new SarNode(new ShlNode(val,shf.keep()).peephole(),shf.unkeep()).peephole(); @@ -753,6 +859,10 @@ public class Parser { return (ConstantNode) new ConstantNode(_lexer.parseNumber()).peephole(); } + public static Node con( long con ) { + return new ConstantNode(TypeInteger.constant(con)).peephole(); + } + ////////////////////////////////// // Utilities for lexical analysis -- cgit v1.2.3