diff options
| author | Cliff Click <cliffc@acm.org> | 2026-11-15 16:11:39 -0800 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-11-15 16:11:39 -0800 |
| commit | 9fe7c6f9697b5bbf3041261fdc60040e75cc674f (patch) | |
| tree | d92a8ff20ed984938d90ad8917b4d67fba9fb745 /chapter32/src/main/java/com/seaofnodes/simple/parser | |
| parent | f0a6c6757a795b8e186de0076836a87acef59fa7 (diff) | |
| download | Simple-ch32.tar.gz Simple-ch32.zip | |
Split off chapter 31ch32
Ch 32 will be focused on compiler performance issues.
Diffstat (limited to 'chapter32/src/main/java/com/seaofnodes/simple/parser')
19 files changed, 4038 insertions, 0 deletions
diff --git a/chapter32/src/main/java/com/seaofnodes/simple/parser/Allocations.java b/chapter32/src/main/java/com/seaofnodes/simple/parser/Allocations.java new file mode 100644 index 00000000..64234045 --- /dev/null +++ b/chapter32/src/main/java/com/seaofnodes/simple/parser/Allocations.java @@ -0,0 +1,223 @@ +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() { + P._lexer.skipWhiteSpace(); + Lexer site=P.loc(); + Type t = P.types.parseType(); + if( t==null ) { + String tname = P._lexer.matchId(); + if( tname==null || Parser.KEYWORDS.contains(tname) ) + throw Parser.error("Expected a type after 'new'",site); + t = P.types.forwardRefType(tname); + } + // Parse ary[ length_expr ] + if( P.match("[") ) { + boolean readonly = P.match("~"); + if( P.match("]") ) { + P.require("{"); + return P.arrays.parse(t,readonly,null,site); + } + Node len = P.expressions.parseAssignment().keep(); + P.require("]"); + if( P.match("{") ) return P.arrays.parse(t,readonly,len,site); + if( !t.makeZero().isa(t) ) + throw Parser.error("Cannot allocate a non-nullable, since arrays are always zero/null filled",site); + if( readonly ) return new ReadOnlyNode(allocArray(P.types.typeAry(t,true),len)).peephole(); + return allocArray(P.types.typeAry(t,false),len); + } else if( t instanceof TypeMemPtr ary && ary._obj.isAry() && P.match("{") ) { + return P.arrays.parse(ary._obj.field("[]")._t,ary._ro,null,site); + } else { + if( !(t instanceof TypeMemPtr tmp) ) + throw Parser.error("Cannot allocate a "+t.str(),site); + return allocStruct(tmp._obj,site); + } + } + + private Node allocStruct(TypeStruct ts, Lexer site) { + Ary<Node> 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(TypeStruct.addClzPrefix(typeName)); + if( clz==null ) + throw Parser.error("Unknown struct type '" + ts._name + "'",site); + Field afld = clz.field("<new>"); + Node alloc; + if( afld != null ) { + TypeFunPtr tfp = (TypeFunPtr)afld._t; + FunNode fun = P._code.link(tfp); + alloc = fun==null + ? new FRefNode((TypeStruct.addClzPrefix(typeName)+".<new>").intern(),P.loc()).init() + : new FunPtrNode(tfp,P._code._start,fun.ret()).peephole(); + } else { + if( !ts._fref ) + throw Parser.error("Constructor arguments for '" + ts._name + "' but no constructor is defined",site); + Type[] sig = new Type[ctorArgs._len]; + for( int i = 0; i<ctorArgs._len; i++ ) + sig[i] = ctorArgs.at(i)._type; + alloc = new FRefNode((TypeStruct.addClzPrefix(typeName)+".<new>").intern(),P.loc(), + TypeFunPtr.make(false,sig,TypeMemPtr.make(ts))).init(); + } + Ary<Node> args = new Ary<>(Node.class); + args.add(P.ctrl()); args.add(P.mem()); + for( Node arg : ctorArgs ) args.add(arg.unkeep()); + args.add(alloc); + Node result = P.functions.functionCall(args); + if( P.ctrl()._type==Type.XCONTROL ) return result; + return new ConstructNode(result,ctorArgs).peephole(); + } + + private Ary<Node> constructorArgs() { + Ary<Node> 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("[]"); + + Node base = ConFldOffNode.make(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, ConFldOffNode.make(ts,"#"), len.unkeep(), true)); + + 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(byte[] s) { + TypeStruct ts = P.types.typeAry(TypeInteger.U8,true); + int lenAlias = ts.field("#" )._alias; + int elemAlias = ts.field("[]")._alias; + TypeConAry body = TypeConAry.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) { + if( ctorFld==null ) { + Field legacy = ts.field(ts._name.substring(ts._name.lastIndexOf('.')+1).intern()); + if( legacy!=null && legacy._t instanceof TypeFunPtr sig && sig.nargs()>=2 && sig.arg(1) instanceof TypeMem ) + ctorFld = legacy; + } + 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<nargs; i++ ) atypes[i] = ctor.arg(i+2); + TypeMemPtr ptr = TypeMemPtr.make(ts); + TypeFunPtr sig = TypeFunPtr.make1((byte)2,true,atypes,ptr,P._code.fidx(P._ref._cname)); + String name = (ts._name+".<new>").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<nargs; i++ ) + parms[i] = new ParmNode("arg"+i,i+2,atypes[i],fun,ConstantNode.seed(fun.defaultArg(i)).peephole()).peephole(); + + NewNode nnn = new NewNode(ts,fun,ConFldOffNode.make(ts," len")).init(); + Node self = new ProjNode(nnn,0,ts.str()).init(); + Node priv = new ProjNode(nnn,1,"#selfMem").init(); + Node[] initArgs = new Node[]{fun,pub,self,priv, + new FunPtrNode(initRet.fun().sig(),P._code._start,initRet).peephole()}; + CallEndNode cend = rawCall(initArgs,initRet.fun()); + Node ctl = new CProjNode(cend,0,ScopeNode.CTRL).peephole(); + pub = new ProjNode(cend,1,ScopeNode.MEM0).peephole(); + priv = new ProjNode(cend,2,"#selfMem").peephole(); + + if( ctor != null ) { + Node[] cargs = new Node[nargs+5]; + cargs[0] = ctl; cargs[1] = pub; cargs[2] = self; cargs[3] = priv; + for( int i = 0; i<nargs; i++ ) cargs[i+4] = parms[i]; + FunNode cfun = P._code.link(ctor); + cargs[cargs.length-1] = new FunPtrNode(ctor,P._code._start,cfun.ret()).peephole(); + cend = rawCall(cargs,cfun); + ctl = new CProjNode(cend,0,ScopeNode.CTRL).peephole(); + pub = new ProjNode(cend,1,ScopeNode.MEM0).peephole(); + priv = new ProjNode(cend,2,"#selfMem").peephole(); + } + + // Hidden construction helpers have only allocator callers. + if( initRet.fun().unknownCallers() ) initRet.fun().removeDeadPath(1); + if( ctor!=null ) { + FunNode cfun = P._code.link(ctor); + if( cfun.unknownCallers() ) cfun.removeDeadPath(1); + } + + priv.keep(); + for( Field field : ts._fields ) { + Type storage = field._t.makeStorage(); + Field escaped = field._final ? field : field.makeFrom(storage).makeFrom(true); + pub.keep(); + Node esc = new EscapeNode(escaped,self,priv,pub).peephole(); + MemMergeNode merge = new MemMergeNode(null,pub); + merge.alias(field._alias,esc); + Node next = merge.peephole(); + pub.unkeep(); + pub = next; + } + Node finished = new ConstructNode(self,priv,P.loc(),ctor!=null).peephole(); + priv.unkeep(); + ReturnNode ret = (ReturnNode)new ReturnNode(ctl,pub,finished,rpc,fun).peephole(); + fun.setRet(ret); + fun._approxUIDs = P._code.UID() - oldUID; + P._ref.addFun(P._code,fun); + return sig; + } + + private CallEndNode rawCall(Node[] args, FunNode target) { + // Establish this known declaration-side edge immediately, but do not + // peephole or inline it while the surrounding factory is being built. + // IterPeeps therefore starts with the complete initializer caller set. + CallNode call = new CallNode(P.loc(),args).init(); + CallEndNode cend = new CallEndNode(call,TypeRPC.constant(P._code.rpc(P._ref._cname))).init(); + call.link(target); + return cend; + } +} diff --git a/chapter32/src/main/java/com/seaofnodes/simple/parser/ArrayInitializers.java b/chapter32/src/main/java/com/seaofnodes/simple/parser/ArrayInitializers.java new file mode 100644 index 00000000..079853cd --- /dev/null +++ b/chapter32/src/main/java/com/seaofnodes/simple/parser/ArrayInitializers.java @@ -0,0 +1,187 @@ +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; + +/** Array construction keeps the destination private until all elements exist. + * A generator is a scoped, immediately executed loop body, not an escaping closure. */ +final class ArrayInitializers { + private final Parser P; + Frame _frame; + + static final class Frame { + final Kind.Block _kind; + final int _depth; + final Var _value; + ScopeNode _returns; + Frame(Kind.Block kind, int depth, Var value) { + _kind=kind; _depth=depth; _value=value; + } + } + + ArrayInitializers(Parser P) { this.P=P; } + + // Opening brace consumed; an absent length means a list with inferred size. + Node parse(Type elem, boolean readonly, Node len, Lexer site) { + int pos=P.pos(); + Type indexType=P.types.parseType(); + String index=indexType==null ? null : P._lexer.matchId(); + boolean generator=index!=null && P.match("->"); + if( !generator ) P.pos(pos); + if( generator && Parser.KEYWORDS.contains(index) ) + throw Parser.error("Expected an array index name",site); + if( generator && (indexType!=TypeInteger.BOT && indexType!=TypeInteger.I32 && indexType!=TypeInteger.U32) ) + throw Parser.error("Array generator index must be int, i64, or u32",site); + if( generator && len==null ) + throw Parser.error("Array generator requires a length",site); + + Ary<Node> values=new Ary<>(Node.class); + if( !generator ) { + if( !P.peek('}') ) do { + values.add(P.conversions.convertExpr(P.expressions.parseAssignment(),elem).keep()); + } while( P.match(",") && !P.peek('}') ); + P.require("}"); + if( len==null ) len=P.con(values.size()).keep(); + } + + TypeStruct ts=P.types.typeAry(elem,readonly); + Field body=ts.field("[]"), length=ts.field("#"); + Node size=new AddNode(ConFldOffNode.make(ts,"[]"), + new ShlNode(null,len,P.con(ts.aryScale())).peephole()).peephole(); + NewNode alloc=new NewNode(ts,P.ctrl(),size).init(); + Node self=new ProjNode(alloc,0,ts.str()).init().keep(); + Node mem=new ProjNode(alloc,1,"#arrayMem").init().keep(); + Node slen=new StoreNode(site,"#",length._alias,TypeInteger.U32,null,mem,self, + ConFldOffNode.make(ts,"#"),len,true).peephole().keep(); + + if( generator ) { + mem=generator(ts,self,mem,len,index,indexType,site); + } else { + for( int i=0; i<values.size(); i++ ) { + Node st=store(ts,self,mem,P.con(i),values.at(i),site).keep(); + mem.unkeep(); + mem=st; + } + } + + Node result=new ArrayInitNode(P.ctrl(),mem,self,len, + generator ? -1 : values.size(),site,values).peephole().keep(); + Node prior=P.mem(); + P.mem(P.mergeAlias(prior,length._alias,new EscapeNode(length,result,slen.unkeep(),prior).peephole())); + prior=P.mem(); + P.mem(P.mergeAlias(prior,body._alias,new EscapeNode(body,result,mem,prior).peephole())); + mem.unkeep(); self.unkeep(); len.unkeep(); + for( Node value : values ) value.unkeep(); + result.unkeep(); + return readonly ? new ReadOnlyNode(result).peephole() : result; + } + + private Node store(TypeStruct ts, Node self, Node mem, Node idx, Node value, Lexer site) { + Field fld=ts.field("[]"); + Node off=new AddNode(ConFldOffNode.make(ts,"[]"), + new ShlNode(null,idx,P.con(ts.aryScale())).peephole()).peephole(); + return new StoreNode(site,"[]",fld._alias,fld._t,P.ctrl(),mem,self,off,value,true).peephole(); + } + + private Var define(String name, Type type, boolean fin, Node value, Lexer site) { + if( !P._scope.define(name,type,fin,value,site) ) throw Parser.error("Duplicate name '"+name+"'",site); + return P._scope.lookup(name); + } + + private Node read(Var var) { return P._scope.in(P._scope.update(var,null)); } + + private Node generator(TypeStruct ts, Node self, Node mem, Node len, String name, + Type indexType, Lexer site) { + Frame outer=_frame; + ScopeNode oldBreak=P.statements._breakScope, oldContinue=P.statements._continueScope; + P.statements._breakScope=P.statements._continueScope=null; + Kind.Block kind=new Kind.Block(); + P._scope.push(kind); + // The counter stays wide even when the source index is a narrow int. + // The private memory and result slots cannot be named in source. + Var counter=define("$arrayIndex",TypeInteger.BOT,false,P.con(0),site); + Var memory=define("$arrayMem",TypeMem.makePrivate(Type.BOTTOM),false,mem.unkeep(),site); + Var result=define("$arrayValue",ts.field("[]")._t,false,P.con(Type.TOP),site); + _frame=new Frame(kind,P._scope.depth(),result); + + P.ctrl(new LoopNode(site,null,P.ctrl()).peephole()); + ScopeNode head=P._scope.keep(); + P._xScopes.push(P._scope=P._scope.dup(true)); + Node idx=read(counter).keep(); + Node pred=new BoolNode.LT(idx,len).peephole().keep(); + Node iff=new IfNode(P.ctrl(),pred).peephole().keep(); + CFGNode yes=new CProjNode(iff,0,"True").peephole().keep(); + CFGNode no=(CFGNode)new CProjNode(iff.unkeep(),1,"False").peephole(); + P.ctrl(no); + ScopeNode exit=P._scope.dup(); + P._xScopes.push(exit); + exit.addGuards(no,pred,true); + P.ctrl(yes.unkeep()); + P._scope.addGuards(yes,pred.unkeep(),false); + + P._scope.push(new Kind.Block()); + define(name,indexType,true,new ConvertNode(indexType,idx).peephole(),site); + Node last=P._code.ZERO; + while( !P.peek('}') && !P._lexer.isEOF() ) { + P._code.add(last); + last=P.statements.parseStatement(); + } + P.require("}"); + if( P.ctrl()._type!=Type.XCONTROL ) addReturn(last); + P._scope.pop(); + if( _frame._returns!=null ) { + P._scope.kill(); + P._scope=_frame._returns; + } + Node value=read(result); + // The loop starts with the whole private array memory. Keep that shape + // on the backedge too: mixing it with an element slice yields BOTTOM, + // which would falsely publish every function when the array escapes. + Node prior=read(memory).keep(); + Node st=store(ts,self,prior,idx,value,site); + P._scope.update(memory,P.mergeAlias(prior.unkeep(),ts.field("[]")._alias,st)); + P._scope.update(counter,new AddNode(idx.unkeep(),P.con(1)).peephole()); + P._scope.removeGuards(yes); + head.balanceLoopFRefs(P._scope); + exit.balanceLoopFRefs(P._scope); + head.endLoop(P._scope,exit); + head.unkeep().kill(); + P._xScopes.pop(); + P._xScopes.pop(); + if( !P._xScopes.isEmpty() ) { P._xScopes.pop(); P._xScopes.push(exit); } + P._scope=exit; + Node done=read(memory).keep(); + P._scope.pop(); + _frame=outer; + P.statements._breakScope=oldBreak; + P.statements._continueScope=oldContinue; + return done; + } + + Node addReturn(Node expr) { + Node value=P.conversions.convertExpr(expr,_frame._value.type()); + value=new ArrayInitNode(P.ctrl(),value,P.loc()).peephole().keep(); + P.mem(); // Materialize lazy memory before cloning a return path. + ScopeNode cur=P._scope.dup(); + // Saved paths share Var records with the active scope. Drop locals + // without promoting them, then copy forward references explicitly. + while( cur.depth()>_frame._depth ) cur._pop(); + cur.balanceLoopFRefs(P._scope); + cur.update(_frame._value,value.unkeep()); + if( _frame._returns==null ) _frame._returns=cur; + else { + _frame._returns.balanceLoopFRefs(cur); + cur.balanceLoopFRefs(_frame._returns); + _frame._returns.ctrl(_frame._returns.mergeScopes(cur,P.loc()).peephole()); + } + P.ctrl(P._code.XCTRL); + return P._code.ZERO; + } + + void checkAssignment(Var var, Lexer site) { + if( _frame!=null && var._idx<_frame._kind._lexSize ) + throw Parser.error("Cannot assign captured local '"+var._name+"' in an array generator",site); + } +} diff --git a/chapter32/src/main/java/com/seaofnodes/simple/parser/Construction.java b/chapter32/src/main/java/com/seaofnodes/simple/parser/Construction.java new file mode 100644 index 00000000..7797cae4 --- /dev/null +++ b/chapter32/src/main/java/com/seaofnodes/simple/parser/Construction.java @@ -0,0 +1,131 @@ +package com.seaofnodes.simple.parser; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.Ary; + +/** + * Field initialization is ordinary forward typing: New supplies Scalar.BOT + * fields in private memory, Store replaces a field, and Phi meets the incoming + * memories. Scalar.BOT survives a missing live arm; Integer.BOT describes an + * initialized integer. Loads and merged Returns inspect these types after the + * parser closes loops and compute() stabilizes. No backwards initialization walk. + * + * Constructor self and ^ parameters are incomplete. InitViewNode combines self + * with its current private memory: set fields carry their declared types and + * missing fields carry Scalar.BOT. Local ^ parameters meet these shapes through + * ordinary forward flow; unknown callers promise no initialized fields. Only + * the original constructor may write through an incomplete pointer. + * + * Calls borrowing self receive its Stores on the ordinary public memory edge, + * using aliasable Escape slices without publishing its identity. Field values + * come from memory, not the pointer's initialization shape. Incomplete values + * may be retained only in private construction memory. Nested object references + * conservatively promise no initialized fields; arrays are born initialized. + * No field requirements are inferred and no extra memory arguments are added. + * + * Incompleteness lives in TypeMemPtr, not a parser provenance graph. Ordinary + * Phis carry it around loops, conversions preserve it, and ConstructNode types + * each allocation result from its actual arguments. Errors belong to the IR + * nodes and are checked at TypeCheck; the parser keeps no source-use lists. + * + * The qualifier is a two-point lattice: complete meets incomplete to incomplete. + * Constructor self and ^ formals seed incomplete; a ^ formal stays restricted + * even if its known callers are complete. A ConstructNode wraps each source new + * and ORs the actual argument qualifiers. Thus new Child(self) is incomplete, + * while new Child(null) and new Child(oldParent) are complete, even though all + * three calls share the same constructor Return. The raw allocator result is + * complete after its own fields have been checked; ConstructNode adds the + * caller's restriction and disappears after TypeCheck. + * + * Reading a pointer field through a completed receiver gives a completed view + * of that field too: its object's construction could only retain incomplete + * references from the enclosing construction. There is no group ID to clear. + * A read through an incomplete pointer conservatively returns an incomplete reference + * (except initialized arrays), even when the stored value happens to be complete. + * Own-self access is identified by the receiver and its private memory, not by + * the nominal class: a ^ argument of the same class cannot use that exception. + * + * The existing SCCP pass solves qualifier cycles optimistically. For p = null followed + * by p = new Link(p) in a loop, nothing introduces incompleteness, so the loop + * stays complete. A backedge carrying self makes the Phi and its uses incomplete. + * Both cases use the ordinary worklist; no recursive Load/Phi/Call query remains. + * A partial-only ConstructNode supplies the body view of self and ^ formals. + * The Parm itself merges callers normally; inlining cannot erase the view. + * Hidden helpers have only allocator callers, while the public constructor + * binding denotes the allocator. Private-memory Parms therefore need no + * fictitious external default or constructor-specific transfer function. + * InitView and Construct are erased by the existing TypeCheck walk. There is + * no extra construction pass; see chapter29/docs/construction-groups.md + * from the repository root, and chapter29/README.md for the introduction. + */ +final class Construction { + private final Parser P; + boolean _borrowed; // Source ^ parameters; separate compilation is still deferred. + Frame _frame; + + Construction(Parser P) { this.P = P; } + + static final class Frame { + final boolean _owner; + final Node _self; + Frame(boolean owner, Node self) { _owner = owner; _self = self; } + } + + Frame enter(FunNode fun, boolean owner) { + Frame old = _frame; + _frame = new Frame(owner,fun.parm(2)); + return old; + } + + Node memory(Node ptr) { + return own(ptr) ? selfMem() : P.mem(); + } + + Node selfMem() { + Var mem = P._scope.lookup("#selfMem"); + return P._scope.in(P._scope.update(mem,null)); + } + + Node view(Node ptr) { + return own(ptr) ? new InitViewNode((TypeMemPtr)((ParmNode)_frame._self)._declaredType,ptr,selfMem()).peephole() : ptr; + } + + // Carry the constructor's Stores on the call's ordinary memory edge. + // The borrowed receiver is read-only; this does not publish its identity. + Node callMemory(Ary<Node> args, Node pub) { + if( !_frame._owner ) return pub; + boolean lends = false; + for( int i=2; i<args.size()-1; i++ ) lends |= own(args.at(i)); + if( !lends ) return pub; + Node self = _frame._self; + TypeStruct ts = (TypeStruct)Parser.TYPES.get(((TypeMemPtr)self._type)._obj._name); + Node priv = selfMem().keep(); + for( Field fld : ts._fields ) { + pub.keep(); + Node loan = new EscapeNode(fld,self,priv,pub,true).peephole(); + Node next = P.mergeAlias(pub,fld._alias,loan); + pub.unkeep(); + pub = next; + } + priv.unkeep(); + return pub; + } + + boolean own(Node ptr) { + while( ptr instanceof InitViewNode || ptr instanceof ConvertNode || ptr instanceof ReadOnlyNode || ptr instanceof GuardNode || (ptr instanceof ConstructNode con && con._partial) ) ptr = ptr.in(1); + return _frame._owner && ptr==_frame._self; + } + + Node storeMemory(Node ptr) { return own(ptr) ? selfMem() : P.mem(); } + + void store(Node ptr, int alias, Node st, Node prior) { + if( own(ptr) ) P._scope.update("#selfMem",P.mergeAlias(prior,alias,st)); + else P.storeMem(st,alias,prior); + } + + void checkSerializable() { + if( _borrowed ) + throw P.error("Separate compilation of functions with '^' parameters is not supported yet"); + } +} diff --git a/chapter32/src/main/java/com/seaofnodes/simple/parser/ControlFlow.java b/chapter32/src/main/java/com/seaofnodes/simple/parser/ControlFlow.java new file mode 100644 index 00000000..6c626669 --- /dev/null +++ b/chapter32/src/main/java/com/seaofnodes/simple/parser/ControlFlow.java @@ -0,0 +1,98 @@ +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; + +/** Shared guarded branch/merge construction for if, ?:, && and ||. */ +final class ControlFlow { + private final Parser P; + + ControlFlow(Parser P) { this.P = P; } + + // Parse a conditional expression, merging results. + Node conditional( Node pred, String fside ) { + Lexer site=P.loc(); + if( !fside.equals("else") ) site._position-=fside.equals(":") ? 1 : 2; + // IfNode takes current control and predicate + pred.keep(); + Node ifNode = new IfNode(P.ctrl(), pred).peephole(); + // Setup projection nodes + CFGNode ifT = new CProjNode(ifNode. keep(), 0, "True" ).peephole().keep(); + CFGNode ifF = new CProjNode(ifNode.unkeep(), 1, "False").peephole().keep(); + // In if true branch, the ifT proj node becomes the ctrl + // But first clone the scope and set it as current + ScopeNode fScope = P._scope.dup(); // Duplicate current scope + fScope.ctrl(ifF); // The pending arm already starts at False + P._xScopes.push(fScope); // For graph visualization we need all scopes + + // Parse the true side + P.ctrl(ifT.unkeep()); // set ctrl token to ifTrue projection + P._scope.addGuards(ifT,pred,false); // Up-cast predicate + // Parse true-side flavor + Node lhs = switch( fside ) { + case "else" -> 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 Parser.error(err.getMessage(),site); + ret.keep(); + r.peephole(); + return ret.unkeep(); + } +} diff --git a/chapter32/src/main/java/com/seaofnodes/simple/parser/Conversions.java b/chapter32/src/main/java/com/seaofnodes/simple/parser/Conversions.java new file mode 100644 index 00000000..72247ca6 --- /dev/null +++ b/chapter32/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)),ConFldOffNode.make(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/chapter32/src/main/java/com/seaofnodes/simple/parser/Declarations.java b/chapter32/src/main/java/com/seaofnodes/simple/parser/Declarations.java new file mode 100644 index 00000000..473a7c24 --- /dev/null +++ b/chapter32/src/main/java/com/seaofnodes/simple/parser/Declarations.java @@ -0,0 +1,173 @@ +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 ';' + * <p> + * 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(P._scope.klast() instanceof Kind.Func fun && FunNode.isInit(fun._name)); + // 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("=") ) { + P._lexer.skipWhiteSpace(); + Lexer initializer=P.loc(); + if( isExternDecl() ) { + if( !(t instanceof TypeFunPtr) ) { + Node ptr = externData(name,t,loc); + // 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,false); + } else { + expr = P.expressions.parseAssignment(); + } + // var/val, then type comes from expression + if( inferType ) { + if( expr._type==Type.NIL ) + throw Parser.error("Cannot infer a type from null; declare a nullable type explicitly",initializer); + t = expr._type; + // A typed expression may still await a forward callee's flow + // type (e.g. interpolation while sys.text is parsed). Its + // checked conversion already supplies a binding/storage type. + if( t==Type.BOTTOM && expr instanceof ConvertNode convert ) t=convert.dst(); + 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()); + // The explicit signature specifies source parameters/return; + // the receiver of a method body is still inferred. + if( expr instanceof FunPtrNode && P.structs.inStructDeclaration() ) + t = ((TypeFunPtr)t).makeFrom(tfp.arg(0),0); + 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.structs.declareField(P._scope.lookup(name),lift,uninit); + return lift; + } + + // Just after parsing "type foo = " can parse `"C"` + private boolean isExternDecl( ) { + int old = P.pos(); + if( P.match("\"C\"") ) 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, Lexer site) { + if( !(t instanceof TypeInteger) && !(t instanceof TypeFloat) ) + throw Parser.error("C data binding requires an integer or float type",site); + 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 Parser.error("Conflicting types for C data '"+name+"'",site); + return P.con(TypeMemPtr.make((byte)2,ts,true)); + } +} diff --git a/chapter32/src/main/java/com/seaofnodes/simple/parser/Expressions.java b/chapter32/src/main/java/com/seaofnodes/simple/parser/Expressions.java new file mode 100644 index 00000000..ffc96f57 --- /dev/null +++ b/chapter32/src/main/java/com/seaofnodes/simple/parser/Expressions.java @@ -0,0 +1,415 @@ +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() { + P._lexer.skipWhiteSpace(); + Lexer site=P.loc(); + 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 ) { + P.pos(old); + P._lexer.skipWhiteSpace(); + 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,site); + return P.references.assign(def,parseAssignment()); + } + + /** + * Parse an expression of the form: + * + * <pre> + * expression : logicalExpression ('?' assignment (':' assignment)?)? + * </pre> + * @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 + * + * <pre> + * logicalExpression : bitwiseExpression (('&&' | '||') logicalExpression)? + * </pre> + * @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: + * + * <pre> + * expr : shiftExpr < shiftExpr <= shiftExpr... + * expr : shiftExpr > shiftExpr >= shiftExpr... + * </pre> + * @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? + P._lexer.skipWhiteSpace(); + Lexer operator=P.loc(); + 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 Parser.error("Mixing relational directions in a chained relational test",operator); + // 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 + P._lexer.skipWhiteSpace(); + operator=P.loc(); + 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 + * + * <pre> + * shiftExpr : additiveExpr (('<<' | '>>' | '>>>') additiveExpr)* + * </pre> + * @return a shift expression {@link Node}, never {@code null} + */ + private Node parseShift() { + Node lhs = parseAddition(); + while( true ) { + P._lexer.skipWhiteSpace(); + Lexer site=P.loc(); + if( P.match("<<") ) lhs = new ShlNode(site,lhs,null); + else if( P.match(">>>")) lhs = new ShrNode(site,lhs,null); + else if( P.match(">>") ) lhs = new SarNode(site,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 + * + * <pre> + * additiveExpr : multiplicativeExpr (('+' | '-') multiplicativeExpr)* + * </pre> + * @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 + * + * <pre> + * multiplicativeExpr : unaryExpr (('*' | '/' | '%') unaryExpr)* + * </pre> + * @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 if( P.match("%") ) lhs = new ModNode(lhs,null); + else break; + lhs.setDef(2,parseUnary()); + lhs = P.peep(lhs); + } + return lhs; + } + + /** + * Parse a unary minus expression. + * + * <pre> + * unaryExpr : ('-') unaryExpr | '!') unaryExpr | postfixExpr | primaryExpr | '--' Id | '++' Id + * </pre> + * @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 + P._lexer.skipWhiteSpace(); + int start = P.pos(); + Lexer site=P.loc(); + 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 Parser.error("Cannot reassign final '"+var._name+"'",site); + // 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: + * + * <pre> + * primaryExpr : integerLiteral | "string" | 'char' | true | false | null | + * new Type | '(' expression ')' | Id['++','--'] | + * type['.' Id]* + * </pre> + * @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.strings.parse()); + 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) ) { + P.pos(pos); + 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( !Lexer.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 ModNode(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 '#' + * + * <pre> + * expr ('.' FIELD)* [ = expr ] // Field reference + * expr '#' // Postfix unary read operator + * expr ['++' | '--' ] // Postfix unary write operator + * expr ('[' expr ']')* = [ = expr ] // Array reference + * expr '(' [args,]* ')' // Function call + * </pre> + */ + 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(".") ) { + P._lexer.skipWhiteSpace(); + site=P.loc(); + name = P.requireId(true); + } + 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 + * + * <pre> + * integerLiteral: [1-9][0-9]* | 0[0-7]* | 0[xX][0-9a-fA-F]+ + * floatLiteral: [digits].[digits]?[e [digits]]?[f]? + * </pre> + */ + private ConstantNode parseLiteral() { return P.con(P._lexer.parseNumber()); } + + // Already parsed "'" + Node parseChar() { + return P.con(TypeInteger.constant(P._lexer.parseChar())); + } +} diff --git a/chapter32/src/main/java/com/seaofnodes/simple/parser/Functions.java b/chapter32/src/main/java/com/seaofnodes/simple/parser/Functions.java new file mode 100644 index 00000000..84bd509e --- /dev/null +++ b/chapter32/src/main/java/com/seaofnodes/simple/parser/Functions.java @@ -0,0 +1,418 @@ +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; + + // Instance method headers are available immediately; their bodies need + // the complete field scope, just like explicitly declared constructors. + private record Method(FunPtrNode ptr, Lexer body, Lexer loc, BitSet finals, String[] ids) {} + private Ary<Method> _methods; + + Functions(Parser P) { this.P = P; } + + /** + * Parse a function body; the caller will parse the surrounding "{}" + * + * <pre> + * { [type arg,]* -> expr } + * { -> statements } // The no-argument function + * </pre> + */ + Node parseFunction() { + Ary<Type> ts = new Ary<>(Type.class); + Ary<String> ids = new Ary<>(String.class); + BitSet finals = new BitSet(); + Type self = P.types.implicitSelfType(); + if( P.structs.inStructDeclaration() ) self = self.makeRO(); + 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,false); + // 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)); + if( P.structs.inStructDeclaration() ) { + FunPtrNode ptr = (FunPtrNode)new FunPtrNode(tfp,P._code._start,null).peephole().keep(); + _methods.push(new Method(ptr,P.loc(),loc,finals,ids.asAry())); + P._lexer.skipTo('{','}',"method body"); + return ptr; + } + ReturnNode ret = parseFunctionBody(tfp,loc,finals,ids.asAry()); + return new FunPtrNode(tfp,P._code._start,ret).peephole(); + } + + private void finishMethods() { + if( _methods == null ) return; + Ary<Method> methods = _methods; + Lexer after = P._lexer; + for( Method method : methods ) { + P._lexer = new Lexer(method.body()); + TypeFunPtr sig = (TypeFunPtr)method.ptr()._con; + ReturnNode ret = parseFunctionBody(sig,method.loc(),method.finals(),method.ids()); + method.ptr().setDef(1,ret); + P.require("}"); + } + Ary<FunNode> functions = new Ary<>(FunNode.class); + for( Method method : methods ) functions.add(method.ptr().fun()); + MethodAccess.infer(functions); + for( Method method : methods ) { + ReturnNode ret = method.ptr().ret(); + TypeFunPtr sig = ret.fun().sig(); + method.ptr().peephole(); + // Declarations saw the header before its FunNode existed. + for( Var var : P._scope._vars ) + if( var.type() instanceof TypeFunPtr tfp && tfp.isConstant() && tfp.fidx() == sig.fidx() ) { + ret.fun().setName(var._name); + var.refineType(var.type().join(method.ptr()._type)); + TypeStruct self = P._scope.constructorSelf(); + TypeStruct shape = (TypeStruct)Parser.TYPES.get(self._name); + Parser.TYPES.put(shape._name,shape.replace(shape.field(var._name).makeFrom(var.type()))); + break; + } + method.ptr().unkeep(); + } + P._lexer = after; + } + + Node parseConstructor(String name, boolean explicit) { + P.require("{"); + Ary<Type> ts = new Ary<>(Type.class); + Ary<String> ids = new Ary<>(String.class); + BitSet finals = new BitSet(); + TypeStruct self = P._scope.constructorSelf(); + assert self != null; + ts.push(TypeMemPtr.make(Structs.constructorRecv(self)).withPartial(true)); + ids.push("self"); + // Explicit constructors use the same hidden allocation arguments as + // <init>: 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(Type.BOTTOM)); + ids.push("#selfMem"); + + P._lexer.skipWhiteSpace(); + Lexer loc = P.loc(); + parameters(ts,ids,finals,explicit); + TypeFunPtr tfp = TypeFunPtr.make1((byte)2,true,ts.asAry(),TypeMem.makePrivate(Type.BOTTOM),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<Type> ts, Ary<String> ids, BitSet finals, boolean constructor) { + while( true ) { + Type t = P.types.parseType(); // Arg type + if( t==null ) break; + P._lexer.skipWhiteSpace(); + Lexer qualifier=P.loc(); + if( P.match("^") ) { + if( !(t instanceof TypeMemPtr ptr) || ptr._obj.isAry() ) + throw Parser.error("'^' requires a struct parameter",qualifier); + t = ptr.withPartial(true); + P.construction._borrowed = true; + } + finals.set(ids.size(),P.declarations.bindingFinal(t)); + P._lexer.skipWhiteSpace(); + Lexer nameLoc=P.loc(); + String id = P.requireId(); + if( ids.find(id)!=-1 ) throw Parser.error("Duplicate parameter '"+id+"'",nameLoc); + ts .push(t ); // Push type/arg pairs + ids.push(id); + P.match(","); + } + P.require("->"); + } + + /** + * Parse function call arguments; caller will parse the surrounding "()" + * <pre> + * ( arg* ) + * </pre> + */ + Node functionCall(Node fcn, Node self) { + Lexer site = P.loc(); + site._position--; // Opening '('; arguments can contain nested calls. + if( fcn._type == Type.NIL ) + throw Parser.error("Calling a null function pointer",site); + fcn.keep(); // Keep while parsing args + + Ary<Node> 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<Node> args ) { + return functionCall(args,P.loc()); + } + + Node functionCall( Ary<Node> 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 + args.set(1,P.construction.callMemory(args,args.at(1))); + 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<Node> 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 + // - Store class singleton fields; instance Stores already exist + // - <init> and user constructors return their current private memory + // 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) { + ArrayInitializers.Frame outerArray = P.arrays._frame; + P.arrays._frame = null; + Structs.Constructor outerCtor = P.structs._pendingCtor; + P.structs._pendingCtor = null; + boolean isInit = FunNode.isInit(funName); + Ary<Method> outerMethods = _methods; + _methods = FunNode.isInstance(funName) ? new Ary<>(Method.class) : null; + 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(".<clinit>"))); + 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); + // Guards belong to this function's control flow. Do not inherit an + // enclosing function's predicates or leak this body's guards on exit. + P._scope.addGuards(fun,null,false); + Construction.Frame outerConstruction = P.construction.enter(fun,isCtor && !fun.isClz()); + Node rpc = fun.parm(0); + 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 <init> and <clinit>, 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 ) { + finishMethods(); + P.structs.finishConstructor(); + } + _methods = outerMethods; + 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 = P.construction.selfMem(); + } + addReturn(last); + // exit path is now dead (nothing live after a "return") + } + if( isInit ) + P.structs.finishInitializer(typeName,fun.isClz(),self); + + // 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 + P._scope.removeGuards(fun); + if( _returnScope != null ) _returnScope.kill(); + _returnScope = returnScope; + P.statements._continueScope = continueScope; + P.statements._breakScope = breakScope; + P._scope.pop(); + P.construction._frame = outerConstruction; + P.arrays._frame = outerArray; + + 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<ids.length; i++ ) { + Type t = sig.arg(i); + // Parse an implicit receiver with write access, then infer the + // public requirement from its uses once every method is present. + if( i == 0 && ids[0].equals("self") && !FunNode.isInit(funName) && + !(sig.ret() instanceof TypeMem) && t instanceof TypeMemPtr ptr ) + t = ptr.withAccess(false); + // Args take a default input if called from Start/external-world + Type seed = i == 0 && t instanceof TypeMemPtr ? t : fun.defaultArg(i); + Node parm = new ParmNode(ids[i],i+2,t,fun,ConstantNode.seed(seed).peephole()).peephole(); + if( t instanceof TypeMemPtr ptr && ptr._partial ) parm = new ConstructNode(parm).peephole(); + P._scope.define(ids[i], t, (i==0 && ids[0]=="self") || (finals!=null && finals.get(i)), parm, loc); + } + + return fun; + } + Node addReturn(Node expr) { + if( P.construction._frame._owner ) expr = P.construction.selfMem(); + expr.keep(); + // Force the pending lazy bulk-memory Phi. + P.mem(); // Force a pending lazy bulk-memory Phi + // Class fields are still stored at exit. Instance fields already + // travel in expr's private memory; only their scope layout is retained. + 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(); + if( k._name.endsWith(".<clinit>") ) + for( int i = k._lexSize; i<nestedLexSize; i++ ) + P._scope.update(P._scope.var(i),null); + if( _returnScope != null ) { + Var vexpr = _returnScope._vars.pop(); + Node oldX = _returnScope.removeLast(); + int rlen = _returnScope.nIns(); + while( rlen < nestedLexSize ) { + _returnScope._vars.add(P._scope.var(rlen)); + _returnScope.addDef(P.con(P._scope.var(rlen++).type().makeZero())); + } + _returnScope._vars.add(vexpr); + _returnScope.addDef(oldX); + } + } + + // No prior merge point? Just clone and hang on to it + if( _returnScope == null ) { + _returnScope = P._scope.dup(); + while( lexN+1 < _returnScope.depth() ) + _returnScope._pop(); // Pop a nested block scope until we hit the function scope + _returnScope.define("$expr", Conversions.inferredReturnType(expr._type), true, expr, null); + + } else { + // The initializer scopes have already been aligned above. + 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,PhiNode.make("$expr",expr._type, 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/chapter32/src/main/java/com/seaofnodes/simple/parser/Lexer.java b/chapter32/src/main/java/com/seaofnodes/simple/parser/Lexer.java new file mode 100644 index 00000000..8633f2be --- /dev/null +++ b/chapter32/src/main/java/com/seaofnodes/simple/parser/Lexer.java @@ -0,0 +1,495 @@ +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.codegen.SourceError; +import com.seaofnodes.simple.parser.Parser.ParseException; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.BAOS; +import java.util.HashMap; +import java.io.ByteArrayOutputStream; + +// 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; } + + public String diagnostic(String message) { + return _cu==null ? SourceError.format("<input>",_input,_position,message) + : SourceError.format(_cu,_position,message); + } + + /** + * 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<String,Integer> 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<String,Integer> 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+1 < _input.length && + _input[_position ] == '/' && + _input[_position+1] == '/') { + inc(); inc(); + while( !isEOF() && _input[_position] != '\n' ) + inc(); + } else if( _position+1 < _input.length && + _input[_position ] == '/' && + _input[_position+1] == '*') { + Lexer start=new Lexer(this); + inc(); inc(); + while( !isEOF() && !(peek()=='*' && _position+1<_input.length && peek(1)=='/') ) + inc(); + if( isEOF() ) throw Parser.error("Unclosed block comment",start); + 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() { + Lexer start=new Lexer(this); + if( isHex() ) return parseInteger(parseNumberString(),16,2,start); + int old = _position; + int len = isLongOrDouble(); + boolean f32 = peek()=='f'; + if( f32 ) nextChar(); + int n = Math.abs(len); + String literal=new String(_input,old,n); + try { + if( f32 ) + return TypeFloat.constant(Float.parseFloat(literal)); + if( len > 0 ) { + if( len > 1 && _input[old]=='0' ) + return parseInteger(literal,8,0,start); + long i = Long.parseLong(literal); + return TypeInteger.constant(i); + } + return TypeFloat.constant(Double.parseDouble(literal)); + } catch( NumberFormatException ex ) { + throw Parser.error(len>0 && !f32 ? "Integer literal is outside the signed 64-bit range" + : "Invalid floating-point literal '"+literal+(f32 ? "f" : "")+"'",start); + } + } + private String parseNumberString() { + int old = _position; + if( isHex() ) { + _position += 2; + while( isIdLetter(peek()) ) inc(); + return new String(_input,old,_position-old); + } + int len = Math.abs(isLongOrDouble()); + if( peek()=='f' ) { + nextChar(); + len++; + } + return new String(_input,old,len); + } + + private boolean isHex() { + return peek()=='0' && _position+1<_input.length && (peek(1)=='x' || peek(1)=='X'); + } + + private TypeInteger parseInteger(String literal, int radix, int prefix, Lexer start) { + String kind = radix==16 ? "Hexadecimal" : "Octal"; + if( literal.length()==prefix ) + throw Parser.error(kind+" integer literal requires at least one digit",start); + for( int i=prefix; i<literal.length(); i++ ) + if( Character.digit(literal.charAt(i),radix)<0 ) + throw Parser.error("Invalid "+kind.toLowerCase()+" integer literal '"+literal+"'",start); + try { + return TypeInteger.constant(Long.parseUnsignedLong(literal.substring(prefix),radix)); + } catch( NumberFormatException ex ) { + throw Parser.error(kind+" integer literal exceeds 64 bits",start); + } + } + + // 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; + + // ch is +/- 1, means oper++ or oper-- means postfix. + static boolean postfix(char ch) { + return (byte)ch== 1 || (byte)ch== -1; + } + + 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; + } + + record StringPart(byte[] text, boolean end) {} + + // Opening quote has been consumed. Leave a format's '%' unread so both + // the expression parser and deferred-body scanner use the same grammar. + StringPart stringPart(Lexer start) { + ByteArrayOutputStream sb = new ByteArrayOutputStream(); + while( !isEOF() ) { + char c = nextChar(); + if( c=='"' ) return new StringPart(sb.toByteArray(),true); + if( c=='%' ) { + if( peek()=='%' ) { inc(); sb.write('%'); continue; } + _position--; + return new StringPart(sb.toByteArray(),false); + } + if( c!='\\' ) { + sb.write(c); + continue; + } + if( isEOF() ) + throw Parser.error("Unclosed string",start); + sb.write(escapedChar("string")); + } + throw Parser.error("Unclosed string",start); + } + + record Format(int kind, int flags, int width, int precision, Lexer site) {} + + Format stringFormat() { + Lexer site = new Lexer(this); + assert peek()=='%'; + inc(); + if( peek()=='(' ) { inc(); return new Format(0,0,0,-1,site); } + int flags=0, bit; + while( (bit="-+ #0".indexOf(peek()))>=0 ) { + int mask=1<<bit; + if( (flags&mask)!=0 ) throw Parser.error("Repeated format flag",site); + flags |= mask; + inc(); + } + int width = formatNumber(site); + int precision = -1; + if( peek()=='.' ) { + inc(); + precision = formatNumber(site); + } + char kind=nextChar(); + if( "diuoxXfFeEgGaAcsbt".indexOf(kind)<0 ) + throw Parser.error("Expected a string format: %(expression), %d(expression), or %%",site); + boolean number="diuoxXfFeEgGaA".indexOf(kind)>=0; + if( !number && (flags&~1)!=0 || "uoxX".indexOf(kind)>=0 && (flags&6)!=0 || + "diu".indexOf(kind)>=0 && (flags&8)!=0 ) + throw Parser.error("Invalid flags for %"+kind,site); + if( precision>=0 && (kind=='c' || kind=='b' || kind=='t') ) + throw Parser.error("Precision is not supported for %"+kind,site); + if( kind=='t' && peek()!='(' ) { + int style="FrRMDT".indexOf(nextChar()); + if( style<0 ) throw Parser.error("Expected a time format: %t, %tF, %tr, %tR, %tM, %tD, or %tT",site); + flags |= style<<8; + } + if( peek()!='(' ) throw Parser.error("Expected '(' after string format %"+kind,site); + inc(); + return new Format(kind,flags,width,precision,site); + } + + private int formatNumber(Lexer site) { + long n=0; + while( peek()>='0' && peek()<='9' ) { + n=n*10+nextChar()-'0'; + if( n>Integer.MAX_VALUE ) throw Parser.error("String format width or precision is too large",site); + } + return (int)n; + } + + private char escapedChar(String kind) { + Lexer start=new Lexer(this); + start._position--; // The backslash introducing the escape. + char esc = nextChar(); + return switch( esc ) { + case '0' -> '\u0000'; + case 'n' -> '\n'; + case 't' -> '\t'; + case 'r' -> '\r'; + case '\\' -> '\\'; + case '"' -> '"'; + case '\'' -> '\''; + case '%' -> '%'; + default -> throw Parser.error("Unknown "+kind+" escape \\"+esc,start); + }; + } + + char parseChar() { + Lexer start=new Lexer(this); + start._position--; // Opening quote was consumed by the caller. + if( isEOF() || peek()=='\n' || peek()=='\r' ) throw Parser.error("Unclosed character literal",start); + if( peek()=='\'' ) throw Parser.error("Empty character literal",start); + char c = nextChar(); + if( c=='\\' ) { + if( isEOF() ) throw Parser.error("Unclosed character literal",start); + c = escapedChar("character"); + } + if( isEOF() || peek()=='\n' || peek()=='\r' ) throw Parser.error("Unclosed character literal",start); + if( peek()!='\'' ) throw Parser.error("Character literal must contain exactly one byte",start); + inc(); + 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; + Lexer site=ch=='"' ? new Lexer(this) : null; + nextChar(); + if( ch==open ) depth++; + else if( ch==close ) depth--; + else if( ch=='"' ) { + while( !stringPart(site).end() ) { + stringFormat(); + skipTo('(',')',"string interpolation"); + nextChar(); + } + } else if( ch=='\'' ) { + parseChar(); + } + } + } + +} diff --git a/chapter32/src/main/java/com/seaofnodes/simple/parser/MethodAccess.java b/chapter32/src/main/java/com/seaofnodes/simple/parser/MethodAccess.java new file mode 100644 index 00000000..099ba036 --- /dev/null +++ b/chapter32/src/main/java/com/seaofnodes/simple/parser/MethodAccess.java @@ -0,0 +1,130 @@ +package com.seaofnodes.simple.parser; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.Ary; +import java.util.ArrayDeque; +import java.util.HashMap; +import java.util.HashSet; +import java.util.Collections; +import java.util.IdentityHashMap; +import java.util.Set; + +/** Infer the access required through an instance method's receiver. */ +final class MethodAccess { + private final FunNode _fun; + private final Set<Node> _aliases = Collections.newSetFromMap(new IdentityHashMap<>()); + private final Set<MethodAccess> _calls = new HashSet<>(); + private boolean _writes; + + private MethodAccess(FunNode fun) { _fun = fun; } + + static void infer(Ary<FunNode> functions) { + HashMap<Integer,MethodAccess> methods = new HashMap<>(); + for( FunNode fun : functions ) methods.put(fun.sig().fidx(),new MethodAccess(fun)); + for( MethodAccess method : methods.values() ) method.scan(methods); + boolean changed; + do { + changed = false; + for( MethodAccess method : methods.values() ) + if( !method._writes ) + for( MethodAccess callee : method._calls ) + if( callee._writes ) { method._writes = true; changed = true; break; } + } while( changed ); + for( MethodAccess method : methods.values() ) method.finish(); + } + + private void scan(HashMap<Integer,MethodAccess> methods) { + if( _fun.parm(2) == null ) return; // Unused receiver. + ArrayDeque<Node> work = new ArrayDeque<>(); + work.add(_fun.parm(2)); + while( !work.isEmpty() ) { + Node value = work.remove(); + if( !_aliases.add(value) ) continue; + for( Node use : value._outputs ) { + if( use == null || use instanceof ReadOnlyNode ) continue; + if( use instanceof StoreNode store ) { + if( store.ptr() == value || store.val() == value ) _writes = true; + } else if( use instanceof CallNode call ) { + for( int i = 2; i < call.nIns()-1; i++ ) + if( call.in(i) == value ) call(call,i-2,methods); + } else if( use instanceof ReturnNode ret ) { + // Returning a writable alias must not grant write access + // to an object reached through a read-only receiver. + if( ret.expr() == value ) _writes = true; + } else if( use instanceof LoadNode load && load.ptr() == value ) { + Type type = type(load); + if( type instanceof TypeMemPtr ptr ) { + if( !ptr._ro ) work.add(load); + } else if( type == Type.BOTTOM || type == TypeScalar.BOT ) _writes = true; + } else if( use instanceof PhiNode || use instanceof GuardNode ) { + work.add(use); + } else if( use instanceof ConvertNode convert ) { + if( !(convert.dst() instanceof TypeMemPtr ptr && ptr._ro) ) _writes = true; + } else if( use instanceof BoolNode || use instanceof NotNode || + use instanceof FldOffNode || use instanceof ScopeNode || use instanceof CLInitNode ) { + // Comparisons and field offsets do not expose write access. + } else { + // Includes raw-address casts and unrecognized escapes. + _writes = true; + } + } + } + } + + private void call(CallNode call, int arg, HashMap<Integer,MethodAccess> methods) { + // Every member of this struct is now declared. An unresolved bare + // function name belongs to an outer scope, whose hidden slot is not self. + if( arg == 0 && call.fptr() instanceof FRefNode ) return; + Type type = type(call.fptr()); + if( !(type instanceof TypeFunPtr sig) || arg >= sig.nargs() ) { _writes = true; return; } + if( arg == 0 && sig.arg(0) == TypePtr.PTR ) return; + if( arg == 0 ) { + if( XInt.isHigh(sig.fidxs()) ) { _writes = true; return; } + for( int fidx = XInt.next(sig.fidxs(),-1); fidx >= 0; fidx = XInt.next(sig.fidxs(),fidx) ) { + MethodAccess local = methods.get(fidx); + if( local != null ) _calls.add(local); + else { + FunNode target = CodeGen.CODE.link(fidx); + Type receiver = target == null ? sig.arg(0) : target.sig().arg(0); + if( !(receiver instanceof TypeMemPtr ptr && ptr._ro) ) _writes = true; + } + } + return; + } + if( !(sig.arg(arg) instanceof TypeMemPtr ptr && ptr._ro) ) _writes = true; + } + + private static Type type(Node value) { + // Flow types can still be BOTTOM while the parser discovers fields. + if( value instanceof LoadNode load ) { + TypeStruct obj = load.off() instanceof ConFldOffNode off ? off._ts : + type(load.ptr()) instanceof TypeMemPtr ptr ? ptr._obj : null; + if( obj != null ) { + if( !obj.isAry() && Parser.TYPES.get(obj._name) instanceof TypeStruct latest ) obj = latest; + Field field = obj.field(load._name); + if( field != null ) return field._t; + } + } + return value._type; + } + + private void finish() { + ParmNode self = _fun.parm(2); + if( self == null ) return; + TypeMemPtr receiver = ((TypeMemPtr)self._declaredType).withAccess(!_writes); + _fun.setSig(_fun.sig().makeFrom(receiver,0)); + if( _writes ) return; + self._declaredType = receiver; + self.setDef(1,ConstantNode.seed(receiver).peephole()); + // These parser-time assumptions are settled before Iter/SCCP. No + // writable alias escapes a method classified as read-only. + for( Node alias : _aliases ) + if( alias._type instanceof TypeMemPtr ptr ) { + alias._type = ptr.makeRO(); + CodeGen.CODE.add(alias); + CodeGen.CODE.addAll(alias._outputs); + } + } +} diff --git a/chapter32/src/main/java/com/seaofnodes/simple/parser/Parser.java b/chapter32/src/main/java/com/seaofnodes/simple/parser/Parser.java new file mode 100644 index 00000000..9c18385d --- /dev/null +++ b/chapter32/src/main/java/com/seaofnodes/simple/parser/Parser.java @@ -0,0 +1,300 @@ +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.LinkedHashMap; +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 ArrayInitializers arrays = new ArrayInitializers(this); + final References references = new References(this); + final Conversions conversions = new Conversions(this); + final Construction construction = new Construction(this); + final Strings strings = new Strings(this); + + public void checkConstructionSerializable() { construction.checkSerializable(); } + + // Compile driver + public final CodeGen _code; + + // The Lexer. Thin wrapper over a byte[] buffer with a cursor. + Lexer _lexer; + + // 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()}. + * <p> + * 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. + * <p> + * 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<String> 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<ScopeNode> _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 LinkedHashMap<String,Lexer> _requiredTypes = new LinkedHashMap<>(); + + // Mapping from a type name to a Type. The string name matches + // `type.str()` call. + public static final HashMap<String, Type> TYPES = new HashMap<>(); + public static final HashMap<String, Type> 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.I32); + 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==null ? null : new Lexer(loc); } + public String diagnostic() { return _loc==null ? getMessage() : _loc.diagnostic(getMessage()); } + // JUnit and uncaught-exception reporters use these entry points rather + // than the CLI's diagnostic(). Source errors should retain their source + // excerpt and caret there too. getMessage() stays stable for callers. + @Override public void printStackTrace(java.io.PrintStream out) { out.println(diagnostic()); } + @Override public void printStackTrace(java.io.PrintWriter out) { out.println(diagnostic()); } + } + + public Parser(CodeGen code ) { + _code = code; + } + + public Ary<FRefNode> 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 = TypeStruct.addClzPrefix(ref._cname); + + // Parse whole file, which is a struct-level class initializer + structs.parseInitializer( true, typeName ); + + if( !_lexer.isEOF() ) throw _errorSyntax("unexpected"); + + Ary<FRefNode> 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; + } + + // Cursor and token helpers + + // 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); } + // Skip whitespace, but leave the next token unread. + boolean peek(char ch) { return _lexer.peek(ch); } + + 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() { + return requireId(false); + } + + // Primitive names are useful member names (sys.text.int), but remain + // reserved for local variables, parameters and type declarations. + String requireId(boolean member) { + _lexer.skipWhiteSpace(); + Lexer site=loc(); + String id = _lexer.matchId(); + if (id != null && (!KEYWORDS.contains(id) || member && + (INIT_TYPES.get(id) instanceof TypeInteger || INIT_TYPES.get(id) instanceof TypeFloat)) ) return id.intern(); + throw error("Expected an identifier, found '"+new Lexer(site).getAnyNextToken()+"'",site); + } + + 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> N require(N n, String syntax) { + if (match(syntax)) return n; + throw errorSyntax(syntax); + } + + // Scope, control, and memory + + // Read and set CTRL + Node ctrl() { return _scope.ctrl(); } + <N extends Node> 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); } + + // 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)); + } + + 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,ScopeNode.memName(flag._alias)).peephole())); + bulk.unkeep(); + init.unkeep(); + } + + // IR construction using the current parser context + + ConstantNode con( long con ) { return _code.con(con); } + ConstantNode con( Type t ) { return _code.con(t ); } + + // 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); + } + // Field offset for an unknown type + public Node fldoff( Node n, String name ) { + if( n._type instanceof TypeMemPtr ptr && ptr._obj._fref ) + _requiredTypes.putIfAbsent(ptr._obj._name,loc()); + return new FldOffNode(n,name,loc()).peephole(); + } + public Node peep( Node n ) { + // Peephole, then improve with lexically scoped guards + return _scope.upcastGuard(n.peephole()); + } + + // Diagnostics + + ParseException errorSyntax(String syntax) { return _errorSyntax("expected `"+syntax+"`"); } + private ParseException _errorSyntax(String msg) { + _lexer.skipWhiteSpace(); + // Reading the token for the message must not advance the error location. + return error("Syntax error, "+msg+" but found `" + loc().getAnyNextToken()+"`"); + } + ParseException error(String msg) { return error(msg,_lexer); } + public static ParseException error(String msg, Lexer loc) { return new ParseException(msg,loc); } + + // Debugging + + @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); } +} diff --git a/chapter32/src/main/java/com/seaofnodes/simple/parser/README.md b/chapter32/src/main/java/com/seaofnodes/simple/parser/README.md new file mode 100644 index 00000000..0ed3f298 --- /dev/null +++ b/chapter32/src/main/java/com/seaofnodes/simple/parser/README.md @@ -0,0 +1,45 @@ +# 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/32-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. | +| `MethodAccess.java` | Infers whether an instance method needs writable access through its receiver. | +| `Structs.java` | Struct and constructor declarations, field discovery, and initialization Stores. | +| `Construction.java` | Selects private self memory during parsing; its comment explains BOT fields, the TypeMemPtr qualifier, and checks deferred to TypeCheck. | +| `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, and mutability. | + +Start with `Statements.parseStatement` or `Expressions.parseAssignment` to follow +the grammar. Loop updates are parsed after their bodies. Instance method headers +are parsed immediately, but their bodies and declared constructor bodies wait +until all fields are known. Methods can therefore use fields declared later in +the struct. `Lexer.skipTo` scans these deferred fragments. + +Method receivers accept read-only access unless the body needs writable access. +The check follows aliases, child references, array elements, and calls between +methods. Writing an independent argument does not require a writable receiver. +Returning or storing a writable receiver alias also requires writable access; +an explicit read-only view can be exposed without that requirement. + +`Parser` keeps the short cursor, scope/memory, IR-building, and diagnostic helpers +used by these components. Independent helpers live with their data: class-object +names in `TypeStruct`, postfix operator encoding in `Lexer`, known field-offset +creation in `ConFldOffNode.make`, and memory-alias labels in `ScopeNode.memName`. + +Instance constructor fields live in ordinary memory, with one hidden `#selfMem` +binding per activation. Forward field types use `TypeScalar.BOT` for missing +initialization; there are no per-field snapshots or store-all constructor exits. diff --git a/chapter32/src/main/java/com/seaofnodes/simple/parser/References.java b/chapter32/src/main/java/com/seaofnodes/simple/parser/References.java new file mode 100644 index 00000000..7724103e --- /dev/null +++ b/chapter32/src/main/java/com/seaofnodes/simple/parser/References.java @@ -0,0 +1,346 @@ +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; + +/** Name and field access, receiver selection, and lvalue checks. */ +final class References { + private final Parser P; + // Forward references created during this unit. + Ary<FRefNode> _frefs; + + References(Parser P) { this.P = P; } + + // Compiler-generated library references use ordinary module lookup and + // forward resolution, without a synthetic token stream. + Node classReference(String name, Lexer site) { + CompUnit cu=ParseAll.findCompUnit(P._code,P._ref,name); + if( cu==null ) throw Parser.error("Cannot find standard library '"+name+"'",site); + String clzName=TypeStruct.addClzPrefix(cu._cname); + TypeStruct clz=(TypeStruct)Parser.TYPES.computeIfAbsent(clzName,n -> TypeStruct.make(n,true)); + FRefNode ref=new FRefNode(name,site,TypeMemPtr.make((byte)2,clz,true)); + _frefs.push(ref); + return ref.peephole(); + } + + // Read a member without consuming a postfix from source text. + Node member(Node receiver, String name, Lexer site) { + Field fld=receiver._type instanceof TypeMemPtr ptr ? ptr._obj.field(name) : null; + return P.peep(new LoadNode(site,name,fld==null ? 1 : fld._alias, + P.ctrl(),P.mem(),receiver,P.fldoff(receiver,name))); + } + + // Resolve a primary name, retaining its use site before speculative type lookup. + Node parseName(String id, int pre, int pos, int pos2) { + Lexer site=P.loc(); + site._position=pos; + site.skipWhiteSpace(); + // 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); + Lexer nameLoc = P.loc(); + Type t = P.types.parseType(); + if( t!=null ) { + // Static <clinit> 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 <clinit> 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 = TypeStruct.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,nameLoc); + 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); + Node fieldSelf = fieldSelf(var); + if( fieldSelf!=null ) return parseField(fieldSelf,id,pre); + int kx = P._scope.kindx(var); + int fx = P._scope.enclosingFunction(); + + // 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 Parser.error("Variable '"+var._name+"' is out of function scope and must be a final constant",site); + + // 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(P.construction.view(rvalue),P._scope.in(P._scope.update(P._scope.var(selfx),null))); + } + // Assign-update direct into Scope + P.arrays.checkAssignment(var,site); + if( var._final && !P._scope.canInit(var) ) + throw Parser.error("Cannot reassign final '"+var._name+"'",site); + checkSharedFunction(var); + Node op = P.expressions.opAssign(ch,rvalue, var.type() ); + P._scope.update(var,op); + if( Lexer.postfix(ch) ) rvalue.unkeep(); + return pre==0 && Lexer.postfix(ch) ? rvalue : op; + } + + void checkAssignment(Var def, Lexer site) { + if( fieldSelf(def)==null ) P.arrays.checkAssignment(def,site); + 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 Parser.error("Cannot reassign final '"+name+"'",site); + checkSharedFunction(def); + + } + + Node assign(Var def, Node expr) { + Node self = fieldSelf(def); + if( self!=null ) { + TypeStruct ts = P.types.latestStruct(((TypeMemPtr)self._type)._obj); + Field fld = ts.field(def._name); + Node val = expr.keep(); + Node lift = P.conversions.convertExpr(val,def.type()); + Node mem = P.construction.storeMemory(self).keep(); + Node st = new StoreNode(P.loc(),fld._fname,fld._alias,fld._t,P.ctrl(),mem,self, + ConFldOffNode.make(ts,fld._fname),lift,P.construction.own(self)).peephole(); + P.construction.store(self,fld._alias,st,mem); + mem.unkeep(); + return val.unkeep(); + } + 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); + + 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 '#' + * + * <pre> + * expr ['++' | '--' ] // Postfix unary write operator + * expr [ [op]= expr ] // Field reference + * expr ('[' expr ']')* [ [op]= expr ] // Array reference + * </pre> + */ + + // 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) { + // 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 && !TypeStruct.startsClzPrefix(ts._name) ) { + Type clz0 = Parser.TYPES.get(TypeStruct.addClzPrefix(ts._name)); + if( clz0 instanceof TypeStruct clz && (fld = P.types.latestStruct(clz).field(name)) != null ) { + expr.unkill(); + 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 Parser.error("Accessing unknown field '"+name+"' from '*"+ts._name+"'",site); + + // 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() || TypeStruct.startsClzPrefix(ts._name)) && + !(ts!=null && (ts._name+".<clinit>").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.construction.storeMemory(expr); + // Store to field + mem.keep(); + if( !P.construction.own(expr) && expr._type instanceof TypeMemPtr view && view._ro && P.ctrl()._type!=Type.XCONTROL ) + throw Parser.error("Cannot modify final field '"+name+"'",site); + Node st = new StoreNode(P.loc(), name, alias, decl, P.ctrl(), mem, expr.unkeep(), off.unkeep(), lift, P.construction.own(expr)).peephole().keep(); + P.construction.store(expr,alias,st,mem); + st.unkeep(); + mem.unkeep(); + + return val.unkeep(); // "obj.a = expr" returns the expression while updating memory + } + + // Memory for load + Node mem = P.construction.memory(expr); + // 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(site,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 && !ts._fref ) + throw Parser.error( "'" + ts._name + "' is not fully initialized, field '" + fld._fname + "' needs to be set in a constructor",site ); + Node op = P.expressions.opAssign(ch,load, decl ).keep(); + mem.keep(); + if( !P.construction.own(expr) && expr._type instanceof TypeMemPtr view && view._ro && P.ctrl()._type!=Type.XCONTROL ) + throw Parser.error("Cannot modify final field '"+name+"'",site); + Node st = new StoreNode(P.loc(), name, alias, decl, P.ctrl(), mem, expr.unkeep(), off.unkeep(), op, P.construction.own(expr)).peephole().keep(); + P.construction.store(expr,alias,st,mem); + st.unkeep(); + mem.unkeep(); + + op.unkeep(); // A narrow Store may have folded away the expression's conversion. + if( Lexer.postfix(ch) ) load.unkeep(); + return pre==0 && Lexer.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)); + } + + // Fields are lvalues in memory, including inside their initializer and + // explicit constructor. Scope slots retain declaration metadata only. + private Node fieldSelf(Var var) { + int kx = P._scope.kindx(var); + ScopeNode.Kind kind = P._scope._kinds.at(kx); + if( !(kind instanceof Kind.Func inst) || !FunNode.isInstance(inst._name) || var._idx<inst._lexSize+2 ) return null; + // Nested functions have their own receiver parameter. Resolve fields + // through it even across intervening function and block scopes. + Node self = defaultSelf(); + Type owner = P._scope.var(inst._lexSize).type(); + if( self._type instanceof TypeMemPtr ptr && owner instanceof TypeMemPtr declared && + ptr._obj._name.equals(declared._obj._name) ) return self; + return null; + } + + 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+"'"); + } + + Ary<FRefNode> resolve() { + // All still-unresolved forward refs + // should immediately resolve to a file-based name which is a Simple + // class type. + Ary<FRefNode> frefs = new Ary<>(FRefNode.class); + for( FRefNode fref : _frefs ) { + if( fref.nIns() != 1 && fref._con == FRefNode.FREF_TYPE ) continue; + CompUnit cu = ParseAll.findCompUnit(P._code,P._ref,fref._name); + if( cu==null ) throw fref.err(); + // Name lookup may already know this class's fields. Do not replace + // that information with an empty placeholder before Iter runs. + if( fref._con==FRefNode.FREF_TYPE ) + fref.liftType(TypeMemPtr.make((byte)2,TypeStruct.make(TypeStruct.addClzPrefix(cu._cname),true),true)); + frefs.push(fref); + } + + return frefs; + } +} diff --git a/chapter32/src/main/java/com/seaofnodes/simple/parser/Statements.java b/chapter32/src/main/java/com/seaofnodes/simple/parser/Statements.java new file mode 100644 index 00000000..0c2a25f7 --- /dev/null +++ b/chapter32/src/main/java/com/seaofnodes/simple/parser/Statements.java @@ -0,0 +1,284 @@ +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 + * + * <pre> + * returnStatement | declStatement | blockStatement | ifStatement | expressionStatement + * </pre> + * @return a {@link Node} or {@code null} + */ + Node parseStatement() { + P._lexer.skipWhiteSpace(); + Lexer site=P.loc(); + 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(site); + else if (P.matchx("continue")) return parseContinue(site); + 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 + * + * <pre> + * '{' statements '}' + * </pre> + * 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. + * + * <pre> + * 'return' expr ; + * </pre> + * @return an expression {@link Node}, never {@code null} + */ + private Node parseReturn() { + var expr = P.require(P.expressions.parseAssignment(), ";"); + if( P.arrays._frame!=null ) return P.arrays.addReturn(expr); + return P.functions.addReturn(expr); + } + + /** + * Parses a statement + * + * <pre> + * if ( expression ) statement [else statement] + * </pre> + * @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 + * + * <pre> + * while ( expression ) statement + * </pre> + * @return a {@link Node}, never {@code null} + */ + private Node parseWhile() { + P.require("("); + return parseLooping(false); + } + + /** + * Parses a for statement + * + * <pre> + * for( var x=init; test; incr ) body + * </pre> + * @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().isKill(); + 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(Lexer site) { + checkLoopActive(site); + // 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(Lexer site) { checkLoopActive(site); _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 + // The clone shares lexical boundaries and Var records with the active + // parser scope. Promoting on the clone would move those boundaries + // without moving the active scope's bindings. Drop locals first, then + // copy forward references into the jump scope with their own indices. + while( cur.depth() > _breakScope.depth() ) + cur._pop(); + cur.balanceLoopFRefs(P._scope); + // 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(); + // A later path can discover forward references after an earlier + // break/continue saved its scope. Keep those bindings across the merge. + toScope.balanceLoopFRefs(cur); + cur.balanceLoopFRefs(toScope); + toScope.ctrl(toScope.mergeScopes(cur,P.loc()).peephole()); + return toScope; + } + + private void checkLoopActive(Lexer site) { if (_breakScope == null) throw Parser.error("No active loop for a break or continue",site); } +} diff --git a/chapter32/src/main/java/com/seaofnodes/simple/parser/Strings.java b/chapter32/src/main/java/com/seaofnodes/simple/parser/Strings.java new file mode 100644 index 00000000..be913371 --- /dev/null +++ b/chapter32/src/main/java/com/seaofnodes/simple/parser/Strings.java @@ -0,0 +1,59 @@ +package com.seaofnodes.simple.parser; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.Ary; + +/** Interpolation expands to ordinary sys.text calls. The library itself uses + * no interpolation, so it can be compiled from source without staging. */ +final class Strings { + private final Parser P; + Strings(Parser p) { P=p; } + + Node parse() { + Lexer start=P.loc(); + P.require("\""); + Lexer.StringPart part=P._lexer.stringPart(start); + if( part.end() ) return P.allocations.newString(part.text()); + Node text=P.references.classReference("sys.text",P.loc()).keep(); + P.classInit(P.loc(),text); + Node builder=call(text,"begin",P.loc()).keep(); + while( true ) { + if( part.text().length!=0 ) + call(text,"string",P.loc(),builder,P.allocations.newString(part.text()),P.con('s'),P.con(0),P.con(-1)).isKill(); + if( part.end() ) break; + Lexer.Format fmt=P._lexer.stringFormat(); + Node value=P.expressions.parseAssignment().keep(); + P.require(")"); + Node fptr; + if( fmt.kind()==0 ) { + Node ints=P.references.member(text,"integer",fmt.site()).keep(); + Node floats=P.references.member(text,"floating",fmt.site()).keep(); + Node strings=P.references.member(text,"string",fmt.site()).keep(); + fptr=new FormatNode(value,ints.unkeep(),floats.unkeep(),strings.unkeep(),fmt.site()).peephole(); + } else { + String family="diuoxXcb".indexOf(fmt.kind())>=0 ? "integer" : fmt.kind()=='s' ? "string" : fmt.kind()=='t' ? "time" : "floating"; + fptr=P.references.member(text,family,fmt.site()); + } + call(text,fptr,fmt.site(),builder,value.unkeep(),P.con(fmt.kind() | fmt.flags()<<8), + P.con(fmt.width()),P.con(fmt.precision())).isKill(); + part=P._lexer.stringPart(start); + } + // String syntax promises this result type even when sys.text is still + // awaiting its source parse. Check/convert through the normal IR. + Node result=call(text.unkeep(),"end",P.loc(),builder.unkeep()); + return P.conversions.convertExpr(result,TypeMemPtr.make(P.types.typeAry(TypeInteger.U8,true)).makeRO()); + } + + private Node call(Node text, String name, Lexer site, Node... values) { + return call(text,P.references.member(text,name,site),site,values); + } + + private Node call(Node text, Node fptr, Lexer site, Node... values) { + Ary<Node> args=new Ary<>(Node.class); + args.push(P.ctrl()); args.push(P.mem()); args.push(text); + for( Node value:values ) args.push(value); + args.push(fptr); + return P.functions.functionCall(args,site); + } +} diff --git a/chapter32/src/main/java/com/seaofnodes/simple/parser/Structs.java b/chapter32/src/main/java/com/seaofnodes/simple/parser/Structs.java new file mode 100644 index 00000000..3a3d894c --- /dev/null +++ b/chapter32/src/main/java/com/seaofnodes/simple/parser/Structs.java @@ -0,0 +1,340 @@ +package com.seaofnodes.simple.parser; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.node.ScopeNode.Kind; +import com.seaofnodes.simple.type.*; + +/** Struct and constructor declarations, field discovery, and initialization checks. */ +final class Structs { + private final Parser P; + + // 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; // Pop nested stack + + // 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 = TypeStruct.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("<ctor>"); + // 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); + // The visible constructor name denotes allocation, not the hidden initializer. + sig = alloc; + ts = ts.replace(fld.makeFrom(alloc)); + ts = ts.add(Field.make("<new>",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 = <new>" + // and is a nicer version of updateSelfAsFieldsDiscovered. + P._scope.define(typeName, sig, true, new FunPtrNode(sig,P._code._start,P._code.link(alloc).ret()).peephole(), P.loc()); + Var binding = P._scope.lookup(typeName); + declareField(binding,P._scope.in(binding),false); + + 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; + P._lexer.skipWhiteSpace(); + Lexer site=P.loc(); + String name = P.requireId(); + String expect = initFieldName(self._name); + if( name != expect ) + throw Parser.error("Constructor name '" + name + "' must match type name '" + expect + "'",site); + P.require("="); + if( _pendingCtor!=null ) throw Parser.error("Redefining constructor '"+name+"'",site); + _pendingCtor = new Constructor(name,P.loc()); + // Parse the body after all field declarations are known, so self.x + // and x resolve the same field 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,true); + TypeFunPtr sig = (TypeFunPtr)ctor._type; + String clzName = TypeStruct.addClzPrefix(self._name); + TypeStruct clz = (TypeStruct)Parser.TYPES.get(clzName); + Field old = clz==null ? null : clz.field("<ctor>"); + if( old != null ) + throw P.error("Redefining constructor '" + name + "'"); + Field fld = Field.make("<ctor>",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 ) { + // Record & restore global state set during parsing the <init> 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 <clinit> 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 ? ".<clinit>" : ".<init>")).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); + // Unwind global state. + P.ctrl(oldCtrl.unkeep()); + P.mem (oldMem .unkeep()); + return ret; + } + + // <cl/init> 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 ) { + // One object, unknown contents. The signature must not promise that + // its declared field values have already been supplied. + Type targ = isClz ? TypeInteger.BOT : TypeMem.makePrivate(Type.BOTTOM); + // 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(Type.BOTTOM); + Type[] targs = new Type[]{ TypeMemPtr.make((byte)2,tself,isClz).withPartial(!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 <init> order, 2nd in the file just behind the <clinit> + if( isClz ) { + assert TypeStruct.startsClzPrefix( clzBare ); + clzBare = clzBare.substring(TypeStruct.CLZ.length()).intern(); + order = 2; // 2 is always the <clinit> 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 finishInitializer( String typeName, boolean isClz, ParmNode self ) { + 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 + // Default <init>/<clinit> defines the struct and can sharpen fields. + // A named constructor only initializes the already-closed struct. + for( int i = 0; i<tself.nkids(); i++ ) { + Field tfld = tself._fields[i]; + int vidx = fieldVarIdx(base,tfld._fname); + if( vidx == -1 ) + continue; + Var v = P._scope.var(vidx); + // Forward-ref fields where placed in tself but will get promoted + // to an outer scope - and should not be in tself. + if( v._fref ) + tself = tself.remove(i--); + else if( v.type() != tfld._t ) { + assert v.type().isa(tfld._t); + tself = tself.replace( tfld.makeFrom( v.type() ) ); + } + } + + // Close Struct type after parsing struct body. + Parser.TYPES.put( tself._name, tself = tself.close() ); + // Improve the receiver type in scope. + // Class self-type is a singleton pointer. Instance <init> 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)).withPartial(true); + FunNode fun = self.fun(); + fun.setSig(fun.sig().makeFrom(self._type,0)); + + // When can _returnScope be null here? A never-exit constructor will + // not have any returns, and thus no need to gather values and store + // them into the (never) constructed object + if( P.functions._returnScope==null ) + return; + + // Class singleton fields retain their store-at-exit path. Instance + // initializers already returned their current private memory. + if( !isClz ) return; // Instance fields already have their Stores. + Node mmm = P.functions._returnScope.mem(1); + + // Store constructor results into fields + for( int i = 0; i<tself.nkids(); i++ ) { + Field fld = tself._fields[i]; + int vidx = fieldVarIdx(base,fld._fname); + if( vidx == -1 ) + continue; + Var v = P._scope.var(vidx); + if( v._fref || v._extern!=0 ) continue; // C storage has no Simple initializer + Node val = P.functions._returnScope.in(vidx); + // A numeric merge can still be untyped while parsing. Retain its + // declared conversion at the helper boundary, as assignments do. + if( fld._t instanceof TypeInteger || fld._t instanceof TypeFloat ) + val = P.conversions.convertExpr(val,fld._t); + // Store value into extended struct + Node prior = mmm.keep(); + Node st = P.peep(new StoreNode(null, fld._fname, fld._alias, fld._t, null, prior, self, ConFldOffNode.make(tself,fld._fname), val, fld._final)); + mmm = P.mergeAlias(prior,fld._alias,st); + prior.unkeep(); + } + mmm = mmm.peephole(); + + P.functions._returnScope.mem(mmm); + } + + // Instance declarations establish field metadata and emit their default + // Stores immediately. Required fields emit no Store until assigned. + void declareField(Var var, Node value, boolean uninit) { + if( !(P._scope.klast() instanceof Kind.Func kind) || !FunNode.isInstance(kind._name) ) return; + TypeStruct self = P._scope.constructorSelf(); + TypeStruct shape = (TypeStruct)Parser.TYPES.get(self._name); + Field old = shape.field(var._name); + Field fld = old==null ? Field.make(var._name,var.type(),P._code.alias(P._ref._cname),var._final) : old.makeFrom(var.type()); + Parser.TYPES.put(shape._name,shape = shape.addOrUpdate(fld)); + if( uninit || var._extern!=0 ) return; + Node ptr = P.references.defaultSelf(); + Node mem = P.construction.selfMem().keep(); + Node st = new StoreNode(var._loc,fld._fname,fld._alias,fld._t,P.ctrl(),mem,ptr, + ConFldOffNode.make(shape,fld._fname),value,true).peephole(); + P.construction.store(ptr,fld._alias,st,mem); + mem.unkeep(); + } + + 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 = TypeStruct.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(); + } + + private int fieldVarIdx( int base, String name ) { + for( int i = base; i<P._scope.nIns(); 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<fs.length; i++ ) { + Field fld = self._fields[i]; + fs[i] = fld.makeFrom(fld._t.makeStorage()); + } + return TypeStruct.make(self._name,self._open,fs); + } + + private static String initFieldName( String typeName ) { + if( TypeStruct.startsClzPrefix(typeName) ) + typeName = typeName.substring(TypeStruct.CLZ.length()); + int idx = typeName.lastIndexOf('.'); + return (idx == -1 ? typeName : typeName.substring(idx+1)).intern(); + } +} diff --git a/chapter32/src/main/java/com/seaofnodes/simple/parser/Types.java b/chapter32/src/main/java/com/seaofnodes/simple/parser/Types.java new file mode 100644 index 00000000..501924f0 --- /dev/null +++ b/chapter32/src/main/java/com/seaofnodes/simple/parser/Types.java @@ -0,0 +1,252 @@ +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.type.*; +import com.seaofnodes.simple.util.Ary; + +/** Type syntax, qualified type lookup, and forward type declarations. */ +final class Types { + private final Parser P; + + Types(Parser P) { this.P = P; } + + // Parse a type or restore the cursor and return null. Unknown names need + // a following binding to distinguish a forward type from an expression. + + // Structs have nested names, and can be discovered with a partial name + // match. Example, searching for a type name "C.D" in the namespace "A.B". + // This will match "A.B.C.D", then "A.C.D", then "C.D". + + // Will also match external names like "sys.io" or "externModule.subtype.subtype" + + Type parseType() { + if( P.peek('{') ) return parseFunctionType(); + + int old1 = P.pos(); + boolean writable = P.match("!"); + boolean readonly = !writable && P.match("~"); + String tname = P._lexer.matchId(); + if( tname==null ) return P.posT(old1); + + Type t0 = Parser.TYPES.get(tname); + if( Parser.KEYWORDS.contains(tname) ) { + if( t0==null ) return P.posT(old1); + } else { + if( t0==Type.BOTTOM || t0==Type.TOP ) return t0; // var/val + tname = typeName(tname).intern(); + t0 = Parser.TYPES.get(tname); + // Bare forward types use the same file-relative name as `new`. + // A later sibling declaration must complete this very type. + if( t0 == null && tname.indexOf('.') == -1 ) { + tname = fullTypeName(tname); + t0 = Parser.TYPES.get(tname); + } + } + Type t1 = t0==null ? TypeStruct.forward(tname) : t0; + + // Structs are always actually references + if( t1 instanceof TypeStruct ts1 ) + t1 = TypeMemPtr.make(ts1); + + // A qualifier before the name applies to the struct reference, not + // to an enclosing array. Arrays have their own [] / [~] qualifier. + if( t1 instanceof TypeMemPtr tmp ) { + if( readonly || !writable ) t1 = tmp.makeRO(); + } else if( writable || readonly ) + return P.posT(old1); + + // Nest arrays and '?' as needed + Type t2 = t1; + while( true ) { + P._lexer.skipWhiteSpace(); + Lexer site=P.loc(); + if( P.match("?") ) { + if( t2 instanceof TypeMemPtr tmp ) { + if( tmp.nullable() ) throw Parser.error("Type "+t2+" already allows null",site); + t2 = tmp.makeNullable(); + } else + throw Parser.error("Type "+t0+" cannot be null",site); + } else if( P.match("[~]") ) { + t2 = TypeMemPtr.make(typeAry(t2,true)).makeRO(); + } else if( P.match("[]") ) { + t2 = TypeMemPtr.make(typeAry(t2,false)); + } else + break; + } + + // Check no forward ref + if( t0 != null ) return t2; + // Check valid forward ref, after parsing all the type extra bits. + // Cannot check earlier, because cannot find required 'id' until after "[]?" syntax + int old2 = P.pos(); + P.match("^"); // Constructor parameter qualifier; parsed by Functions. + if( !P.match("!") ) P.match("~"); + String id = P._lexer.matchId(); + if( !(P.peek(',') || P.peek(';') || P.peek('=') || P.match("->")) || id==null ) + return P.posT(old1); // Reset lexer to reparse + P.pos(old2); // Reset lexer to reparse + // Yes a forward ref, so declare it + forwardRefType(tname,(TypeStruct)((TypeMemPtr)t1)._obj); + // Return the (array, final) type + return t2; + } + + TypeMemPtr forwardRefType( String tname, TypeStruct tself ) { + Parser.TYPES.put(tname,tself); + String clzName = TypeStruct.addClzPrefix( tname ); + // Only a struct declaration publishes an instance initializer. A + // forward type may name a file with just <clinit>, so do not invent + // a constructor field (or overwrite an already parsed class). + Parser.TYPES.putIfAbsent(clzName,TypeStruct.make(clzName,true)); + return TypeMemPtr.make(tself); + } + + TypeMemPtr forwardRefType( String tname ) { + tname = fullTypeName(tname); + return forwardRefType(tname,TypeStruct.forward(tname)); + } + + String fullTypeName( String tname ) { + String nest = P._nestedType, fullq; + while( true ) { + fullq = nest+"."+tname; + if( Parser.TYPES.get(fullq) != null ) + return fullq.intern(); + int idx = nest.lastIndexOf('.'); + if( idx== -1 ) return fullq.intern(); + nest = nest.substring(0,idx); + } + } + + // Make an array type of t. Always record a mutable version, + // but return the requested version. + TypeStruct typeAry( Type t, boolean efinal ) { + // Non-null reference arrays are valid types, even though an ordinary + // zero-filled `new T[len]` cannot construct one. Allocation retains + // that check in parseNew(); trusted runtimes (notably argv construction) + // may fill the private array completely before publishing it. + String tname = ("[]"+t.str()).intern(); + TypeStruct ta = (TypeStruct)Parser.TYPES.get(tname); + if( ta==null ) { + // Primitive arrays use the null compunit + String rcname = Parser.TYPES.get(t) instanceof TypeStruct ? P._ref._cname : ("_."+t).intern(); + ta = TypeStruct.makeAry(tname,TypeInteger.U32,P._code.alias(rcname),t,P._code.alias(rcname), false ); + Parser.TYPES.put(tname,ta); + } + // Already have the aliases, just efinal is wrong + return TypeStruct.makeAry(tname,TypeInteger.U32,ta._fields[0]._alias,t,ta._fields[1]._alias,efinal ); + } + + Type implicitSelfType() { + TypeStruct self = P._scope.constructorSelf(); + // Function types without a body must allow for writes. Function + // expressions can infer a weaker requirement in MethodAccess. + return self == null ? TypePtr.PTR : TypeMemPtr.make(self); + } + + // A function type is `{ type... -> 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<Type> ts = new Ary<>(Type.class); + // Always reserve a receiver slot. Outside constructor scopes the + // broad signature also marks the hidden slot for the machine ABI. + 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/chapter32/src/main/java/com/seaofnodes/simple/parser/Var.java b/chapter32/src/main/java/com/seaofnodes/simple/parser/Var.java new file mode 100644 index 00000000..5361148f --- /dev/null +++ b/chapter32/src/main/java/com/seaofnodes/simple/parser/Var.java @@ -0,0 +1,56 @@ +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 + 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 + + void refineType(Type type) { + assert type.isa(_type) : _name+": "+_type+" -> "+type; + _type = type; + } + + // 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 " : "")+_type.toString()+(_final ? " ": " !")+_name; + } +} diff --git a/chapter32/src/main/java/com/seaofnodes/simple/parser/package-info.java b/chapter32/src/main/java/com/seaofnodes/simple/parser/package-info.java new file mode 100644 index 00000000..828ac6d9 --- /dev/null +++ b/chapter32/src/main/java/com/seaofnodes/simple/parser/package-info.java @@ -0,0 +1,14 @@ +/** + * Handwritten recursive-descent parsing directly into Sea-of-Nodes IR. + * + * <p>{@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. + * + * <p>See {@code chapter32/docs/32-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; |
