From f4bd723d929e53475f7990374dca7b7dfcbbdc42 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sun, 1 Nov 2026 10:33:55 -0800 Subject: Add Chapter 29 for tech debt cleanup with the parser split Keep Chapter 28b intact and carry the grammar-oriented parser package, Var move, IterPeeps move, and parser regression tests into Chapter 29. Defer privacy and exclude its experimental tests and fixture changes. Register the chapter in the indexes, IntelliJ modules and run configurations, Maven reactor, roadmap, and linear-history publisher. Windows and Linux each pass 573 tests, release builds, 199 allocation replays, and 29 native checks. --- .../com/seaofnodes/simple/parser/Allocations.java | 199 ++++++++++ .../com/seaofnodes/simple/parser/ControlFlow.java | 96 +++++ .../com/seaofnodes/simple/parser/Conversions.java | 72 ++++ .../com/seaofnodes/simple/parser/Declarations.java | 164 ++++++++ .../com/seaofnodes/simple/parser/Expressions.java | 394 ++++++++++++++++++++ .../com/seaofnodes/simple/parser/Functions.java | 346 +++++++++++++++++ .../java/com/seaofnodes/simple/parser/Lexer.java | 384 +++++++++++++++++++ .../java/com/seaofnodes/simple/parser/Parser.java | 298 +++++++++++++++ .../java/com/seaofnodes/simple/parser/README.md | 26 ++ .../com/seaofnodes/simple/parser/References.java | 369 ++++++++++++++++++ .../com/seaofnodes/simple/parser/Statements.java | 272 ++++++++++++++ .../java/com/seaofnodes/simple/parser/Structs.java | 411 +++++++++++++++++++++ .../java/com/seaofnodes/simple/parser/Types.java | 244 ++++++++++++ .../java/com/seaofnodes/simple/parser/Var.java | 54 +++ .../com/seaofnodes/simple/parser/package-info.java | 14 + 15 files changed, 3343 insertions(+) create mode 100644 chapter29/src/main/java/com/seaofnodes/simple/parser/Allocations.java create mode 100644 chapter29/src/main/java/com/seaofnodes/simple/parser/ControlFlow.java create mode 100644 chapter29/src/main/java/com/seaofnodes/simple/parser/Conversions.java create mode 100644 chapter29/src/main/java/com/seaofnodes/simple/parser/Declarations.java create mode 100644 chapter29/src/main/java/com/seaofnodes/simple/parser/Expressions.java create mode 100644 chapter29/src/main/java/com/seaofnodes/simple/parser/Functions.java create mode 100644 chapter29/src/main/java/com/seaofnodes/simple/parser/Lexer.java create mode 100644 chapter29/src/main/java/com/seaofnodes/simple/parser/Parser.java create mode 100644 chapter29/src/main/java/com/seaofnodes/simple/parser/README.md create mode 100644 chapter29/src/main/java/com/seaofnodes/simple/parser/References.java create mode 100644 chapter29/src/main/java/com/seaofnodes/simple/parser/Statements.java create mode 100644 chapter29/src/main/java/com/seaofnodes/simple/parser/Structs.java create mode 100644 chapter29/src/main/java/com/seaofnodes/simple/parser/Types.java create mode 100644 chapter29/src/main/java/com/seaofnodes/simple/parser/Var.java create mode 100644 chapter29/src/main/java/com/seaofnodes/simple/parser/package-info.java (limited to 'chapter29/src/main/java/com/seaofnodes/simple/parser') diff --git a/chapter29/src/main/java/com/seaofnodes/simple/parser/Allocations.java b/chapter29/src/main/java/com/seaofnodes/simple/parser/Allocations.java new file mode 100644 index 00000000..c5b8566b --- /dev/null +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/Allocations.java @@ -0,0 +1,199 @@ +package com.seaofnodes.simple.parser; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.Ary; + +/** Allocation expressions and declaration-side allocation helper graphs. */ +final class Allocations { + private final Parser P; + + Allocations(Parser P) { this.P = P; } + + /** + Parse an allocation + */ + Node parseNew() { + Type t = P.types.parseType(); + if( t==null ) { + String tname = P._lexer.matchId(); + if( tname==null || Parser.KEYWORDS.contains(tname) ) + throw P.error("Expected a type"); + t = P.types.forwardRefType(tname); + } + // Parse ary[ length_expr ] + if( P.match("[") ) { + if( !t.makeZero().isa(t) ) + throw P.error("Cannot allocate a non-nullable, since arrays are always zero/null filled"); + Node len = P.expressions.parseAssignment().keep(); + P.require("]"); + return allocArray(P.types.typeAry(t,false),len); + } else { + if( !(t instanceof TypeMemPtr tmp) ) + throw P.error("Cannot allocate a "+t.str()); + return allocStruct(tmp._obj); + } + } + + private Node allocStruct(TypeStruct ts) { + Ary ctorArgs = constructorArgs(); + // A field declaration can leave a short forward type name in TYPES. + // Allocation happens in lexical context, so resolve that short name + // to the completed nested type before selecting its class helper. + String typeName = ts._name.indexOf('.') == -1 ? P.types.fullTypeName(ts._name) : ts._name; + Type resolved = Parser.TYPES.get(typeName); + if( resolved instanceof TypeStruct rts ) ts = rts; + TypeStruct clz = (TypeStruct)Parser.TYPES.get(Parser.addClzPrefix(typeName)); + if( clz==null ) + throw P.error("Unknown struct type '" + ts._name + "'"); + Field afld = clz.field(""); + Node alloc; + if( afld != null ) { + TypeFunPtr tfp = (TypeFunPtr)afld._t; + FunNode fun = P._code.link(tfp); + alloc = fun==null + ? new FRefNode((Parser.addClzPrefix(typeName)+".").intern(),P.loc()) + : new FunPtrNode(tfp,P._code._start,fun.ret()).peephole(); + } else { + if( !ts._fref ) + throw P.error("Constructor arguments for '" + ts._name + "' but no constructor is defined"); + Type[] sig = new Type[ctorArgs._len]; + for( int i = 0; i").intern(),P.loc(), + TypeFunPtr.make(false,sig,TypeMemPtr.make(ts))); + } + Ary args = new Ary<>(Node.class); + args.add(P.ctrl()); args.add(P.mem()); + for( Node arg : ctorArgs ) args.add(arg.unkeep()); + args.add(alloc); + return P.functions.functionCall(args); + } + + private Ary constructorArgs() { + Ary args = new Ary<>(Node.class); + if( !P.match("(") ) + return args; + P.functions.arguments(args); + P.require(")"); + return args; + } + + private Node allocArray(TypeStruct ts, Node len) { + Field lenFld = ts.field("#" ); + Field bodyFld = ts.field("[]"); + + ConFldOffNode base = Parser.off(ts, "[]"); + int scale = ts.aryScale(); + Node size = P.peep(new AddNode(base,P.peep(new ShlNode(null,len,P.con(scale))))); + + // Build a NewNode; takes in and puts out all aliases. + NewNode nnn = new NewNode(ts, P.ctrl(), size ).init(); + ProjNode self = new ProjNode(nnn,0,ts.str()).init().keep(); + ProjNode smem = new ProjNode(nnn,1,"#selfMem").init().keep(); + + // Store length. Rest of array is zero'd via CALLOC during CodeGen. + // Length is casted to sanity. + // TODO: Needs runtime check. + Node st = P.peep(new StoreNode(null, "#", 1, TypeInteger.U32, null, smem, self, Parser.off(ts,"#"), len.unkeep(), true)); + + // TODO: Allow add-on "constructor" to init the array elements + + Node prior = P.mem(); + Node esc = P.peep(new EscapeNode(lenFld,self,st,prior)); + P.mem(P.mergeAlias(prior,lenFld._alias,esc)); + prior = P.mem(); + esc = P.peep(new EscapeNode(bodyFld,self,smem,prior)); + P.mem(P.mergeAlias(prior,bodyFld._alias,esc)); + smem.unkeep(); + return self.unkeep(); + } + + Node newString(String s) { + TypeStruct ts = P.types.typeAry(TypeInteger.U8,true); + int lenAlias = ts.field("#" )._alias; + int elemAlias = ts.field("[]")._alias; + TypeConAryB body = TypeConAryB.make(s); + TypeInteger slen = TypeInteger.constant(s.length()); + // Make a TMP, not-null (byte)2, singleton (true) (requires text + // strings are hash-interned), with a TypeStruct having a constant + // array body. + TypeMemPtr str = TypeMemPtr.make((byte)2,TypeStruct.makeAry("[]u8", slen, lenAlias, body, elemAlias, true),true); + assert str.isConstant(); + return P.con(str.makeRO()); + } + + // Build the declaration-side allocation helper. Allocation sites only + // call this function; all layout, initialization and publication choices + // are made here, where the complete struct and constructor are known. + TypeFunPtr makeAllocator(TypeStruct ts, ReturnNode initRet, Field ctorFld) { + TypeFunPtr ctor = ctorFld==null ? null : (TypeFunPtr)ctorFld._t; + int nargs = ctor==null ? 0 : ctor.nargs()-2; // Hide self and selfMem + Type[] atypes = new Type[nargs]; + for( int i = 0; i").intern(); + + int oldUID = P._code.UID(); + FunNode fun = (FunNode)new FunNode(P.loc(),sig,name,P._ref,null,P._ref._start).peephole(); + P._code.link(fun); + Node rpc = new ParmNode("$rpc",0,TypeRPC.BOT,fun,ConstantNode.seed(TypeRPC.BOT).peephole()).peephole(); + Node pub = new ParmNode(ScopeNode.MEM0,1,TypeMem.BOT,fun, + new ProjNode(P._ref._start,1,ScopeNode.MEM0).peephole()).peephole(); + Node[] parms = new Node[nargs]; + for( int i = 0; i P.statements.parseStatement(); // if( pred ) stmts; + case ":" -> P.expressions.parseAssignment(); // pred ? asgn; + case "&&" -> P.expressions.parseLogical(); // pred && expr + case "||" -> pred; // pred || expr_is_ignored + default -> throw TODO(); + }; + lhs.keep(); + P._scope.removeGuards(ifT); + + // See if a one-sided def was made: "if(pred) int x = 1;" and throw. + // See if any forward-refs were made, and copy them to the other side: + // "pred ? n*fact(n-1) : 1" + fScope.balanceIf(P._scope); + + ScopeNode tScope = P._scope; + + // Parse the false side + P._scope = fScope; // Restore scope, then parse else block if any + ifF.unkeep(); // fScope already owns the false control + // Up-cast predicate, even if not else clause, because predicate can + // remain true if the true clause exits: `if( !ptr ) return 0; return ptr.fld;` + P._scope.addGuards(ifF,pred,true); + // Parse false-side flavor + boolean doRHS = false; // RHS is optional for if/else and trinary + Node rhs = switch( fside ) { + case "else" -> (doRHS = P.match(fside)) ? P.statements.parseStatement() : P.con(lhs._type.makeZero()); + case ":" -> (doRHS = P.match(fside)) ? P.expressions.parseAssignment() : P.con(lhs._type.makeZero()); + case "&&" -> P.con(lhs._type.makeZero()); // pred && expr_is_ignored + case "||" -> P.expressions.parseLogical(); // pred || expr + default -> throw TODO(); + }; + rhs.keep(); + P._scope.removeGuards(ifF); + // The RHS of `||` is parsed on the false side, so retain its updated + // control, memory and locals just as an explicit else arm does. + if( doRHS || fside.equals("||") ) + fScope = P._scope; + pred.unkeep(); + + // Check the trinary widening int/flt + if( !fside.equals("else") ) { + rhs = P.conversions.widenInt( rhs.unkeep(), lhs._type ).keep(); + lhs = P.conversions.widenInt( lhs.unkeep(), rhs._type ).keep(); + } + + P._scope = tScope; + P._xScopes.pop(); // Discard pushed from graph display + // See if a one-sided def was made: "if(pred) int x = 1;" and throw. + // See if any forward-refs were made, and copy them to the other side: + // "pred ? n*fact(n-1) : 1" + tScope.balanceIf(fScope); + + // Merge results + RegionNode r = P.ctrl(tScope.mergeScopes(fScope,P.loc())); + Node ret = P.peep(new PhiNode("",r,lhs.unkeep(),rhs.unkeep())); + // Immediately fail e.g. `arg ? 7 : ptr` + ParseException err; + if( !fside.equals("else") && (err = ret.err()) !=null ) throw err; + ret.keep(); + r.peephole(); + return ret.unkeep(); + } +} diff --git a/chapter29/src/main/java/com/seaofnodes/simple/parser/Conversions.java b/chapter29/src/main/java/com/seaofnodes/simple/parser/Conversions.java new file mode 100644 index 00000000..d50e2031 --- /dev/null +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/Conversions.java @@ -0,0 +1,72 @@ +package com.seaofnodes.simple.parser; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; + +/** Shared declaration, assignment, and return conversions. */ +final class Conversions { + private final Parser P; + + Conversions(Parser P) { this.P = P; } + + // Widen ints to floats; narrow wide int types. + // Early error if types do not match variable. + Node convertExpr( Node expr, Type t ) { + if( !expr._type.accessISA(t) ) + throw P.error("Type "+expr._type.str()+" is not of declared type "+t.str()); + if( t instanceof TypeMemPtr tmp && tmp.isFinal() ) + expr = P.peep(new ReadOnlyNode(expr)); + // A FunPtr carries the semantic edge to its function's Return. Do not + // hide that edge behind a Convert which can fold to a plain constant. + if( expr instanceof FunPtrNode && t instanceof TypeFunPtr ) + return expr; + // Auto-widen array to i64 (cast ptr to raw int bits) + if( t == TypeInteger.BOT && expr._type instanceof TypeMemPtr tmp && tmp._obj.isAry() ) + return P.peep(new AddNode(P.peep(new PtrToIntNode(expr)),Parser.off(tmp._obj,"[]"))); + // Widen ints to floats, narrow wide types + return P.peep(new ConvertNode(t,expr)); + } + + // Inferred `var` declarations describe writable slots, not the exact + // value used to initialize them. Explicitly typed locals retain the + // user's nullability and numeric-width guarantees; `val` retains the + // initializer's precise type. + static Type mutableInferredType(Type t) { + return switch( t ) { + case TypeInteger ti -> TypeInteger.BOT; + case TypeFloat tf -> TypeFloat.F64; + case TypeMemPtr tmp -> tmp.makeVar(); + case TypeFunPtr tfp -> tfp; + case TypeConAry a -> a; + case TypePtr ptr -> TypePtr.PTR; + case TypeScalar ts -> TypeScalar.BOT; + default -> t; + }; + } + + Type constructorFieldType(Type t) { + if( t instanceof TypeMemPtr ptr && ptr._obj.isConAry() ) { + TypeStruct declared = (TypeStruct)Parser.TYPES.get(ptr._obj._name); + TypeStruct shape = P.types.typeAry(declared._fields[1]._t,ptr._obj._fields[1]._final); + return TypeMemPtr.make((byte)2,shape,false).withAccess(ptr._ro); + } + return mutableInferredType(t); + } + + // Seed an inferred return merge with the declared numeric family instead + // of a transient constant/range. Pointer nullability remains part of the + // inferred function result and is combined by the later Phi. + static Type inferredReturnType(Type t) { + return switch( t ) { + case TypeInteger ti -> TypeInteger.BOT; + case TypeFloat tf -> TypeFloat.F64; + default -> t; + }; + } + + Node widenInt( Node expr, Type t ) { + return (expr._type instanceof TypeInteger || expr._type==Type.NIL) && t instanceof TypeFloat + ? P.peep(new ToFloatNode(expr)) : expr; + } + +} diff --git a/chapter29/src/main/java/com/seaofnodes/simple/parser/Declarations.java b/chapter29/src/main/java/com/seaofnodes/simple/parser/Declarations.java new file mode 100644 index 00000000..92e978b6 --- /dev/null +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/Declarations.java @@ -0,0 +1,164 @@ +package com.seaofnodes.simple.parser; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.node.ScopeNode.Kind; +import com.seaofnodes.simple.type.*; + +/** Local/field bindings and native symbol declarations. */ +final class Declarations { + private final Parser P; + + Declarations(Parser P) { this.P = P; } + + /** + * Parse declaration or expression statement + * declStmt = type var['=' exprAsgn][, var['=' exprAsgn]]* ';' | exprAsgn ';' + *

+ * exprAsgn = var '=' exprAsgn | expr + */ + Node parseDeclarationStatement() { + int old = P.pos(); + Type t = P.types.parseType(); + if( P.peek('.') ) // Ambiguity static vars: "type.var", parse as expression + { P.pos(old); t = null; } + if( t == null ) + return P.require(P.expressions.parseAssignment(),";"); + + // now parse var['=' asgnexpr] in a loop + Node n = parseDeclaration(t); + while( P.match(",") ) + n = parseDeclaration(t); + return P.require(n,";"); + } + + // The binding modifier sits immediately before the name. It never + // changes permissions on the referenced object. + boolean bindingFinal(Type t) { + if( P.match("!") ) return false; + if( P.match("~") ) return true; + return t==Type.TOP || t instanceof TypeNil; + } + + /** Parse final: [!|~]var['=' asgn] + */ + private Node parseDeclaration(Type t) { + assert t!=null; + // Has var/val instead of a user-declared type + boolean inferType = t==Type.TOP || t==Type.BOTTOM; + boolean xfinal = bindingFinal(t); + Lexer loc = P.loc(); + String name = P.requireId(); + // Optional initializing expression follows + boolean fld_final = false; // Field is final, but not deeply final + boolean uninit = false; // Required non-null constructor field + Node expr; + if( P.match("=") ) { + if( isExternDecl() ) { + if( !(t instanceof TypeFunPtr) ) { + Node ptr = externData(name,t); + // The lexical binding is a fixed address; its contents are mutable. + if( !P._scope.define(name,t,true,ptr,loc) ) + throw Parser.error("Redefining name '"+name+"'",loc); + P._scope.lookup(name)._extern = P._code.externAlias(name); + return P._code.ZERO; + } + expr = externDecl(name,t); + t = expr._type; // Upgrade declared type to the exact extern decl type + } else if( P.structs.isConstructorDecl(name) ) { + expr = P.functions.parseConstructor(name); + } else { + expr = P.expressions.parseAssignment(); + } + // var/val, then type comes from expression + if( inferType ) { + if( expr._type==Type.NIL ) + throw P.error("a not-null/non-zero expression"); + t = expr._type; + if( !xfinal ) t = Conversions.mutableInferredType(t); + // Instance fields may change until the constructor finishes. + // Keep the declared family/access, not the default's constant + // value or string contents. Class constants remain static. + else if( P._scope.klast() instanceof Kind.Func fun && FunNode.isInstance(fun._name) && !(t instanceof TypeFunPtr) ) + t = P.conversions.constructorFieldType(t); + } + + // expr is a constant function + if( t instanceof TypeFunPtr decl && expr._type instanceof TypeFunPtr tfp && tfp.isConstant() ) { + t = decl.makeFrom(tfp.fidx()); + FunNode fun = P._code.link(tfp); + if( fun != null ) + fun.setName(name); // Assign debug name to Simple function + } + + } else { + // Since no initializer, not-final but might need an initializer + + // Need an expression to infer the type. + // Also, if not-null then need an initializing expression. + // Allowed in a class def, because type/init will happen in the constructor. + if( (inferType || (t instanceof TypeNil tn && !tn.nullable() )) && !P._scope.inConstructor() ) + throw P.errorSyntax("=expression"); + // Initial value for uninitialized struct fields. + expr = switch( t ) { + // Required pointers retain their declared shape, but include + // null until every constructor path assigns them. + case TypeNil tn -> tn.nullable() ? P.con(Type.NIL) : P.con(t.meet(Type.NIL)); + case TypeInteger ti -> xfinal ? P.con(Type.BOTTOM) : P._code.ZERO; + case TypeFloat tf -> P.con(xfinal ? Type.BOTTOM : TypeFloat.FZERO); + // Bottom signals type inference: they must be initialized in + // the constructor and that's when we'll discover the type. + case Type tt -> { assert tt==Type.BOTTOM; yield P.con(tt); } + }; + // Every non-null pointer without a default is constructor-required. + // Without `!` it is also shallow-final; mutability and definite + // initialization are independent properties. + if( (xfinal && !(t instanceof TypeNil)) || (t instanceof TypeNil tn && !tn.nullable()) ) { + uninit = true; + if( xfinal ) fld_final = true; + } + } + + // Lift expression, based on type + // Do not let an authoritative Convert hide the nullable + // not-yet-initialized state from constructor-local type flow. + Node lift = uninit ? expr : P.conversions.convertExpr(expr, t); + + // Define a new name + if( !P._scope.define(name,t,xfinal || fld_final,lift, loc) ) + throw P.error("Redefining name '" + name + "'", loc); + P._scope.lookup(name)._uninit = uninit; + return lift; + } + + // Just after parsing "type foo = " can parse `"C"` + private boolean isExternDecl( ) { + int old = P.pos(); + String s = P._lexer.parseString(); + if( "C".equals(s) ) return true; + P.pos(old); + return false; + } + // External linked constant + private ConstantNode externDecl( String ex, Type t ) { + if( t instanceof TypeFunPtr tfp ) { // Generic TFP from type parse + int fidx = P._code.fidx(P._ref._cname); // Get a FIDX + tfp = tfp.makeFrom(fidx); // Become a constant + P._code.externFunc(fidx,ex); // Map fidx to extern name + t = tfp; + } + return (ExternNode)(new ExternNode(t,ex).peephole()); + } + + // A lexical C binding has a singleton namespace with one external field. + // The namespace occupies no storage; its field offset supplies the address. + private Node externData(String name, Type t) { + if( !(t instanceof TypeInteger) && !(t instanceof TypeFloat) ) + throw P.error("C data binding requires an integer or float type"); + String cname = ("C:"+name).intern(); + TypeStruct ts = TypeStruct.make(cname,false,Field.make(name,t,P._code.externAlias(name),false,true)); + Type old = Parser.TYPES.putIfAbsent(cname,ts); + if( old!=null && old!=ts ) + throw P.error("Conflicting types for C data '"+name+"'"); + return P.con(TypeMemPtr.make((byte)2,ts,true)); + } +} diff --git a/chapter29/src/main/java/com/seaofnodes/simple/parser/Expressions.java b/chapter29/src/main/java/com/seaofnodes/simple/parser/Expressions.java new file mode 100644 index 00000000..c3971c63 --- /dev/null +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/Expressions.java @@ -0,0 +1,394 @@ +package com.seaofnodes.simple.parser; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.parser.Parser.ParseException; +import com.seaofnodes.simple.type.*; + +import static com.seaofnodes.simple.util.Utils.TODO; + +/** Recursive-descent expression precedence, from assignment down to primaries. */ +final class Expressions { + private final Parser P; + + Expressions(Parser P) { this.P = P; } + + /** Parse: [name '='] expr + */ + Node parseAssignment() { + int old = P.pos(); + String name = P._lexer.matchId(); + // Just a plain expression, no assignment. + // Distinguish `var==expr` from `var=expr` + if( name==null || Parser.KEYWORDS.contains(name) || !P.matchOpx('=','=') ) + { P.pos(old); return parseExpression(); } + + // Find variable to update + Var def = P._scope.lookup(name); + if( def==null ) + throw P.error("Undefined name '" + name + "'"); + + if( def._extern!=0 ) // Parse the C binding as a memory lvalue + { P.pos(old); return parseExpression(); } + + P.references.checkAssignment(def); + return P.references.assign(def,parseAssignment()); + } + + /** + * Parse an expression of the form: + * + * 

+     *     expression : logicalExpression ('?' assignment (':' assignment)?)?
+     *
+ * @return an expression {@link Node}, never {@code null} + */ + private Node parseExpression() { + Node expr = parseLogical(); + return P.match("?") ? P.controlflow.conditional(expr,":") : expr; + } + + /** + * Parse a logical expression + * + * 
+     *     logicalExpression : bitwiseExpression (('&&' | '||') logicalExpression)?
+     *
+ * @return a bitwise expression {@link Node}, never {@code null} + */ + + Node parseLogical() { + Node lhs = parseBitwise(); + while (true) { + if( P.match("&&") ) lhs = P.controlflow.conditional(lhs, "&&"); + else if( P.match("||") ) lhs = P.controlflow.conditional(lhs, "||"); + else break; + } + return lhs; + } + + private Node parseBitwise() { + Node lhs = parseEquality(); + while( true ) { + if( P.matchOp('&') ) lhs = new AndNode(P.loc(),lhs,null); + else if( P.matchOp('|') ) lhs = new OrNode(P.loc(),lhs,null); + else if( P.match ("^") ) lhs = new XorNode(P.loc(),lhs,null); + else break; + lhs.setDef(2,parseEquality()); + lhs = P.peep(lhs); + } + return lhs; + } + + /** + * Parse an eq/ne expression + */ + private Node parseEquality() { + Node lhs = parseComparison(); + while( true ) { + boolean eq = false; + if( P.match("==") ) eq = true; + else if( !P.match("!=") ) break; + lhs.keep(); + Node rhs = parseComparison(); + lhs = P.peep(new BoolNode.EQ(lhs.unkeep(),rhs)); + if( !eq ) lhs = P.peep(new NotNode(lhs)); + } + return lhs; + } + + /** + * Parse an expression of the form: + * + * 
+     *     expr : shiftExpr < shiftExpr <= shiftExpr...
+     *     expr : shiftExpr > shiftExpr >= shiftExpr...
+     *
+ * @return an comparator expression {@link Node}, never {@code null} + */ + private Node parseComparison() { + Node lhs = parseShift(); + int dir = parseCompDir(); + // No compare + if( dir==0 ) return lhs; + lhs.keep(); + + // Compare + Node rhs = parseShift().keep(); + Node cmp = makeCompBool(dir,lhs.unkeep(),rhs).keep(); // Convert to a bool + + // Stacked compares? + int dir0 = parseCompDir(); + if( dir0 == 0 ) { + rhs.unkill(); + return cmp.unkeep(); + } + + // Keep the middle operand separately from the boolean result. + // The next test compares adjacent operands, not that boolean. + Node ifNode = new IfNode(P.ctrl(), cmp.unkeep()).peephole(); + Node ifT = new CProjNode(ifNode. keep(), 0, "True" ).peephole().keep(); + Node ifF = new CProjNode(ifNode.unkeep(), 1, "False").peephole(); + // False side does nothing but capture memory & side-effects + ScopeNode fail = P._scope.dup(); + fail.ctrl(ifF); + + // Loop over stacked compares. Each loop moves the old RHS to become + // the new LHS, so e.g. (a < b < c < d) compares (LHS:a < RHS:b) then + // compares (LHS:b < RHS:c) then (LHS:c < RHS:d), etc. + while( dir0 != 0 ) { + if( Math.abs(dir) != Math.abs(dir0) ) + throw P.error("Mixing relational directions in a chained relational test"); + // True side parses next arm of test + P.ctrl(ifT.unkeep()); + lhs = rhs; // Reuse the previous RHS exactly once + rhs = parseShift().keep(); + cmp = makeCompBool(dir0,lhs.unkeep(),rhs); // Convert to a bool + ifNode = new IfNode(P.ctrl(), cmp).peephole(); + ifT = new CProjNode(ifNode. keep(), 0, "True" ).peephole().keep(); + ifF = new CProjNode(ifNode.unkeep(), 1, "False").peephole(); + // Merge result into the fail case + P.ctrl(ifF); + fail.mergeScopes(P._scope.dup(), P.loc()).peephole(); + // Check next stacked compare + dir0 = parseCompDir(); + } + rhs.unkill(); + P.ctrl(ifT.unkeep()); + RegionNode r = fail.mergeScopes(P._scope, P.loc()).init(); + P._scope = fail; + return new PhiNode("", r,P.con(0),P.con(1)).peephole(); + } + + private int parseCompDir() { + if( P.match("<=") ) return -1; // Negative for "equals-or-less" + if( P.match(">=") ) return -2; // 1 for <, 2 for > + if( P.match("<" ) ) return 1; // Positive for just "less" + if( P.match(">" ) ) return 2; + return 0; + } + + private Node makeCompBool( int dir, Node lhs, Node rhs ) { + if( Math.abs(dir)==2 ) + { Node tmp = lhs; lhs = rhs; rhs = tmp; } + Node cmp = dir < 0 ? new BoolNode.LE(lhs,rhs) : new BoolNode.LT(lhs,rhs); + return P.peep(cmp); + } + + /** + * Parse an additive expression + * + * 
+     *     shiftExpr : additiveExpr (('<<' | '>>' | '>>>') additiveExpr)*
+     *
+ * @return a shift expression {@link Node}, never {@code null} + */ + private Node parseShift() { + Node lhs = parseAddition(); + while( true ) { + if( P.match("<<") ) lhs = new ShlNode(P.loc(),lhs,null); + else if( P.match(">>>")) lhs = new ShrNode(P.loc(),lhs,null); + else if( P.match(">>") ) lhs = new SarNode(P.loc(),lhs,null); + else break; + lhs.setDef(2,parseAddition()); + ParseException err; + if( (err = lhs.err()) != null ) + throw err; + lhs = P.peep(lhs); + } + return lhs; + } + + /** + * Parse an additive expression + * + * 
+     *     additiveExpr : multiplicativeExpr (('+' | '-') multiplicativeExpr)*
+     *
+ * @return an add expression {@link Node}, never {@code null} + */ + private Node parseAddition() { + Node lhs = parseMultiplication(); + while( true ) { + if( P.match("+") ) lhs = new AddNode(lhs,null); + else if( P.match("-") ) lhs = new SubNode(lhs,null); + else break; + lhs.setDef(2,parseMultiplication()); + lhs = P.peep(lhs); + } + return lhs; + } + + /** + * Parse an multiplicativeExpr expression + * + * 
+     *     multiplicativeExpr : unaryExpr (('*' | '/') unaryExpr)*
+     *
+ * @return a multiply expression {@link Node}, never {@code null} + */ + private Node parseMultiplication() { + var lhs = parseUnary(); + while( true ) { + if( P.match("*") ) lhs = new MulNode(lhs,null); + else if( P.match("/") ) lhs = new DivNode(lhs,null); + else break; + lhs.setDef(2,parseUnary()); + lhs = P.peep(lhs); + } + return lhs; + } + + /** + * Parse a unary minus expression. + * + * 
+     *     unaryExpr : ('-') unaryExpr | '!') unaryExpr | postfixExpr | primaryExpr | '--' Id | '++' Id
+     *
+ * @return a unary expression {@link Node}, never {@code null} + */ + private Node parseUnary() { + // Pre-dec/pre-inc + int old = P.pos(); + if( P.match("--") || P.match("++") ) { + int delta = P._lexer.peek(-1)=='+' ? 1 : -1; // Inc vs Dec + int start = P.pos(); + String name = P._lexer.matchId(); + Var var = name==null ? null : P._scope.lookup(name); + if( var!=null && !(var.type() instanceof TypeMemPtr) ) { + if( var._extern==0 && var._final && !P._scope.canInit(var) ) + throw P.error("Cannot reassign final '"+var._name+"'"); + // Resolve fields just as a read or postfix update does. Updating + // their declaration's local slot would silently lose the Store. + P.pos(start); + return parsePrimary(delta); + } + // Reset, try again + P.pos(old); + } + if (P.match("-")) return P.peep(new MinusNode(parseUnary())); + if (P.match("!")) return P.peep(new NotNode(parseUnary())); + // Else be a primary expression + return parsePrimary(); + } + + /** + * Parse a primary expression: + * + * 
+     *     primaryExpr : integerLiteral | "string" | 'char' | true | false | null |
+     *                   new Type | '(' expression ')' | Id['++','--'] |
+     *                   type['.' Id]*
+     *
+ * @return a primary {@link Node}, never {@code null} + */ + private Node parsePrimary() { return parsePrimary(0); } + + // pre is +/-1 for a prefix update of a known name, zero otherwise. + private Node parsePrimary(int pre) { + if( P._lexer.isNumber(P._lexer.peek()) ) return parseLiteral(); + if( P._lexer.peek('"') ) return parsePostfix(P.allocations.newString(P._lexer.parseString())); + if( P.matchx("true" ) ) return P.con(1); + if( P.matchx("false") ) return P._code.ZERO; + if( P.matchx("null" ) ) return P.con(Type.NIL); + if( P.match ("'" ) ) return parseChar(); + if( P.match ("(" ) ) return parsePostfix(P.require(parseAssignment(), ")")); + if( P.matchx("new" ) ) return parsePostfix(P.allocations.parseNew()); + if( P.match ("{" ) ) return parsePostfix(P.require(P.functions.parseFunction(),"}")); + + int pos = P.pos(); + // Expect an identifier now + String id = P._lexer.matchId(); + if( id == null || Parser.KEYWORDS.contains(id) ) + throw P.errorSyntax("an identifier or expression"); + int pos2 = P.pos(); + return P.references.parseName(id,pre,pos,pos2); + } + + // Check for assign-update, "x += e0". + // Returns "x + e0"; the caller assigns value. + // if ch is postfix, then lhs is kept and caller will unkeep and return it. + Node opAssign( char ch, Node lhs, Type t ) { + // RHS of the update. + lhs.keep(); // Alive across parseAssignment + Node rhs = + (byte)ch == 1 ? P.con( 1) : // var++ + (byte)ch == -1 ? P.con(-1) : // var-- + parseAssignment(); // var op= rhs + if( !Parser.postfix(ch) ) lhs.unkeep(); // Allow to die in next peep + // 4 cases: + // int + int ==>> narrow int + // int + flt ==>> error, caller must fail assigning flt into int + // flt + int ==>> use float op, wrap toFloat() + // flt + flt ==>> use float op + Node op = switch(ch) { + case 1, (char)-1, + '+' -> new AddNode(lhs,rhs); + case '-' -> new SubNode(lhs,rhs); + case '*' -> new MulNode(lhs,rhs); + case '/' -> new DivNode(lhs,rhs); + case '|' -> new OrNode(null,lhs,rhs); + case '&' -> new AndNode(null,lhs,rhs); + case '^' -> new XorNode(P.loc(),lhs,rhs); + case Lexer.SHL -> new ShlNode(P.loc(),lhs,rhs); + case Lexer.SAR -> new SarNode(P.loc(),lhs,rhs); + case Lexer.SHR -> new ShrNode(P.loc(),lhs,rhs); + default -> throw TODO(); + }; + // Convert to float ops, or narrow int types; error if not declared type. + // Also, if postfix LHS is still keep() + return P.conversions.convertExpr(P.peep(op),t); + } + + /** + * Parse postfix expression; this can be a field expression, an array + * lookup or a postfix operator like '#' + * + * 
+     *     expr ('.' FIELD)* [ = expr ]       // Field reference
+     *     expr '#'                           // Postfix unary read operator
+     *     expr ['++' | '--' ]                // Postfix unary write operator
+     *     expr ('[' expr ']')* = [ = expr ]  // Array reference
+     *     expr '(' [args,]* ')'              // Function call
+     *
+ */ + Node parsePostfixMethod(Node expr, Node self) { + // TODO: This is too broad because the parser lacks strong types here. + // Some normal functions can end up with a "self" argument. + + // Self method call? Self is a TMP-not-CLZ, then assume and pass self. + if( P.match("(") ) { + expr = parsePostfix(P.require(P.functions.functionCall(expr,self),")")); + } else if( expr != self ) + self.isKill(); // Not a method call, no need for self + return parsePostfix(expr); + } + Node parsePostfix(Node expr) { + P._lexer.skipWhiteSpace(); + Lexer site = P.loc(); + String name; + if( P.match(".") ) name = P.requireId(); + else if( P.match("#") ) name = "#"; + else if( P.match("[") ) name = "[]"; + // Can get here without an explicit receiver: "f()" or + // "self.method()(next)(next)(next)". Pass the current function self. + else if( P.match("(") ) return parsePostfix(P.require(P.functions.functionCall(expr,P.references.defaultSelf()),")")); + else return expr; // No postfix + + return P.references.parseField(expr,name,0,site); + } + + /** + * Parse integer literal + * + * 
+     *     integerLiteral: [1-9][0-9]* | [0]
+     *     floatLiteral: [digits].[digits]?[e [digits]]?[f]?
+     *
+ */ + private ConstantNode parseLiteral() { return P.con(P._lexer.parseNumber()); } + + // Already parsed "'" + Node parseChar() { + return P.require(P.con(TypeInteger.constant(P._lexer.parseChar())),"'"); + } +} diff --git a/chapter29/src/main/java/com/seaofnodes/simple/parser/Functions.java b/chapter29/src/main/java/com/seaofnodes/simple/parser/Functions.java new file mode 100644 index 00000000..d848b0e3 --- /dev/null +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/Functions.java @@ -0,0 +1,346 @@ +package com.seaofnodes.simple.parser; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.node.ScopeNode.Kind; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.Ary; +import java.util.BitSet; + +import static com.seaofnodes.simple.util.Utils.TODO; + +/** Function expressions, parameters, calls, and function entry/exit graphs. */ +final class Functions { + private final Parser P; + // Merge all function exits here. + ScopeNode _returnScope; + + Functions(Parser P) { this.P = P; } + + /** + * Parse a function body; the caller will parse the surrounding "{}" + * + * 
+     *     { [type arg,]* -> expr }
+     *     { -> statements } // The no-argument function
+     *
+ */ + Node parseFunction() { + Ary ts = new Ary<>(Type.class); + Ary ids = new Ary<>(String.class); + BitSet finals = new BitSet(); + Type self = P.types.implicitSelfType(); + ts.push(self); + ids.push(self == TypePtr.PTR ? "#self" : "self"); + + // Parse other arguments + P._lexer.skipWhiteSpace(); + Lexer loc = P.loc(); // First argument location + parameters(ts,ids,finals); + // Make a concrete function type, with a fidx + TypeFunPtr tfp = TypeFunPtr.make1((byte)2,true,ts.asAry(),Type.BOTTOM,P._code.fidx(P._ref._cname)); + ReturnNode ret = parseFunctionBody(tfp,loc,finals,ids.asAry()); + return new FunPtrNode(tfp,P._code._start,ret).peephole(); + } + + Node parseConstructor(String name) { + P.require("{"); + Ary ts = new Ary<>(Type.class); + Ary ids = new Ary<>(String.class); + BitSet finals = new BitSet(); + TypeStruct self = P._scope.constructorSelf(); + assert self != null; + ts.push(TypeMemPtr.make(Structs.constructorRecv(self))); + ids.push("self"); + // Explicit constructors use the same hidden allocation arguments as + // : public memory is the call memory edge (index 1), followed by + // self (index 2) and the private, unescaped object memory (index 3). + ts.push(TypeMem.makePrivate(self)); + ids.push("#selfMem"); + + P._lexer.skipWhiteSpace(); + Lexer loc = P.loc(); + parameters(ts,ids,finals); + TypeFunPtr tfp = TypeFunPtr.make1((byte)2,true,ts.asAry(),TypeMem.makePrivate(self),P._code.fidx(P._ref._cname)); + Node[] preParse = P._scope.save(); + ReturnNode ret = parseBody((self._name+"."+name).intern(),tfp,loc,finals,ids.asAry()); + P._scope.restore(preParse); + P.require("}"); + return new FunPtrNode(tfp,P._code._start,ret).peephole(); + } + + // parameterList followed by the function arrow; callers seed hidden parameters. + private void parameters(Ary ts, Ary ids, BitSet finals) { + while( true ) { + Type t = P.types.parseType(); // Arg type + if( t==null ) break; + finals.set(ids.size(),P.declarations.bindingFinal(t)); + String id = P.requireId(); + ts .push(t ); // Push type/arg pairs + ids.push(id); + P.match(","); + } + P.require("->"); + } + + /** + * Parse function call arguments; caller will parse the surrounding "()" + * 
+     *   ( arg* )
+     *
+ */ + Node functionCall(Node fcn, Node self) { + Lexer site = P.loc(); + site._position--; // Opening '('; arguments can contain nested calls. + if( fcn._type == Type.NIL ) + throw P.error("Calling a null function pointer"); + fcn.keep(); // Keep while parsing args + + Ary args = new Ary<>( Node.class ); + args.push(null); // Space for ctrl,mem + args.push(null); + if( self != null ) // Method call has a self + args.push(self.keep()); + arguments(args); + // Control & memory after parsing args + args.set(0,P.ctrl().keep()); + args.set(1,P.mem().keep()); + args.push(fcn); // Function pointer + // Unkeep them all + for( Node arg : args ) + arg.unkeep(); + return functionCall(args,site); + } + + Node functionCall( Ary args ) { + return functionCall(args,P.loc()); + } + + Node functionCall( Ary args, Lexer site ) { + // Dead into the call? Skip all the node gen + if( P.ctrl()._type == Type.XCONTROL ) { + for( Node arg : args ) + if( arg.isUnused() ) + arg.kill(); + return P.con(Type.TOP); + } + + // Into the call + CallNode call = (CallNode)new CallNode(site, args.asAry()).peephole(); + // Post-call setup + CallEndNode cend = (CallEndNode)new CallEndNode(call,TypeRPC.constant(P._code.rpc(P._ref._cname))).peephole(); + call.peephole(); // Rerun peeps after CallEnd, allows early inlining + cend = (CallEndNode)cend.keep().peephole(); // TODO: Might inline + // Control from CallEnd + P.ctrl(new CProjNode(cend,0,ScopeNode.CTRL).peephole()); + // Memory from CallEnd + Node mem = new ProjNode(cend,1,ScopeNode.MEM0).peephole(); + P.mem(mem); + // Call result + return new ProjNode(cend.unkeep(),2,"#2").peephole(); + } + + // argumentList; returns kept values and leaves the closing parenthesis to the caller. + void arguments(Ary args) { + while( !P.peek(')') ) { + Node arg = P.expressions.parseAssignment(); + if( arg==null ) break; + args.push(arg.keep()); + if( !P.match(",") ) break; + } + } + + /** + * Parses a function body, assuming the header is parsed. + */ + + private ReturnNode parseFunctionBody( TypeFunPtr sig, Lexer loc, BitSet finals, String[] ids) { + // Record & restore the existing scope vars. The function parse might + // update fields, so when the parse is done reset back to the pre-parse + // state. + Node[] preParse = P._scope.save(); + + // Parse function body normally + ReturnNode ret = parseBody(null, sig,loc,finals,ids); + + // Reset all fields to pre-parse days + P._scope.restore(preParse); + return ret; + } + + // Parse a function body + + // Stack the {break,continue,return} scopes and a new lexical scope. + // Build a FunNode and parameters, extending scope by parm names. + // Parse the function body + // - while( not end-of-function ) + // - - parseStatement + // - - If isInit, also incrementally extend the self-type. + // If isInit + // - upgrade and close the self-type + // - Gather fields and store values + // - returns self, not last + // Unstack the {break,continue,return} scopes. + + ReturnNode parseBody( String funName, TypeFunPtr sig, Lexer loc, String[] ids) { + return parseBody(funName, sig, loc, null, ids); + } + + ReturnNode parseBody( String funName, TypeFunPtr sig, Lexer loc, BitSet finals, String[] ids) { + Structs.Constructor outerCtor = P.structs._pendingCtor; + P.structs._pendingCtor = null; + boolean isInit = FunNode.isInit(funName); + boolean isCtor = isInit || P.structs.isExplicitConstructorName(funName); + String typeName = isCtor ? ((TypeMemPtr)sig._sig[0])._obj._name : null; + + // Stack parser state on the local Java stack, and unstack it later + P._scope.push(new Kind.Func(funName,isCtor && !funName.endsWith("."))); + ScopeNode breakScope = P.statements._breakScope; P.statements._breakScope = null; + ScopeNode continueScope = P.statements._continueScope; P.statements._continueScope = null; + ScopeNode returnScope = _returnScope; _returnScope = null; + + int oldUID = P._code.UID(); // Used to approximate function size + FunNode fun = enterFunction(funName,sig,loc,finals,ids); + Node rpc = fun.parm(0); + if( isCtor && !isInit ) P.structs.constructorDefaults(typeName,fun,loc); + if( fun.isClz() ) P.structs.beginClassInit(fun,loc); + + // Parse the function body. + Node last = P._code.ZERO; // Last statement as the default result + + int nvar = 0; + while (!P.peek('}') && !P._lexer.isEOF()) { + // Parse a statement; record last statement as default return + last = P._code.add(P.statements.parseStatement()); + // For and , local vars are really struct fields and + // get exposed as discovered. This allows late local functions to + // use early declared fields. + if( isInit ) + nvar = P.structs.updateSelfAsFieldsDiscovered( typeName, nvar ); + } + + if( isInit ) P.structs.finishConstructor(); + P.structs._pendingCtor = outerCtor; + + ParmNode self = fun.parm(2); + // Last expression is the return + if( P.ctrl()._type==Type.CONTROL ) { + // Constructors get special return types + if( fun.isClz() ) { + assert last!=null; + } else if( isCtor ) { + last = fun.parm(3); + } + addReturn(last); + // exit path is now dead (nothing live after a "return") + } + if( isCtor ) + P.structs.upgradeSelfTypeAndStoreFields( typeName, fun.isClz(), self, fun.parm(3), isInit ); + + // Build a return from the _returnScope. + // Can be no returns for never-exit functions + Node rctl = _returnScope==null ? P._code.XCTRL : _returnScope.ctrl().peephole(); + Node rmem = rctl==P._code.XCTRL ? P.con(TypeMem.TOP) : _returnScope.mem(); + Node expr = rctl==P._code.XCTRL ? P.con(Type.TOP) : _returnScope._inputs.last().peephole(); + ReturnNode ret = (ReturnNode)P.peep(new ReturnNode(rctl, rmem, expr, rpc, fun)); + fun.setRet(ret); + // Approximate function size, for inlining heuristics + fun._approxUIDs = P._code.UID() - oldUID; + for( Node cend : ret.outs() ) + if( cend instanceof CallEndNode ) + throw TODO(); //_code.add(cend); // have call ends ALREADY? just barely made the Return + + // Export (and keep-alive) functions until prove dead + P._ref.addFun(P._code,fun); + + // Unstack parser state + if( _returnScope != null ) _returnScope.kill(); + _returnScope = returnScope; + P.statements._continueScope = continueScope; + P.statements._breakScope = breakScope; + P._scope.pop(); + + return ret; + } + + private FunNode enterFunction(String funName, TypeFunPtr sig, Lexer loc, BitSet finals, String[] ids) { + FunNode fun = (FunNode)P.peep(new FunNode(P.loc(),sig, funName, P._ref, null, P._ref._start)); + // Once the function header is available, install in linker table - + // allowing recursive functions. Linker matches on declared args and + // exact fidx, and ignores the return (because the fidx will only match + // the exact single function). + P._code.link(fun); + + new ParmNode("$rpc",0,TypeRPC.BOT,fun,ConstantNode.seed(TypeRPC.BOT).peephole()).peephole(); + + // Pre-call the function from Start, with worse-case arguments. This + // represents all the future, yet-to-be-parsed functions calls and + // external calls. + P._scope.ctrl(fun); // Scope control from function + // Private mem alias tracking per function + Node defaultMem = new ProjNode(P._ref._start,1,ScopeNode.MEM0).peephole(); + Node privMem = new ParmNode(ScopeNode.MEM0,1,TypeMem.BOT,fun,defaultMem).peephole(); + P.mem(privMem); + // All args, "as-if" called externally + for( int i = 0; i and - all fields in scope will be live-on-exit + // and stored into `self` and need to have lazy-phi's inserted. + int lexN = P._scope.enclosingFuncOrDecl(); + Kind.Func k = (Kind.Func)P._scope._kinds.at(lexN); + if( FunNode.isInit(k._name) ) { + int nestedLexSize = lexN+1 < P._scope.depth() ? P._scope._kinds.at(lexN+1)._lexSize : P._scope.nIns(); + for( int i = k._lexSize; i and - ALL FIELDS IN LAST SCOPE are live + // and need to have lazy-phi's inserted. + + // And fields might not match.... will need matching Var/define with default values + int rlen = _returnScope.nIns()-1; + RegionNode r = P.ctrl(new RegionNode(null, null,_returnScope.ctrl(), P._scope.ctrl()).init().keep()); + _returnScope._merge(P._scope, r, rlen); + Node oldExpr = _returnScope.in(rlen); + _returnScope.setDef(rlen,new PhiNode("$expr", r, oldExpr, expr).peephole()); + P._code.add(r); + _returnScope.ctrl(r.unkeep()); + } + P.ctrl(P._code.XCTRL); // Kill control + return expr.unkeep(); + } +} diff --git a/chapter29/src/main/java/com/seaofnodes/simple/parser/Lexer.java b/chapter29/src/main/java/com/seaofnodes/simple/parser/Lexer.java new file mode 100644 index 00000000..f2857c9f --- /dev/null +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/Lexer.java @@ -0,0 +1,384 @@ +package com.seaofnodes.simple.parser; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.CompUnit; +import com.seaofnodes.simple.codegen.Serialize; +import com.seaofnodes.simple.parser.Parser.ParseException; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.BAOS; +import java.util.HashMap; + +// Lexer provides low level access to the raw file bytes, peeks and matches +// short strings, parses numbers, skips comments and whitespace, tracks +// line numbers, allows the parse position to be saved and restored, and +// serves as a location indicator for errors. + +public class Lexer { + + // Input buffer; an array of text bytes read from a file or a string + private final byte[] _input; + // Original source, retained across inlining. + public final CompUnit _cu; + // Tracks current position in input buffer + int _position = 0; + + // + private int _line_number = 1; + // Start of current line + private int _line_start = 0; + + /** True when this location precedes {@code that} in the same source. */ + public boolean before(Lexer that) { + return that != null && (_cu!=null ? _cu==that._cu : _input==that._input) && _position < that._position; + } + + public String position() { return _line_number+":"+(_position-_line_start+1); } + public int pos() { return _position; } + + /** + * Record the source text for lexing + */ + public Lexer(String source) { + this(source.getBytes()); + } + + /** + * Direct from disk file source + */ + public Lexer(byte[] buf) { + _input = buf; + _cu = null; + } + + Lexer(CompUnit cu) { + _input = cu._src.getBytes(); + _cu = cu; + } + + // Imported location: source text is only needed when reporting an error. + Lexer(CompUnit cu, int pos) { + _input = null; + _cu = cu; + _position = pos; + } + + public static void gather(Lexer loc, HashMap strs) { + if( loc==null || loc._cu==null ) return; + Serialize.gather(strs,loc._cu._cname); + String file = loc._cu.sourceFile(); + if( file!=null ) Serialize.gather(strs,file); + } + + public static void packed(Lexer loc, BAOS out, HashMap strs) { + if( loc==null || loc._cu==null ) { out.packed4(0); return; } + out.packed4(loc._position+1); + out.packed4(strs.get(loc._cu._cname)); + String file = loc._cu.sourceFile(); + out.packed4(file==null ? 0 : strs.get(file)); + } + + public static Lexer unpack(BAOS in, String[] strs) { + int pos = in.packed4(); + if( pos==0 ) return null; + String owner = strs[in.packed4()]; + String file = strs[in.packed4()]; + CompUnit cu = CodeGen.CODE._compunits.get(owner.replace('.','/')); + assert cu!=null : owner; + if( !file.isEmpty() ) cu._sourceFile = file; + return new Lexer(cu,pos-1); + } + + /** + * Copy a lexer from a lexer + */ + Lexer(Lexer l) { + _input = l._input; + _cu = l._cu; + _position = l._position; + _line_number = l._line_number; + _line_start = l._line_start; + } + + // Very handy in the debugger, shows the unparsed program + @Override + public String toString() { + return _input==null ? _cu._cname+"@"+_position : new String(_input, _position, _input.length - _position); + } + + // True if at EOF + boolean isEOF() { + return _position >= _input.length; + } + + // Peek next character, or report EOF + char peek() { + return isEOF() ? Character.MAX_VALUE // Special value that causes parsing to terminate + : (char) _input[_position]; + } + // Just crash if misused + public byte peek(int off) { return _input[_position+off]; } + + private void inc() { + if( _position++ < _input.length && _input[_position-1] == '\n' ) { + _line_number++; + _line_start = _position; + } + } + // Does not honor LF, so caller must roll back position on a LF + private char nextChar() { + char ch = peek(); + inc(); + return ch; + } + + // True if a white space + private boolean isWhiteSpace() { + return peek() <= ' '; // Includes all the use space, tab, newline, CR + } + + /** + * Return the next non-white-space character + */ + void skipWhiteSpace() { + while( true ) { + if( isWhiteSpace() ) inc(); + // Skip // to end of line + else if( _position+2 < _input.length && + _input[_position ] == '/' && + _input[_position+1] == '/') { + inc(); inc(); + while( !isEOF() && _input[_position] != '\n' ) + inc(); + } else if( _position+2 < _input.length && + _input[_position ] == '/' && + _input[_position+1] == '*') { + // Skip /*comment*/ + while( !isEOF() && !(_input[_position-1] == '*' && _input[_position] == '/')) + inc(); + inc(); + } else break; + } + } + + // Return true, if we find "syntax" after skipping white space; also + // then advance the cursor past syntax. + // Return false otherwise, and do not advance the cursor. + boolean match(String syntax) { + assert syntax.indexOf('\n')==-1; // No newlines in match + skipWhiteSpace(); + int len = syntax.length(); + if (_position + len > _input.length) return false; + for (int i = 0; i < len; i++) + if ((char) _input[_position + i] != syntax.charAt(i)) + return false; + _position += len; + return true; + } + + // Match must be exact and not followed by more ID characters. + // Prevents identifier "ifxy" from matching an "if" statement. + boolean matchx(String syntax) { + if( !match(syntax) ) return false; + if( !isIdLetter(peek()) ) return true; + _position -= syntax.length(); + return false; + } + // Match this char, and the next char must be different. + // Handles '&&' vs '&' + boolean matchOp( char c0 ) { + skipWhiteSpace(); + if( _position+1 >= _input.length || _input[_position]!=c0 || _input[_position+1]==c0 ) + return false; + inc(); + return true; + } + // Match these two characters in a row + boolean matchOpx(char c0, char c1) { + skipWhiteSpace(); + if( _position+1 >= _input.length || _input[_position]!=c0 || _input[_position+1]==c1 ) + return false; + inc(); + return true; + } + + boolean peek(char ch) { + skipWhiteSpace(); + return peek()==ch; + } + + boolean peekIsId() { + skipWhiteSpace(); + return isIdStart(peek()); + } + + // Return an identifier or null + String matchId() { + return peekIsId() ? parseId() : null; + } + + // Used for errors + String getAnyNextToken() { + if (isEOF()) return "EOF"; + if (isIdStart(peek())) return parseId(); + if (isNumber(peek())) return parseNumberString(); + if (isPunctuation(peek())) return parsePunctuation(); + return String.valueOf(peek()); + } + + boolean isNumber(char ch) {return Character.isDigit(ch);} + + // Return a constant Type, either TypeInteger or TypeFloat + Type parseNumber() { + int old = _position; + int len = isLongOrDouble(); + boolean f32 = peek()=='f'; + if( f32 ) nextChar(); + int n = Math.abs(len); + if( f32 ) + return TypeFloat.constant(Float.parseFloat(new String(_input,old,n))); + if( len > 0 ) { + if( len > 1 && _input[old]=='0' ) + throw Parser.error("Syntax error: integer values cannot start with '0'",this); + long i = Long.parseLong(new String(_input,old,len)); + return TypeInteger.constant(i); + } + return TypeFloat.constant(Double.parseDouble(new String(_input,old,n))); + } + private String parseNumberString() { + int old = _position; + int len = Math.abs(isLongOrDouble()); + if( peek()=='f' ) { + nextChar(); + len++; + } + return new String(_input,old,len); + } + + // Return +len that ends a long + // Return -len that ends a double + private int isLongOrDouble() { + int old = _position; + char c; + while( Character.isDigit(c = nextChar()) ) ; + if( !(c=='e' || c=='.') ) + return --_position - old; + if( peek() == '-' ) nextChar(); + while( Character.isDigit(c = nextChar()) || c=='e' || c=='.' ) ; + return -(--_position - old); + } + + // First letter of an identifier + private boolean isIdStart(char ch) { + return Character.isAlphabetic(ch) || ch == '_'; + } + + // All characters of an identifier, e.g. "_x123" + private boolean isIdLetter(char ch) { + return Character.isLetterOrDigit(ch) || ch == '_'; + } + + private String parseId() { + int start = _position; + while (isIdLetter(nextChar())) ; + return new String(_input, start, --_position - start).intern(); + } + + // + private boolean isPunctuation(char ch) { + return "=;[]<>()+-/*&|^".indexOf(ch) != -1; + } + + private String parsePunctuation() { + int start = _position; + return new String(_input, start, 1); + } + + // Next oper= character, or 0. + // As a convenience, mark "++" as a char 1 and "--" as char -1 (65535) + // Distinct tags for the multi-character compound operators. + static final char SHL = 2, SAR = 3, SHR = 4; + + public char matchOperAssign() { + skipWhiteSpace(); + if( match("<<=" ) ) return SHL; + if( match(">>>=") ) return SHR; + if( match(">>=" ) ) return SAR; + if( _position+2 >= _input.length ) return 0; + char ch0 = (char)_input[_position]; + if( "+-/*&|^".indexOf(ch0) == -1 ) return 0; + char ch1 = (char)_input[_position+1]; + if( ch1 == '=' ) { _position += 2; return ch0; } + if( isIdLetter((char)_input[_position+2]) ) return 0; + if( ch0 == '+' && ch1 == '+' ) { _position += 2; return (char) 1; } + if( ch0 == '-' && ch1 == '-' ) { _position += 2; return (char)-1; } + return 0; + } + + String parseString() { + if( !peek('"') ) return null; + inc(); + StringBuilder sb = new StringBuilder(); + while( !isEOF() ) { + char c = nextChar(); + if( c=='"' ) return sb.toString(); + if( c!='\\' ) { + sb.append(c); + continue; + } + if( isEOF() ) + throw error("Unclosed string"); + sb.append(escapedChar("string")); + } + throw error("Unclosed string"); + } + + private char escapedChar(String kind) { + char esc = nextChar(); + return switch( esc ) { + case '0' -> '\u0000'; + case 'n' -> '\n'; + case 't' -> '\t'; + case 'r' -> '\r'; + case '\\' -> '\\'; + case '"' -> '"'; + case '\'' -> '\''; + default -> throw error("Unknown "+kind+" escape \\\\"+esc); + }; + } + + char parseChar() { + if( isEOF() ) throw error("Unclosed character"); + char c = nextChar(); + if( c=='\\' ) { + if( isEOF() ) throw error("Unclosed character"); + c = escapedChar("character"); + } + return c; + } + + private ParseException error(String msg) { return Parser.error(msg,this); } + + // Scan a deferred fragment, leaving its unmatched closing delimiter unread. + // Comments, quoted text, and escapes do not affect the nesting depth. + void skipTo(char open, char close, String what) { + int depth = 0; + while( true ) { + skipWhiteSpace(); + if( isEOF() ) throw error("Unclosed "+what); + char ch = peek(); + if( ch==close && depth==0 ) return; + nextChar(); + if( ch==open ) depth++; + else if( ch==close ) depth--; + else if( ch=='"' || ch=='\'' ) { + char quote = ch; + while( !isEOF() ) { + ch = nextChar(); + if( ch=='\\' ) nextChar(); + else if( ch==quote ) break; + } + } + } + } + +} diff --git a/chapter29/src/main/java/com/seaofnodes/simple/parser/Parser.java b/chapter29/src/main/java/com/seaofnodes/simple/parser/Parser.java new file mode 100644 index 00000000..913fd2b2 --- /dev/null +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/Parser.java @@ -0,0 +1,298 @@ +package com.seaofnodes.simple.parser; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.CompUnit; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.Ary; +import java.util.HashMap; +import java.util.HashSet; +import java.util.LinkedHashSet; +import java.util.Stack; + +/** Source-unit entry point and shared cursor, scope, and IR utilities. + * Grammar productions live in the package-local components below. */ +public class Parser { + final Statements statements = new Statements(this); + final ControlFlow controlflow = new ControlFlow(this); + final Expressions expressions = new Expressions(this); + final Declarations declarations = new Declarations(this); + final Types types = new Types(this); + final Functions functions = new Functions(this); + final Structs structs = new Structs(this); + final Allocations allocations = new Allocations(this); + final References references = new References(this); + final Conversions conversions = new Conversions(this); + + // Compile driver + public final CodeGen _code; + + // The Lexer. Thin wrapper over a byte[] buffer with a cursor. + Lexer _lexer; + + // Class-object name, distinct from its instance type. + public static final String CLZ = "class:"; + + // Source file for compilation + public CompUnit _ref; + + // Current classname being parsed + String _nestedType; + /** + * Current ScopeNode - ScopeNodes change as we parse code, but at any point of time + * there is one current ScopeNode. The reason the current ScopeNode can change is to do with how + * we handle branching. See {@link Statements#parseIf()}. + *

+ * Each ScopeNode contains a stack of lexical scopes, each scope is a symbol table that binds + * variable names to Nodes. The top of this stack represents current scope. + *

+ * We keep a list of all ScopeNodes so that we can show them in graphs. + * @see Statements#parseIf() + * @see #_xScopes + */ + public ScopeNode _scope; + + /** + * List of keywords disallowed as identifiers + */ + public static final HashSet KEYWORDS = new HashSet<>(){{ + add("bool"); + add("break"); + add("byte"); + add("continue"); + add("else"); + add("f32"); + add("f64"); + add("false"); + add("flt"); + add("i16"); + add("i32"); + add("i64"); + add("i8"); + add("if"); + add("int"); + add("new"); + add("null"); + add("return"); + add("struct"); + add("true"); + add("u1"); + add("u16"); + add("u32"); + add("u8"); + add("while"); + }}; + + /** + * We clone ScopeNodes when control flows branch; it is useful to have + * a list of all active ScopeNodes for purposes of visualization of the SoN graph + */ + public final Stack _xScopes = new Stack<>(); + // Layouts needed by field accesses in this source file. Resolve after + // parsing, since a later local struct declaration can satisfy the use. + public final LinkedHashSet _requiredTypes = new LinkedHashSet<>(); + + // Mapping from a type name to a Type. The string name matches + // `type.str()` call. + public static final HashMap TYPES = new HashMap<>(); + public static final HashMap INIT_TYPES = + new HashMap<>() {{ + put("bool",TypeInteger.U1 ); + put("byte",TypeInteger.U8 ); + put("f32" ,TypeFloat .F32); + put("f64" ,TypeFloat .F64); + put("flt" ,TypeFloat .F64); + put("i16" ,TypeInteger.I16); + put("i32" ,TypeInteger.I32); + put("i64" ,TypeInteger.BOT); + put("i8" ,TypeInteger.I8 ); + put("int" ,TypeInteger.BOT); + put("u1" ,TypeInteger.U1 ); + put("u16" ,TypeInteger.U16); + put("u32" ,TypeInteger.U32); + put("u8" ,TypeInteger.U8 ); + put("val" ,Type.TOP); // Marker type, indicates type inference + put("var" ,Type.BOTTOM); // Marker type, indicates type inference + }}; + + public static class ParseException extends RuntimeException { + public final Lexer _loc; + ParseException( String msg, Lexer loc ) { super(msg); _loc = loc; } + } + + public Parser(CodeGen code ) { + _code = code; + } + + public Ary parse( CompUnit ref ) { + assert _scope == null && statements._breakScope == null && statements._continueScope == null && functions._returnScope == null; + assert references._frefs == null; + _lexer = new Lexer(ref); + references._frefs = new Ary<>(FRefNode.class); + _requiredTypes.clear(); + // Starting Scope has control, memory, initial arguments + _scope = new ScopeNode(); + _scope.define(ScopeNode.CTRL, Type.CONTROL , false, null, _lexer); + _scope.define(ScopeNode.MEM0, TypeMem.BOT , false, null, _lexer); + // Track active scopes for Graph display + _xScopes.push(_scope); + ctrl(_code.XCTRL); + mem(con(TypeMem.BOT)); + + // File-level struct declaration + _ref = ref; + _nestedType = ref._cname; + String typeName = addClzPrefix(ref._cname); + + // Parse whole file, which is a struct-level class initializer + structs.parseInitializer( true, typeName ); + + if( !_lexer.isEOF() ) throw _errorSyntax("unexpected"); + + Ary frefs = references.resolve(); + + // The class being published + ref._clz = (TypeStruct)TYPES.get(typeName); + + // Clean up and reset + _xScopes.pop(); + _scope.kill(); + _scope = null; + references._frefs = null; + + return frefs; + } + + @Override + public String toString() { return _lexer==null ? "" : _lexer.toString(); } + + // Debugging utility to find a Node by index + public Node f(int nid) { return _code.f(nid); } + public static String addClzPrefix( String x ) { + assert !x.startsWith(CLZ); + return (CLZ+x).intern(); + } + public static boolean startsClzPrefix( String s ) { + return s.startsWith(CLZ); + } + public static boolean isPublicClassName( String name ) { + if( startsClzPrefix(name) ) name = name.substring(CLZ.length()); + return !name.isEmpty() && name.charAt(0)!='_' && name.indexOf("._")==-1; + } + + // Read and set CTRL + Node ctrl() { return _scope.ctrl(); } + N ctrl(N n) { return _scope.ctrl(n); } + // Read and set Memory + Node mem() { return _scope.mem(1); } + void mem(Node mem) { _scope.mem(mem); } + // Structural label for precise memory Phis. The '$' prefix cannot be + // referenced in Simple source. + public static String memName(int alias) { return ("$"+alias).intern(); } + + // Ordinary parsing carries one whole-memory value. Alias partitioning is + // graph optimization, not parser state. + void storeMem( Node st, int alias, Node prior ) { + mem(alias==1 ? st : mergeAlias(prior,alias,st)); + } + + // A semantic graph partition representing the complete memory after a + // precise alias update. ScopeNode treats this as one opaque value. + Node mergeAlias(Node bulk, int alias, Node precise) { + assert bulk != null : "Missing bulk memory for alias #"+alias; + MemMergeNode merge = new MemMergeNode(null,bulk); + merge.alias(alias,precise); + return peep(merge); + } + ConstantNode con( long con ) { return _code.con(con); } + ConstantNode con( Type t ) { return _code.con(t ); } + void classInit(Lexer site, Node ptr) { + // Ordinary load machinery resolves the flag alias and offset when + // the receiver is still a forward reference. + Field flag = ptr._type instanceof TypeMemPtr tmp ? tmp._obj.field("$init") : null; + int alias = flag==null ? 1 : flag._alias; + Node ready = new LoadNode(site,"$init",alias,null,mem(),ptr,fldoff(ptr,"$init")).peephole(); + CLInitNode init = new CLInitNode(site,ctrl(),mem(),ptr,ready).peephole().keep(); + ctrl(new CProjNode(init,0,ScopeNode.CTRL).peephole()); + Node bulk = new ProjNode(init,1,ScopeNode.MEM0).peephole().keep(); + flag = init.flag(); + mem(flag==null ? bulk : mergeAlias(bulk,flag._alias, + new ProjNode(init,2,memName(flag._alias)).peephole())); + bulk.unkeep(); + init.unkeep(); + } + + // Field offset for a known type (but unknown offset) + public static ConFldOffNode off( TypeStruct ts, String fname ) { + return (ConFldOffNode)(new ConFldOffNode(ts,fname).peephole()); + } + // Field offset for an unknown type + public Node fldoff( Node n, String name ) { + if( n._type instanceof TypeMemPtr ptr && ptr._obj._fref ) + _requiredTypes.add(ptr._obj._name); + return new FldOffNode(n,name,loc()).peephole(); + } + public Node peep( Node n ) { + // Peephole, then improve with lexically scoped guards + return _scope.upcastGuard(n.peephole()); + } + + // Parse a string or null + + ////////////////////////////////// + // Utilities for lexical analysis + + // Return true and skip if "syntax" is next in the stream. + boolean match (String syntax) { return _lexer.match (syntax); } + // Match must be "exact", not be followed by more id letters + boolean matchx(String syntax) { return _lexer.matchx(syntax); } + boolean matchOp(char c0 ) { return _lexer.matchOp(c0); } + boolean matchOpx(char c0, char c1) { return _lexer.matchOpx(c0,c1); } + // Return true and do NOT skip if 'ch' is next + boolean peek(char ch) { return _lexer.peek(ch); } + + // ch is +/- 1, means oper++ or oper-- means postfix + static boolean postfix(char ch) { + return (byte)ch== 1 || (byte)ch== -1; + } + + public int pos() { return _lexer._position; } + int pos(int pos) { + int old = _lexer._position; + _lexer._position = pos; + return old; + } + Type posT(int pos) { _lexer._position = pos; return null; } + // Source code location + Lexer loc() { return new Lexer(_lexer); } + + // Require and return an identifier + String requireId() { + String id = _lexer.matchId(); + if (id != null && !KEYWORDS.contains(id) ) return id.intern(); + throw error("Expected an identifier, found '"+id+"'"); + } + + String matchId() { + int old = pos(); + String id = _lexer.matchId(); + if( id==null ) return null; + if( !KEYWORDS.contains(id) ) return id; + pos(old); + return null; + } + + // Require an exact match + Parser require(String syntax) { require(null, syntax); return this; } + N require(N n, String syntax) { + if (match(syntax)) return n; + throw errorSyntax(syntax); + } + + ParseException errorSyntax(String syntax) { return _errorSyntax("expected `"+syntax+"`"); } + private ParseException _errorSyntax(String msg) { + return error("Syntax error, "+msg+" but found `" + _lexer.getAnyNextToken()+"`"); + } + ParseException error(String msg) { return error(msg,_lexer); } + public static ParseException error(String msg, Lexer loc) { return new ParseException(msg,loc); } +} diff --git a/chapter29/src/main/java/com/seaofnodes/simple/parser/README.md b/chapter29/src/main/java/com/seaofnodes/simple/parser/README.md new file mode 100644 index 00000000..02a1a2d0 --- /dev/null +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/README.md @@ -0,0 +1,26 @@ +# Parser layout + +The parser builds Sea-of-Nodes IR directly. Each component shares the cursor, +active scope, and compilation state through its `Parser P` reference; there is no intermediate +AST. The [grammar map](../../../../../../../docs/29-grammar.md) connects language +productions to their entry points. + +| File | Responsibility | +| --- | --- | +| `Parser.java` | Source-unit entry point, shared state, type registry, and common token/IR helpers. | +| `Lexer.java` | Tokens, literals, comments, source-location snapshots, and scanning deferred bodies. | +| `Statements.java` | Statement dispatch, blocks, loops, and jumps. | +| `Expressions.java` | Assignment and expression precedence, unary operators, primaries, and postfix dispatch. | +| `Declarations.java` | Bindings, initializers, mutability modifiers, and native declarations. | +| `Types.java` | Type syntax, qualified-name lookup, arrays, function types, and forward types. | +| `Functions.java` | Function expressions, parameters, arguments, calls, and function entry/return graphs. | +| `Structs.java` | Struct and constructor declarations, field discovery, and initialization checks. | +| `References.java` | Bare-name and field resolution, implicit receivers, assignments, and forward references. | +| `Allocations.java` | Allocation expressions, strings, and declaration-side allocation helpers. | +| `ControlFlow.java` | Guarded scope merging shared by `if`, `?:`, `&&`, and `||`. | +| `Conversions.java` | Shared binding, field, and result conversions. | +| `Var.java` | Lexical binding metadata: name, type, scope slot, mutability, and initialization state. | + +Start with `Statements.parseStatement` or `Expressions.parseAssignment` to follow +the grammar. Loop updates are parsed after their bodies, and declared constructor +bodies after field discovery; `Lexer.skipTo` scans these deferred fragments. diff --git a/chapter29/src/main/java/com/seaofnodes/simple/parser/References.java b/chapter29/src/main/java/com/seaofnodes/simple/parser/References.java new file mode 100644 index 00000000..4b474cb8 --- /dev/null +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/References.java @@ -0,0 +1,369 @@ +package com.seaofnodes.simple.parser; + +import com.seaofnodes.simple.codegen.CompUnit; +import com.seaofnodes.simple.codegen.ParseAll; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.node.ScopeNode.Kind; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.Ary; +import java.util.BitSet; + +/** Name and field access, receiver selection, and lvalue checks. */ +final class References { + private final Parser P; + // Forward references created during this unit. + Ary _frefs; + + References(Parser P) { this.P = P; } + + // Resolve a primary name, retaining its use site before speculative type lookup. + Node parseName(String id, int pre, int pos, int pos2) { + // Attempt a local var lookup first + Var var = P._scope.lookup(id); + if( var==null ) { + // Not a local var, try again as a type name + P.pos(pos); + Type t = P.types.parseType(); + if( t!=null ) { + // Static typename lookup + if( P.peek('.') ) // type.fld, which is really a field lookup in the class object + return P.expressions.parsePostfix(P.con(t)); + // Direct reference to a type. Convert the instance + // type to a class type name + if( !(t instanceof TypeMemPtr tmp) ) { + //return new FRefNode(addClzPrefix(tmp._obj._name), loc()).peephole(); + // Not a local var, but yes a bare type... disallow a local + // FREF and return null, not-a-primary parse. + P.pos(pos); + return null; + } + } + + // Insert FREF outside enclosing Kind.Func scope. + P.pos(pos2); + t = FRefNode.FREF_TYPE; + // Check if this is a class. + CompUnit cu = ParseAll.findCompUnit(P._code,P._ref,id); + if( cu!=null ) { + // Must be a final class-type + String clzName = Parser.addClzPrefix(cu._cname); + TypeStruct clz = (TypeStruct)Parser.TYPES.get(clzName); + if( clz == null ) + Parser.TYPES.put(clzName,clz = TypeStruct.make(clzName,true)); + t = TypeMemPtr.make((byte)2,clz,true); + } + // Define the FRef + var = P._scope.defineFRef(id,t,true,P.loc()); + P.references._frefs.push((FRefNode)P._scope.in(var)); + } + + // Load local value + Node rvalue = P._scope.in(var); + if( var._extern!=0 ) + return parseField(rvalue,id,pre); + if( var._fref ) + return P.expressions.parsePostfix(rvalue); + // A constructor may read the unfinished object, but each field it + // reads must already be initialized on every path. Read the current + // local value; other fields may still be waiting for their first write. + if( P.structs.inExplicitConstructor() && var._uninit && missingInit(rvalue,new BitSet()) ) + throw Parser.error("Field '"+id+"' might not be initialized",var._loc); + + // Check for an instance field load + int kx = P._scope.kindx(var); // Declaration scope + int fx = P._scope.enclosingFunction(); // Enclosing function scope + Kind kk = P._scope._kinds.at(kx); + Kind fk = P._scope._kinds.at(fx); + // Access instance field from 'self' + if( kx+1 == fx && kk instanceof Kind.Func inst && FunNode.isInstance(inst._name) && fk instanceof Kind.Func method && !P.structs.inExplicitConstructor() ) + return parseField(P._scope.in(method._lexSize),id,pre); + + // Check for a function-escaping variable; these require true + // closures. Final constants are OK; final vars require a hidden var + // argument; not-final fields can just use an explicit struct arg. + if( kx < fx && !P.structs.inExplicitConstructor() && // Out of scope + !(var._final && rvalue._type.isConstant()) ) { // Not a final constant + if( kx > 0 ) // Global scope is OK, only ever one of these (not one per function invoke) + throw P.error("Variable '"+var._name+"' is out of function scope and must be a final constant"); + + // var.idx==2 is self argument, 3 is args, 4 or more are now static globals + if( var._idx >= 4 ) { + // Read from global scope. + // Surely a nicer way to get the top-level scope compile name? + Var clzptr = P._scope.var( 2 ); + // Get the most recent sharpen global + TypeStruct clz = (TypeStruct) Parser.TYPES.get( ((TypeMemPtr) clzptr.type())._obj._name ); + TypeMemPtr clztmp = TypeMemPtr.make( (byte) 2, clz, true ); + return parseField( P.con( clztmp ), id,pre ); + //return parseField(_scope.in(2),id); + } + } + + // Check for assign-update, x += e0; + char ch = pre==0 ? P._lexer.matchOperAssign() : (char)pre; + if( ch==0 ) { // Normal primary, check for postfix updates + int selfx = P._scope.kindFcn(var)._lexSize; + // Might be a method call from inside a method, so no explicit "self". + // Pass the in-scope "self" + return P.expressions.parsePostfixMethod(rvalue,P._scope.in(P._scope.update(P._scope.var(selfx),null))); + } + // Assign-update direct into Scope + if( var._final && !P._scope.canInit(var) ) + throw P.error("Cannot reassign final '"+var._name+"'"); + checkSharedFunction(var); + Node op = P.expressions.opAssign(ch,rvalue, var.type() ); + P._scope.update(var,op); + if( Parser.postfix(ch) ) rvalue.unkeep(); + return pre==0 && Parser.postfix(ch) ? rvalue : op; + } + + void checkAssignment(Var def) { + String name = def._name; + // A final field may receive its first value in its constructor. + if( P._scope.in(def._idx)._type!=Type.TOP && def._final && + // Inside an allocation, final assign is OK, outside nope. + // The parseNew() call added the allocation scope + !P._scope.canInit(def) ) + throw P.error("Cannot reassign final '"+name+"'"); + checkSharedFunction(def); + + } + + Node assign(Var def, Node expr) { + String name = def._name; + // Lift expression, based on type + Type decl = def.type(); // Declared type + Node lift = P.conversions.convertExpr(expr.keep(), decl).keep(); + // Update + P._scope.update(name,lift); + + // Check for storing into an instance field instead of a local var + int kx = P._scope.kindx(def); // Declaration scope + int fx = P._scope.enclosingFunction(); // Enclosing function scope + Kind kk = P._scope._kinds.at(kx); + Kind fk = P._scope._kinds.at(fx); + // Access instance field from 'self' + if( kx+1 == fx && kk instanceof Kind.Func inst && FunNode.isInstance(inst._name) && + fk instanceof Kind.Func method && !P.structs.inExplicitConstructor() ) { + // Named field offset on an unknown struct type + TypeMemPtr self = (TypeMemPtr)P._scope.var(fk._lexSize).type(); + TypeStruct sobj = (TypeStruct)Parser.TYPES.get(self._obj._name); + Field fld = sobj.field(name); + int alias = fld._alias; + Node ptr = P._scope.in(method._lexSize); + Node off = P.fldoff(ptr,name); + Node prior = P.mem().keep(); + Node st = new StoreNode(P.loc(), name, alias, decl, P.ctrl(), prior, ptr, off, lift, P.structs.inExplicitConstructor()).peephole().keep(); + P.storeMem(st,alias,prior); + st.unkeep(); + prior.unkeep(); + } + lift.unkill(); + + // Return un-lifted expr + return expr.unkeep(); + } + + /** + * Parse postfix expression; this can be a field expression, an array + * lookup or a postfix operator like '#' + * + * 

+     *     expr ['++' | '--' ]                 // Postfix unary write operator
+     *     expr [ [op]= expr ]                 // Field reference
+     *     expr ('[' expr ']')* [ [op]= expr ] // Array reference
+     *
+ */ + + // pre is +/-1 for a prefix update, otherwise parse a postfix operation. + Node parseField(Node expr, String name, int pre) { + return parseField(expr,name,pre,P.loc()); + } + + Node parseField(Node expr, String name, int pre, Lexer site) { + if( P.structs.inExplicitConstructor() && privateSelf(expr) ) return privateField(name,pre); + // Keep expr across possible updates + expr.keep(); + + // Get the best known TypeStruct from a pointer type. + TypeStruct ts = null, ts2; + if( expr._type instanceof TypeMemPtr tmp && (ts2 = ((TypeStruct)Parser.TYPES.get(tmp._obj._name))) != null ) + ts = (TypeStruct)tmp._obj.join(ts2); + // A Load's flow type is intentionally not promised during parsing, + // but its declaring field type is still known. Recover that static + // type for chained accesses such as `_grow(1).buf[len++]`; otherwise + // the array Store is parsed as alias #1 and can hide the independent + // side effect of the postfix `len++`. + if( ts==null && expr instanceof LoadNode load ) { + TypeStruct ots = load.off() instanceof ConFldOffNode coff ? coff._ts : null; + if( ots==null && load.ptr()._type instanceof TypeMemPtr owner ) { + Type owner0 = Parser.TYPES.get(owner._obj._name); + ots = owner0 instanceof TypeStruct obj ? obj : owner._obj; + } + if( ots != null ) { + Field loaded = ots.field(load._name); + if( loaded != null && loaded._t instanceof TypeMemPtr ltmp ) { + Type loaded0 = Parser.TYPES.get(ltmp._obj._name); + ts = loaded0 instanceof TypeStruct obj ? obj : ltmp._obj; + } + } + } + + Field fld = ts==null ? null : ts.field(name); + if( fld==null && ts!=null && !Parser.startsClzPrefix(ts._name) ) { + Type clz0 = Parser.TYPES.get(Parser.addClzPrefix(ts._name)); + if( clz0 instanceof TypeStruct clz && (fld = P.types.latestStruct(clz).field(name)) != null ) { + expr.unkeep(); + ts = P.types.latestStruct(clz); + expr = P.con(TypeMemPtr.make((byte)2,ts,true)).keep(); + } + } + if( fld==null && ts!=null ) + fld = P.types.fieldOrOpen(ts,name,false); + if( fld==null && ts!=null && !P.types.latestStruct(ts)._open ) + throw P.error("Accessing unknown field '"+name+"' from '*"+ts._name+"'"); + + // We have to record "active touches" of a new class, to track when we + // need to force class initialization. Basically, we insert an CLInit, + // and if it does not fold away it'll turn into a runtime check. + Kind.Func func = (Kind.Func)P._scope._kinds.at(P._scope.enclosingFuncOrDecl()); + if( (ts==null || ts==TypeStruct.BOT || ts.isHigh() || Parser.startsClzPrefix(ts._name)) && + !(ts!=null && (ts._name+".").equals(func._name)) ) + P.classInit(site,expr); + + // With no field, we will update the bulk memory + int alias = fld==null ? 1 : fld._alias; + Type decl = fld==null ? Type.BOTTOM : fld._t; + + // Field offset; fixed for structs, computed for arrays + Node off = (name=="[]" + // Array element math, with unknown base offset and shift amount. + ? P.peep(new AddNode(P.fldoff(expr,"[]"),P.peep(new ShlNode(null,P.require(P.expressions.parseAssignment(),"]"),P.fldoff(expr,"<<"))))) + // Named field offset on an unknown struct type + : P.fldoff(expr,name)).keep(); + + // Disambiguate "obj.fld==x" boolean test from "obj.fld=x" field assignment + if( pre==0 && P.matchOpx('=','=') ) { + // Field assignment + Node val = P.expressions.parseAssignment().keep(); + // Lift value for store + Node lift = fld==null ? val : new ConvertNode(fld._t,val).peephole(); + // Memory for store, post assignment expression + Node mem = P.mem(); + // Store to field + mem.keep(); + if( expr._type instanceof TypeMemPtr view && view._ro && P.ctrl()._type!=Type.XCONTROL ) + throw P.error("Cannot modify final field '"+name+"'"); + Node st = new StoreNode(P.loc(), name, alias, decl, P.ctrl(), mem, expr.unkeep(), off.unkeep(), lift, false).peephole().keep(); + P.storeMem(st,alias,mem); + st.unkeep(); + mem.unkeep(); + + return val.unkeep(); // "obj.a = expr" returns the expression while updating memory + } + + // Memory for load + Node mem = P.mem(); + // Loading from a constant array, the declared type is the + // meet-over-elements and not the array itself. + if( name=="[]" && decl instanceof TypeConAry conary ) + decl = conary.elem(); + + // Load field + Node load = P.peep(new LoadNode(P.loc(),name, alias, P.ctrl(), mem, expr, off)); + + // Check for assign-update, "ptr.fld += expr" or "ary[idx]++" + char ch = pre==0 ? P._lexer.matchOperAssign() : (char)pre; + if( ch!=0 ) { + if( fld!=null && decl==Type.BOTTOM ) + throw P.error( "'" + ts._name + "' is not fully initialized, field '" + fld._fname + "' needs to be set in a constructor" ); + Node op = P.expressions.opAssign(ch,load, decl ).keep(); + mem.keep(); + if( expr._type instanceof TypeMemPtr view && view._ro && P.ctrl()._type!=Type.XCONTROL ) + throw P.error("Cannot modify final field '"+name+"'"); + Node st = new StoreNode(P.loc(), name, alias, decl, P.ctrl(), mem, expr.unkeep(), off.unkeep(), op, false).peephole().keep(); + P.storeMem(st,alias,mem); + st.unkeep(); + mem.unkeep(); + + op.unkeep(); // A narrow Store may have folded away the expression's conversion. + if( Parser.postfix(ch) ) load.unkeep(); + return pre==0 && Parser.postfix(ch) ? load : op; + } + off.unkill(); + // Might be a method call, so pass expr as 'self' + return P.expressions.parsePostfixMethod(load,expr.unkeep()); + } + + Node defaultSelf() { + int selfx = P._scope._kinds.at(P._scope.enclosingFuncOrDecl())._lexSize; + return P._scope.in(P._scope.update(P._scope.var(selfx),null)); + } + + private boolean privateSelf(Node ptr) { + while( ptr instanceof ConvertNode || ptr instanceof ReadOnlyNode || ptr instanceof GuardNode ) ptr = ptr.in(1); + Node self = defaultSelf(); + while( self instanceof ConvertNode || self instanceof ReadOnlyNode || self instanceof GuardNode ) self = self.in(1); + return ptr==self; + } + + // An explicit self.x read sees the same current value as bare x. Loading + // the allocation here would miss updates still held in local SSA values. + private Node privateField(String name, int pre) { + int idx = P.structs.fieldVarIdxBefore(P._scope._kinds.at(P._scope.enclosingFuncOrDecl())._lexSize,name); + if( idx<0 ) throw P.error("Cannot resolve field '"+name+"'"); + Var v = P._scope.var(idx); + if( pre==0 && P.matchOpx('=','=') ) { + checkSharedFunction(v); + Node value = P.expressions.parseAssignment().keep(); + P._scope.update(v,P.conversions.convertExpr(value,v.type())); + return value.unkeep(); + } + Node value = P._scope.in(P._scope.update(v,null)); + if( v._uninit && missingInit(value,new BitSet()) ) + throw Parser.error("Field '"+name+"' might not be initialized",v._loc); + char ch = pre==0 ? P._lexer.matchOperAssign() : (char)pre; + if( ch!=0 ) { + checkSharedFunction(v); + Node op = P.expressions.opAssign(ch,value,v.type()); + P._scope.update(v,op); + if( pre!=0 && Parser.postfix(ch) ) value.unkeep(); + return pre==0 && Parser.postfix(ch) ? value.unkeep() : op; + } + return P.expressions.parsePostfixMethod(value,defaultSelf()); + } + + private void checkSharedFunction(Var v) { + if( P._scope.canInit(v) && v._final && v.type() instanceof TypeFunPtr t && t.isConstant() ) + throw P.error("Cannot reassign shared function '"+v._name+"'"); + } + + // A loop Phi is temporarily bottom before its backedge is parsed. That is + // not an unwritten field: follow its live inputs to the actual defaults. + private boolean missingInit(Node value, BitSet seen) { + if( value==null || seen.get(value._nid) ) return false; + seen.set(value._nid); + if( value instanceof PhiNode phi && !(value instanceof ParmNode) ) { + for( int i = 1; i resolve() { + // All still-unresolved forward refs + // should immediately resolve to a file-based name which is a Simple + // class type. + Ary frefs = new Ary<>(FRefNode.class); + for( FRefNode fref : _frefs ) { + if( fref.nIns() != 1 && fref._con == FRefNode.FREF_TYPE ) continue; + CompUnit cu = ParseAll.findCompUnitOrThrow(P._code,P._ref,fref._name); + fref._con = TypeMemPtr.make((byte)2,TypeStruct.make(Parser.addClzPrefix(cu._cname),true),true); + frefs.push(fref); + } + + return frefs; + } +} diff --git a/chapter29/src/main/java/com/seaofnodes/simple/parser/Statements.java b/chapter29/src/main/java/com/seaofnodes/simple/parser/Statements.java new file mode 100644 index 00000000..4ff4993b --- /dev/null +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/Statements.java @@ -0,0 +1,272 @@ +package com.seaofnodes.simple.parser; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.node.ScopeNode.Kind; +import com.seaofnodes.simple.type.*; + +/** Blocks, statements, and loops; builds their control-flow scopes. */ +final class Statements { + private final Parser P; + + // Merge all the while-breaks here + ScopeNode _breakScope; + // Merge all loop continues here. + ScopeNode _continueScope; + + Statements(Parser P) { this.P = P; } + + /** + * Parses a statement + * + * 
+     *     returnStatement | declStatement | blockStatement | ifStatement | expressionStatement
+     *
+ * @return a {@link Node} or {@code null} + */ + Node parseStatement() { + if( P.matchx("return") ) return parseReturn(); + else if (P.matchx("if") ) return parseIf(); + else if (P.matchx("while") ) return parseWhile(); + else if (P.matchx("for") ) return parseFor(); + else if (P.matchx("break") ) return parseBreak(); + else if (P.matchx("continue")) return parseContinue(); + else if (P.matchx("struct") ) return P.structs.parseStruct(); + else if (P.structs.inStructDeclaration() && P.matchx("new")) return P.structs.parseConstructorDeclaration(); + else if (P.matchx(";") ) return P._code.ZERO; // Empty statement + // Break ambiguity around leading function types and starting a block + else if (P.peek('{') && !P.types.isTypeFun() ) { + P.match("{"); + return P.require(parseBlock(new Kind.Block()),"}"); + } + // Declaration or normal assignment/expression + else return P.declarations.parseDeclarationStatement(); + } + + /** + * Parses a block + * + * 
+     *     '{' statements '}'
+     *
+ * Does not parse the opening or closing '{}' + * @return a {@link Node} or {@code null} + */ + private Node parseBlock(Kind kind) { + // Enter a new scope + P._scope.push(kind); + Node last = P._code.ZERO; + while (!P.peek('}') && !P._lexer.isEOF()) { + P._code.add(last); + last = parseStatement(); + } + // Exit scope + last.keep(); + P._scope.pop(); + return last.unkeep(); + } + + /** + * Parses a return statement; "return" already parsed. + * The $ctrl edge is killed. + * + * 
+     *     'return' expr ;
+     *
+ * @return an expression {@link Node}, never {@code null} + */ + private Node parseReturn() { + var expr = P.require(P.expressions.parseAssignment(), ";"); + return P.functions.addReturn(expr); + } + + /** + * Parses a statement + * + * 
+     *     if ( expression ) statement [else statement]
+     *
+ * @return a {@link Node}, never {@code null} + */ + private Node parseIf() { + // Parse predicate + P.require("("); + var pred = P.require(P.expressions.parseAssignment(), ")"); + return P.controlflow.conditional(pred,"else"); + } + + /** + * Parses a while statement + * + * 
+     *     while ( expression ) statement
+     *
+ * @return a {@link Node}, never {@code null} + */ + private Node parseWhile() { + P.require("("); + return parseLooping(false); + } + + /** + * Parses a for statement + * + * 
+     *     for( var x=init; test; incr ) body
+     *
+ * @return a {@link Node}, never {@code null} + */ + private Node parseFor() { + // { var x=init,y=init,...; + // while( test ) { + // body; + // next; + // } + // } + P.require("("); + P._scope.push(new Kind.Block()); // Scope for the index variables + if( !P.match(";") ) // Can be empty init "for(;test;next) body" + P.declarations.parseDeclarationStatement(); // Non-empty init + Node rez = parseLooping(true); + P._scope.pop(); // Exit index variable scope + return rez; + } + + // Shared by `for` and `while` + private Node parseLooping( boolean doFor ) { + + var savedContinueScope = _continueScope; + var savedBreakScope = _breakScope; + + // Loop region has two control inputs, the first is the entry + // point, and second is back edge that is set after loop is parsed + // (see end_loop() call below). Note that the absence of back edge is + // used as an indicator to switch off peepholes of the region and + // associated phis; see {@code inProgress()}. + + P.ctrl(new LoopNode(P.loc(),null,P.ctrl()).peephole()); // Note we set back edge to null here + + // At loop head, we clone the current Scope (this includes all + // names in every nesting level within the Scope). + // We create phis eagerly for all the names we find, see dup(). + + // Save the current scope as the loop head + ScopeNode head = P._scope.keep(); + // Clone the head Scope to create a new Scope for the body. + // Create phis eagerly as part of cloning + P._xScopes.push(P._scope = P._scope.dup(true)); // The true argument triggers creating phis + + // Parse predicate + var pred = P.peek(';') ? P.con(1) : P.expressions.parseAssignment(); + P.require( doFor ? ";" : ")" ); + + // IfNode takes current control and predicate + Node ifNode = new IfNode(P.ctrl(), pred.keep()).peephole(); + // Setup projection nodes + CFGNode ifT = new CProjNode(ifNode. keep(), 0, "True" ).peephole().keep(); + CFGNode ifF = (CFGNode)new CProjNode(ifNode.unkeep(), 1, "False").peephole(); + + // for( ;;next ) body + int nextPos = -1, nextEnd = -1; + if( doFor ) { + // Skip the next expression and parse it later + nextPos = P.pos(); + P._lexer.skipTo('(',')',"for update"); + nextEnd = P.pos(); + P.require(")"); + } + + // Clone the body Scope to create the break/exit Scope which accounts for any + // side effects in the predicate. The break/exit Scope will be the final + // scope after the loop, and its control input is the False branch of + // the loop predicate. Note that body Scope is still our current scope. + P.ctrl(ifF); + P._xScopes.push(_breakScope = P._scope.dup()); + _breakScope.addGuards(ifF,pred,true); // Up-cast predicate + + // No continues yet + _continueScope = null; + + // Parse the true side, which corresponds to loop body + // Our current scope is the body Scope + P.ctrl(ifT.unkeep()); // set ctrl token to ifTrue projection + P._scope.addGuards(ifT,pred.unkeep(),false); // Up-cast predicate + parseStatement().isKill(); // Parse loop body + P._scope.removeGuards(ifT); + + // Merge the loop bottom into other continue statements + if (_continueScope != null) { + _continueScope = jumpTo(_continueScope); + P._scope.kill(); + P._scope = _continueScope; + } + + // Now append the next code onto the body code + if( doFor ) { + int old = P.pos(nextPos); + if( !P.peek(')') ) + P.expressions.parseAssignment(); + if( P.pos() != nextEnd ) + throw P.errorSyntax( "Unexpected code after expression" ); + P.pos(old); + } + + // The true branch loops back, so whatever is current _scope.ctrl gets + // added to head loop as input. endLoop() updates the head scope, and + // goes through all the phis that were created earlier. For each phi, + // it sets the second input to the corresponding input from the back + // edge. If the phi is redundant, it is replaced by its sole input. + var exit = _breakScope; + head.balanceLoopFRefs(P._scope); + exit.balanceLoopFRefs(P._scope); + head.endLoop(P._scope, exit); + head.unkeep().kill(); + + P._xScopes.pop(); // Cleanup + P._xScopes.pop(); // Cleanup + + _continueScope = savedContinueScope; + _breakScope = savedBreakScope; + + // At exit the false control is the current control, and + // the scope is the exit scope after the exit test. + // During sys parsing, there is no xscope here. + if( !P._xScopes.isEmpty() ) { + P._xScopes.pop(); + P._xScopes.push( exit ); + } + P._scope = exit; + return P._code.ZERO; + } + private Node parseBreak () { + checkLoopActive(); + // At the time of the break, and loop-exit conditions are only valid if + // they are ALSO valid at the break. It is the intersection of + // conditions here, not the union. + _breakScope.removeGuards(_breakScope.ctrl()); + _breakScope = P.require(jumpTo(_breakScope ),";"); + _breakScope.addGuards((CFGNode)_breakScope.ctrl(), null, false); + return P._code.ZERO; + } + + private Node parseContinue() { checkLoopActive(); _continueScope = P.require(jumpTo( _continueScope ),";"); return P._code.ZERO; } + + private ScopeNode jumpTo(ScopeNode toScope) { + ScopeNode cur = P._scope.dup(); + P.ctrl(P._code.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.depth() > _breakScope.depth() ) + 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 + // "continue" + if( toScope == null ) + return cur; + // toScope is either the break scope, or a scope that was created here + assert toScope.depth() <= _breakScope.depth(); + toScope.ctrl(toScope.mergeScopes(cur,P.loc()).peephole()); + return toScope; + } + + private void checkLoopActive() { if (_breakScope == null) throw P.error("No active loop for a break or continue"); } +} diff --git a/chapter29/src/main/java/com/seaofnodes/simple/parser/Structs.java b/chapter29/src/main/java/com/seaofnodes/simple/parser/Structs.java new file mode 100644 index 00000000..db17cea3 --- /dev/null +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/Structs.java @@ -0,0 +1,411 @@ +package com.seaofnodes.simple.parser; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.node.ScopeNode.Kind; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.Ary; +import java.util.IdentityHashMap; + +/** Struct and constructor declarations, field discovery, and initialization checks. */ +final class Structs { + private final Parser P; + + // Constructor exit types survive scope teardown until all fields are + // known. A null entry denotes a constructor with no returning path. + Ary> _ctorExits; + + // Constructor declaration: new TypeName = { args -> body }; + record Constructor(String name, Lexer body) {} + Constructor _pendingCtor; + + Structs(Parser P) { this.P = P; } + + /** + * Parse a struct declaration, and return the following statement. + * Structs cannot be redefined, but can be nested. + * + * @return zero + */ + Node parseStruct( ) { + // keyword "struct" already parsed, so expect the struct name next. + String typeName = P.requireId(); + P.require("{"); + + // create type class:NESTED.typeName; no fields. + + String old = P._nestedType; + String fullName = P._scope.depth()==1 && P._nestedType.endsWith(typeName) ? old : (old+"."+typeName).intern(); + P._nestedType = fullName; // Recursive structs start with this as their basename + + ReturnNode ret = parseInitializer( false, fullName ); + + P._nestedType = old; + + // Insert a field into class:NESTED.typeName of "val typeName = fcn-ptr-to-init" + // Function does malloc internally. + // Future self: means subtyping has to deal with "who does the malloc" + String clzName = Parser.addClzPrefix(fullName); + TypeFunPtr sig = ret.fun().sig(); + TypeStruct ts = (TypeStruct)Parser.TYPES.get(clzName); + String initName = initFieldName(fullName); + Field oldFld = ts==null ? null : ts.field(initName); + Field fld = oldFld==null + ? Field.make(initName,sig,P._code.alias(P._ref._cname),true) + : oldFld.makeFrom(sig); + Field ctorFld = ts==null ? null : ts.field(""); + // A same-named struct shares its file's class object and flag. + Field flag = ts==null ? null : ts.field("$init"); + ts = ctorFld==null + ? TypeStruct.make(clzName,false,fld) + : TypeStruct.make(clzName,false,fld,ctorFld); + if( flag!=null ) ts = ts.add(flag); + TypeFunPtr alloc = P.allocations.makeAllocator((TypeStruct)Parser.TYPES.get(fullName),ret,ctorFld); + ts = ts.add(Field.make("",alloc,P._code.alias(P._ref._cname),true)); + Parser.TYPES.put(clzName,ts); + + // Insert a field in the containing class with the nested class type. + // This is basically sugar for "val CLZNAME = " + // and is a nicer version of updateSelfAsFieldsDiscovered. + P._scope.define(typeName, sig, true, new FunPtrNode(sig,P._code._start,ret).peephole(), P.loc()); + + P.require("}"); + return P.require(P._code.ZERO,";"); + } + + boolean inStructDeclaration() { + return P._scope.klast() instanceof Kind.Func fun && FunNode.isInstance(fun._name); + } + + Node parseConstructorDeclaration() { + TypeStruct self = P._scope.constructorSelf(); + assert self != null; + String name = P.requireId(); + String expect = initFieldName(self._name); + if( name != expect ) + throw P.error("Constructor name '" + name + "' must match type name '" + expect + "'"); + P.require("="); + if( _pendingCtor!=null ) throw P.error("Redefining constructor '"+name+"'"); + _pendingCtor = new Constructor(name,P.loc()); + // Parse the body after all field declarations are known, so self.x + // and x share a local slot even when x is declared below this body. + P.require("{"); + P._lexer.skipTo('{','}',"constructor body"); + P.require("}"); + P.require(";"); + return P._code.ZERO; + } + + void finishConstructor() { + if( _pendingCtor==null ) return; + Constructor ctor = _pendingCtor; + _pendingCtor = null; + Lexer after = P._lexer; + P._lexer = new Lexer(ctor.body()); + defineConstructor(ctor.name()); + P._lexer = after; + } + + private void defineConstructor(String name) { + TypeStruct self = P._scope.constructorSelf(); + Node ctor = P.functions.parseConstructor(name); + TypeFunPtr sig = (TypeFunPtr)ctor._type; + String clzName = Parser.addClzPrefix(self._name); + TypeStruct clz = (TypeStruct)Parser.TYPES.get(clzName); + Field old = clz==null ? null : clz.field(""); + if( old != null ) + throw P.error("Redefining constructor '" + name + "'"); + Field fld = Field.make("",sig,P._code.alias(P._ref._cname),true); + Parser.TYPES.put(clzName,clz==null ? TypeStruct.make(clzName,true,fld) : clz.add(fld)); + P.require(ctor,";"); + } + + // Parse a struct declaration (not an allocation); file-level is a + // class-init, and scope structs are normal + ReturnNode parseInitializer( boolean isClz, String typeName ) { + var oldExits = _ctorExits; + _ctorExits = new Ary(IdentityHashMap.class); + // Record & restore global state set during parsing the code + Node oldCtrl= P._scope.ctrl().keep(); + Node oldMem = P._scope.mem ().keep(); + + // Make the future clazz/instance struct. + TypeStruct tself = (TypeStruct)Parser.TYPES.get(typeName); + assert tself==null || tself._open; + // Close an existing open struct, or define a forward ref + tself = tself==null ? TypeStruct.make(typeName,true) : tself.defined(); + + // Class object keeps a runtime flag `$init` to signal the has run. + if( isClz ) + tself = tself.add(Field.make("$init",TypeInteger.BOOL,P._code.alias(P._ref._cname),false)); + Parser.TYPES.put(typeName, tself); + + // Signature of the default constructor + TypeFunPtr sig = structInitSig(isClz,tself); + // Function and argument names of default constructor + String fname = (typeName + (isClz ? "." : ".")).intern(); + String[] ids = new String[]{"self", isClz ? "arg" : "#selfMem"}; + + // Struct decls look like function bodies. Parse function body normally. + ReturnNode ret = P.functions.parseBody(fname,sig,P.loc(),ids); + _ctorExits = oldExits; + // Unwind global state. + P.ctrl(oldCtrl.unkeep()); + P.mem (oldMem .unkeep()); + return ret; + } + + // signature: { self arg/selfMem -> BOT/selfMem } + // Self-memory is the rare *private* (never aliased) memory for the new object. + private TypeFunPtr structInitSig( boolean isClz, TypeStruct tself ) { + // Private uninitialized memory from new object, no escaped values. + TypeMem privMem = isClz ? null : TypeMem.make(1,tself,true,isClz,false,null,null); + Type targ = isClz ? TypeInteger.BOT : privMem; + // Return for private memory has to name all escaped fields, which are not known yet. + // Escape ALL fields, and sharpen later. + Type tret = isClz ? Type.BOTTOM : TypeMem.makePrivate(tself); + Type[] targs = new Type[]{ TypeMemPtr.make((byte)2,tself,isClz), targ }; + // FIDX for FREFs is in the global namespace, needs the correct clz name. + String clzBare = tself._name; + int order = 3; // 3 is always the order, 2nd in the file just behind the + if( isClz ) { + assert Parser.startsClzPrefix( clzBare ); + clzBare = clzBare.substring(Parser.CLZ.length()).intern(); + order = 2; // 2 is always the order, first in file and skipping reserved #1 + } + return TypeFunPtr.make1((byte)2, true, targs, tret, P._code.fidx(clzBare,order)); + } + + int updateSelfAsFieldsDiscovered( String typeName, int nvar ) { + int lex = P._scope.klast()._lexSize + 2/*Skip self and selfMem*/; + // Load self type in and out of the TYPES hashtable. + TypeStruct tself = (TypeStruct)Parser.TYPES.get(typeName); + // Start looking for newly declared vars at the lexical scope start, + // skipping two ("self" and "selfmem") and fields seen already. + while( lex + nvar < P._scope.nIns() ) { + Var v = P._scope.var(lex + nvar++); + // Field with sharper type + Field old = tself.field(v._name); + Field fld = v._extern!=0 + ? Field.make(v._name,v.type(),v._extern,false,true) + : old == null + ? Field.make(v._name,v.type(),P._code.alias(P._ref._cname),v._final) + : old.makeFrom(v.type()); + tself = tself.addOrUpdate(fld); + } + Parser.TYPES.put(typeName,tself); + return nvar; + } + + void upgradeSelfTypeAndStoreFields( String typeName, boolean isClz, ParmNode self, ParmNode smem, boolean upgrade ) { + int lex = P._scope.klast()._lexSize; + assert P._scope.var(lex)._name=="self"; + TypeStruct tself = (TypeStruct)Parser.TYPES.get(typeName); + int base = lex+2; // Skip ctrl, mem + if( upgrade ) { + // Default / defines the struct and can sharpen fields. + // A named constructor only initializes the already-closed struct. + for( int i = 0; i receives the + // broad allocation pointer, while private memory tracks initialized fields. + self._declaredType = self._type = isClz ? TypeMemPtr.make((byte)2,tself,true) : TypeMemPtr.make(constructorRecv(tself)); + FunNode fun = self.fun(); + fun.setSig(fun.sig().makeFrom(self._type,0)); + if( !isClz ) // returns upgraded private memory + smem._declaredType = smem._type = TypeMem.makePrivate(tself); + } + + if( !upgrade ) { + IdentityHashMap exit = null; + if( P.functions._returnScope!=null && !P.functions._returnScope.ctrl()._type.isHigh() ) { + exit = new IdentityHashMap<>(); + int first = P._scope._kinds.at(P._scope.depth()-2)._lexSize+2; + for( int i = first; i updates the private memory that got + // passed in - is treated like a normal argument and not like memory. + Node mmm = isClz ? P.functions._returnScope.mem(1) : smem; + + // Store constructor results into fields + for( int i = 0; i return memory. + P.functions._returnScope.mem(mmm); + //_code.add(mmm); + } + + // Check that all fields are initialized on all constructor exit paths. + private void checkInitFields(TypeStruct ts, int base) { + if( P.functions._returnScope==null || P.functions._returnScope.ctrl()._type.isHigh() ) return; + boolean implicit = _ctorExits.isEmpty(); + if( implicit ) _ctorExits.add(new IdentityHashMap<>()); + for( IdentityHashMap exit : _ctorExits ) { + if( exit==null ) continue; + for( Field fld : ts._fields ) { + int idx = fieldVarIdx(base,fld._fname); + if( idx == -1 ) continue; + Var v = P._scope.var(idx); + if( !v._uninit || v._fref ) continue; + Type t = exit.getOrDefault(v,P.functions._returnScope.in(idx)._type); + if( !initialized(t) ) + throw Parser.error("'"+ts._name+"' is not fully initialized, field '"+fld._fname+ + (implicit ? "' needs to be set in a constructor" : + "' is only partially set in the constructor"),v._loc); + } + } + } + + // Seed the constructor-local SSA slots from the declaration initializer. + void constructorDefaults(String typeName, FunNode fun, Lexer loc) { + int lex = P._scope.klast()._lexSize; + TypeStruct shape = (TypeStruct)Parser.TYPES.get(typeName); + for( Field fld : shape._fields ) { + int idx = fieldVarIdxBefore(lex,fld._fname); + if( idx<0 ) continue; + Var v = P._scope.var(idx); + if( v._fref || v._extern!=0 || v._uninit || P._scope.in(v)._type.isConstant() ) continue; + Node value = P.conversions.convertExpr( + new LoadNode(loc,fld._fname,fld._alias,P.ctrl(),fun.parm(3),fun.parm(2),Parser.off(shape,fld._fname)).peephole(),v.type()); + P._scope.update(v,value); + } + } + + void beginClassInit(FunNode fun, Lexer loc) { + // Each initializer establishes its parent before setting its own + // run-once flag. Keep this in the body so every execution strategy + // shares the same ordering, including direct entry into a child. + if( P._ref._par!=null ) { + String pname = Parser.addClzPrefix(P._ref._par._cname); + TypeStruct parent = (TypeStruct)Parser.TYPES.get(pname); + if( parent==null ) parent = TypeStruct.make(pname,true); + Node ptr = P.con(TypeMemPtr.make((byte)2,parent,true)).keep(); + P.classInit(loc,ptr); + ptr.unkeep(); + } + Node self = fun.parm(2); + Field flag = ((TypeMemPtr)self._type)._obj.field("$init"); + Node prior = P.mem().keep(); + Node st = P.peep(new StoreNode(loc,"$init",flag._alias,flag._t,P.ctrl(),prior,self, + P.fldoff(self,"$init"),P.con(1),false)); + P.storeMem(st,flag._alias,prior); + prior.unkeep(); + } + + // Validate each user constructor, or an implicit empty one, before the + // declaration scope goes away. Later fields use their declaration defaults. + static boolean initialized(Type t) { + // Can't be BOTTOM, that means explicit not initialized. + // Can't be high (initialized to an error) + // Can't be left null and declared not-null. + return t!=Type.BOTTOM && !t.isHigh() && (!(t instanceof TypeNil tn) || tn.notNull()); + } + + private int fieldVarIdx( int base, String name ) { + for( int i = base; i=0; i-- ) + if( P._scope.var(i)._name == name ) + return i; + return -1; + } + + boolean isConstructorDecl(String name) { + TypeStruct self = P._scope.constructorSelf(); + return self != null && name == initFieldName(self._name); + } + + boolean inExplicitConstructor() { + Kind.Func func = (Kind.Func)P._scope._kinds.at(P._scope.enclosingFuncOrDecl()); + return isExplicitConstructorName(func._name); + } + + boolean isExplicitConstructorName(String funName) { + TypeStruct self = P._scope.constructorSelf(); + return self != null && funName == (self._name+"."+initFieldName(self._name)).intern(); + } + + static TypeStruct constructorRecv(TypeStruct self) { + Field[] fs = new Field[self._fields.length]; + for( int i = 0; i type }` or `{ type }`. + private Type parseFunctionType() { + int old = P.pos(); // Record lexer position + P.match("{"); // Skip already-peeked '{' + Type t0 = parseType(); // Either return or first arg + if( t0==null ) return P.posT(old); // Not a function + Ary ts = new Ary<>(Type.class); + // Always reserve a receiver slot. Outside constructor scopes it is + // broad and unused, so call sites can uniformly pass their self. + ts.push(implicitSelfType()); + if( P.match("}") ) // No-arg function { -> type } + return TypeFunPtr.make(P.match("?"),ts.asAry(),t0); + ts.push(t0); // First argument + while( true ) { + if( P.match("->") ) { // End of arguments, parse return + Type ret = parseType(); + if( ret==null || !P.match("}") ) + return P.posT(old); // Not a function + return TypeFunPtr.make(P.match("?"),ts.asAry(),ret); + } + Type t1 = parseType(); + if( t1==null ) return P.posT(old); // Not a function + ts.push(t1); + } + } + + // True if a TypeFunPtr, without advancing parser + boolean isTypeFun() { + int old = P.pos(); + if( parseFunctionType()==null ) return false; + P.pos(old); + return true; + } + + TypeStruct latestStruct( TypeStruct ts ) { + Type t = Parser.TYPES.get(ts._name); + return t instanceof TypeStruct ts2 ? ts2 : ts; + } + + Field fieldOrOpen( TypeStruct ts, String name, boolean xfinal ) { + ts = latestStruct(ts); + Field fld = ts.field(name); + if( fld != null ) return fld; + if( !ts._open || !ts._fref ) return null; + fld = Field.make(name,Type.BOTTOM,P._code.alias(P._ref._cname),xfinal); + Parser.TYPES.put(ts._name,ts = ts.add(fld)); + return fld; + } + + // typeName: walk known local types first, then enclosing namespaces, then + // file modules. A missing suffix of a known type belongs to field parsing. + private String typeName(String name) { + if( Parser.TYPES.containsKey(name) ) return dottedName(name,false); + String root = P._nestedType; + int dot = root.indexOf('.'); + if( dot!=-1 ) root = root.substring(0,dot); + if( name.equals(root) ) return rootedName(name); + + for( String nest = P._nestedType; ; ) { + String full = nest+"."+name; + if( Parser.TYPES.containsKey(full) ) return dottedName(full,false); + int idx = nest.lastIndexOf('.'); + if( idx==-1 ) break; + nest = nest.substring(0,idx); + } + CompUnit cu = ParseAll.findCompUnit(P._code,P._ref,name); + return dottedName(cu==null ? name : cu._cname,true); + } + + private String dottedName(String name, boolean forward) { + while( true ) { + int old = P.pos(); + if( !P.match(".") ) return name; + String part = P.matchId(); + if( part==null || (!forward && !Parser.TYPES.containsKey(name+"."+part)) ) { + P.pos(old); + return name; + } + name += "."+part; + } + } + + // A root-qualified name may introduce an as-yet-undeclared nested type + // inside the current lexical namespace. Once forward, keep its full tail. + private String rootedName(String name) { + boolean forward = false; + while( true ) { + int old = P.pos(); + if( !P.match(".") ) return name; + String part = P.matchId(); + if( part==null ) { P.pos(old); return name; } + String full = name+"."+part; + boolean known = Parser.TYPES.containsKey(full); + if( !known && !forward && + !(P._nestedType.equals(name) || P._nestedType.startsWith(name+".")) ) { + P.pos(old); + return name; + } + name = full; + forward |= !known; + } + } + +} diff --git a/chapter29/src/main/java/com/seaofnodes/simple/parser/Var.java b/chapter29/src/main/java/com/seaofnodes/simple/parser/Var.java new file mode 100644 index 00000000..7d3be3c2 --- /dev/null +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/Var.java @@ -0,0 +1,54 @@ +package com.seaofnodes.simple.parser; + +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.Utils; + + +/** + * The tracked fields are now complex enough to deserve a array-of-structs layout + */ +public class Var { + + public final String _name; // Declared name + // These fields are not final for forward reference late updates or + // promotions. + public int _idx; // index in containing scope + private Type _type; // Declared type + public boolean _final; // Final field + public boolean _fref; // Forward ref + // Parser-only definite-initialization marker. The current binding's + // nullable type carries the path-sensitive state through SSA merges. + public boolean _uninit; + public int _extern; // C storage alias; zero for ordinary variables + public Lexer _loc; // Source location + + public Var(int idx, String name, Type type, boolean xfinal, Lexer loc ) { + this(idx,name,type,xfinal,loc,false); + } + public Var(int idx, String name, Type type, boolean xfinal, Lexer loc, boolean fref) { + _idx = idx; + _name = name; + _type = type; + _final = xfinal; + _fref = fref; + _loc = loc; + } + public Type type() { return _type; } + public Type _type() { return _type; } // ScopeNode printer needs to have no side effects + + // Forward reference variables (not types) must be BOTTOM and + // distinct from inferred variables + public boolean isFRef() { return _fref; } + + public void defFRef( Type type, boolean xfinal, Lexer loc ) { + assert isFRef() && xfinal; + _type = type; + _final = true; + _fref = false; + _loc = loc; + } + + @Override public String toString() { + return (_fref ? "FREF " : "")+(_uninit ? "UNINIT " : "")+_type.toString()+(_final ? " ": " !")+_name; + } +} diff --git a/chapter29/src/main/java/com/seaofnodes/simple/parser/package-info.java b/chapter29/src/main/java/com/seaofnodes/simple/parser/package-info.java new file mode 100644 index 00000000..7212e629 --- /dev/null +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/package-info.java @@ -0,0 +1,14 @@ +/** + * Handwritten recursive-descent parsing directly into Sea-of-Nodes IR. + * + *

{@link com.seaofnodes.simple.parser.Parser} owns the shared cursor and + * scope. Package-local components implement the grammar families: statements, + * expressions, declarations, types, functions, and structs. References handles + * use-side name/field resolution; Allocations, ControlFlow, and Conversions + * contain their shared IR construction. Lexer also supplies location snapshots. + * + *

See {@code chapter29/docs/29-grammar.md} for the production-to-method map. + * Evaluation order and scope lifetimes are explicit: loop updates and declared + * constructor bodies are the two deferred source fragments. There is no AST. + */ +package com.seaofnodes.simple.parser; -- cgit v1.2.3