From d32f97238c903765dec4e9a9f3cbfa5fd12cded6 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Mon, 10 Aug 2026 11:11:18 -0700 Subject: Chapter 25: Modules, Separate Compilation, and SSA Construction Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: Jun Kawasaki Co-authored-by: Claude Opus 5 --- src/main/java/com/seaofnodes/simple/Parser.java | 2117 ++++++++++++++++------- 1 file changed, 1458 insertions(+), 659 deletions(-) (limited to 'src/main/java/com/seaofnodes/simple/Parser.java') diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index 9cf565ac..cd80b3ff 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -1,11 +1,13 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; -import com.seaofnodes.simple.util.Utils; import com.seaofnodes.simple.node.ScopeNode.Kind; + +import static com.seaofnodes.simple.util.Utils.TODO; + import java.util.*; /** @@ -17,16 +19,32 @@ import java.util.*; */ public class Parser { - public static ConstantNode ZERO; // Very common node, cached here - public static ConstantNode NIL; // Very common node, cached here - public static XCtrlNode XCTRL; // Very common node, cached here - // Compile driver public final CodeGen _code; // The Lexer. Thin wrapper over a byte[] buffer with a cursor. private Lexer _lexer; + // Class prefix string; TODO: use something short: "%" + public static final String CLZ = "class:"; + private static final String clzPrefix = CLZ; + public static String addClzPrefix( String x ) { + assert !x.startsWith(clzPrefix); + return (clzPrefix+x).intern(); + } + public static boolean startsClzPrefix( String s ) { + return s.startsWith(clzPrefix); + } + public static boolean isPublicClassName( String name ) { + if( startsClzPrefix(name) ) name = name.substring(clzPrefix.length()); + return !name.isEmpty() && name.charAt(0)!='_' && name.indexOf("._")==-1; + } + + // Source file for compilation + public CompUnit _ref; + + // Current classname being parsed + private 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 @@ -78,34 +96,20 @@ public class Parser { */ public final Stack _xScopes = new Stack<>(); - ScopeNode _continueScope; - ScopeNode _breakScope; // Merge all the while-breaks here - FunNode _fun; // Current function being parsed + ScopeNode _breakScope; // Merge all the while-breaks here + ScopeNode _continueScope; // Merge all the while-continues here + ScopeNode _returnScope; // Merge all the function exits here + Ary _frefs; // Forward refs created during this parse + TypeStruct _ctorOpenStruct; // Open struct being initialized by an allocation constructor block. + // Constructor exit types survive scope teardown until all fields are known. + // A null entry denotes a constructor with no returning path. + private ArrayList> _ctorExits; // Mapping from a type name to a Type. The string name matches // `type.str()` call. - public static HashMap TYPES = defaultTypes(); - - // Mapping from a type name to the constructor for a Type. - public final HashMap INITS; - - - public Parser(CodeGen code, TypeInteger arg) { - _code = code; - _scope = new ScopeNode(); - _continueScope = _breakScope = null; - ZERO = con(TypeInteger.ZERO).keep(); - NIL = con(Type.NIL).keep(); - XCTRL= new XCtrlNode().peephole().keep(); - TYPES = defaultTypes(); - INITS = new HashMap<>(); - } - - @Override - public String toString() { return _lexer.toString(); } - - public static HashMap defaultTypes() { - return new HashMap<>() {{ + public static final HashMap TYPES = new HashMap<>(); + public static final HashMap INIT_TYPES = + new HashMap<>() {{ put("bool",TypeInteger.U1 ); put("byte",TypeInteger.U8 ); put("f32" ,TypeFloat .F32); @@ -123,172 +127,408 @@ public class Parser { put("val" ,Type.TOP); // Marker type, indicates type inference put("var" ,Type.BOTTOM); // Marker type, indicates type inference }}; + + + public Parser(CodeGen code ) { + _code = code; } + @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); } + // Read and set CTRL private Node ctrl() { return _scope.ctrl(); } private N ctrl(N n) { return _scope.ctrl(n); } - - public void parse() { - // Graph callbacks during scope setup need a source position. - _lexer = new Lexer(sys.SYS); - + // Read and set Memory + private Node mem() { return _scope.mem(1); } + private void mem(Node mem) { _scope.mem(mem); } + // Structural label for precise memory Phis. The '$' prefix cannot be + // referenced in Simple source. + public static String memName(int alias) { return ("$"+alias).intern(); } + + // Ordinary parsing carries one whole-memory value. Alias partitioning is + // graph optimization, not parser state. + private void storeMem( Node st, int alias, Node prior ) { + mem(alias==1 ? st : mergeAlias(prior,alias,st)); + } + + // A semantic graph partition representing the complete memory after a + // precise alias update. ScopeNode treats this as one opaque value. + private 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); + } + + + public Ary parse( CompUnit ref ) { + assert _scope == null && _breakScope == null && _continueScope == null && _returnScope == null; + assert _frefs == null; + _lexer = new Lexer(ref._src); + _frefs = new Ary<>(FRefNode.class); + // 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); - _scope.define(ScopeNode.ARG0, TypeInteger.BOT, false, null, _lexer); - - ctrl(XCTRL); - _scope.mem(con(TypeMem.BOT)); + // Track active scopes for Graph display + _xScopes.push(_scope); + ctrl(_code.XCTRL); + mem(con(TypeMem.BOT)); - // Parse the sys import - while( !_lexer.isEOF() ) { - parseStatement(); - _lexer.skipWhiteSpace(); - } + // File-level struct declaration + _ref = ref; + _nestedType = ref._cname; + String typeName = addClzPrefix(ref._cname); - // Reset lexer for program text - _lexer = new Lexer(_code._src); - _xScopes.push(_scope); + ReturnNode clzret = parseStruct( true, typeName ); - // Parse whole program, as-if function header "{ int arg -> body }" - parseFunctionBody( _code._main,loc(),"arg"); - - // Kill an empty default main. Keep only if it was explicitly defined - // (programmer asked for a "main") or it has stuff (i.e. beginner - // default main). - FunNode main = _code.link(_code._main); - StopNode stop = _code._stop; - // Gather an explicit main - FunNode xmain = null; - for( Node n : stop._inputs ) - if( n instanceof ReturnNode ret && "main".equals(ret.fun()._name) ) - if( xmain != null ) throw Utils.TODO(); - else xmain = ret.fun(); - - if( main.ret().expr()._type==Type.TOP && main.uctrl()==null ) { - // Kill an empty default main; so it does not attempt to put a - // "main" in any final ELF file - main.setDef(1,XCTRL); // Delete default start input - stop.delDef(stop._inputs.find(main.ret())); - if( xmain != null ) - _code.setMain(xmain); + if( !_lexer.isEOF() ) throw _errorSyntax("unexpected"); - } else { - // We have a non-empty default main. - if( xmain != null ) - // Found an explicit "main" AND we have a default "main" - throw error("Cannot define both an explicit main and a default main"); - main._name = "main"; + // All still-unresolved forward refs + // should immediately resolve to a file-based name which is a Simple + // class type. + Ary frefs = new Ary<>(FRefNode.class); + for( FRefNode fref : _frefs ) { + if( fref.nIns() != 1 && fref._con == FRefNode.FREF_TYPE ) continue; + CompUnit cu = ParseAll.findCompUnitOrThrow(_code,_ref,fref._name); + fref._con = TypeMemPtr.make((byte)2,TypeStruct.make(addClzPrefix(cu._cname),true),true); + frefs.push(fref); } - if( !_lexer.isEOF() ) throw _errorSyntax("unexpected"); + // The class being published + ref._clz = (TypeStruct)TYPES.get(typeName); // Clean up and reset _xScopes.pop(); _scope.kill(); - for( StructNode init : INITS.values() ) - init.unkeep().kill(); - INITS.clear(); - stop.peephole(); + _scope = null; + _frefs = null; + + return frefs; } + + /** * Parses a function body, assuming the header is parsed. */ - private ReturnNode parseFunctionBody( TypeFunPtr sig, Lexer loc, String... ids) { + private ReturnNode parseFunctionBody( TypeFunPtr sig, Lexer loc, String[] ids) { return parseFunctionBody(sig, loc, null, ids); } - private ReturnNode parseFunctionBody( TypeFunPtr sig, Lexer loc, java.util.BitSet finals, String... ids) { - // If this is a method, record & restore the existing struct fields, - // which are also the struct initializers. The method might update - // mutable fields, so when the function parse is done reset back to - // pre-function-parse values. - Node[] preParse = new Node[_scope.nIns()]; - for( int i=0; i<_scope.nIns(); i++ ) - preParse[i] = _scope.in(i)==null ? null : _scope.in(i).keep(); + private ReturnNode parseFunctionBody( TypeFunPtr sig, Lexer loc, java.util.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 = _scope.save(); + + // Parse function body normally + ReturnNode ret = _parseFunctionBody(null, sig,loc,finals,ids); + + // Reset all fields to pre-parse days + _scope.restore(preParse); + return ret; + } + + + // Parse a function body + + // Stack the {break,continue,return} scopes and a new lexical scope. + // Build a FunNode and parameters, extending scope by parm names. + // Parse the function body + // - while( not end-of-function ) + // - - parseStatement + // - - If isInit, also incrementally extend the self-type. + // If isInit + // - upgrade and close the self-type + // - Gather fields and store values + // - returns self, not last + // Unstack the {break,continue,return} scopes. + + private ReturnNode _parseFunctionBody( String funName, TypeFunPtr sig, Lexer loc, String[] ids) { + return _parseFunctionBody(funName, sig, loc, null, ids); + } + + private ReturnNode _parseFunctionBody( String funName, TypeFunPtr sig, Lexer loc, java.util.BitSet finals, String[] ids) { + boolean isInit = FunNode.isInit(funName); + boolean isCtor = isInit || isExplicitConstructorName(funName); + String typeName = isCtor ? ((TypeMemPtr)sig._sig[0])._obj._name : null; // Stack parser state on the local Java stack, and unstack it later - FunNode oldfun = _fun; - ScopeNode breakScope = _breakScope; _breakScope = null; + _scope.push(new Kind.Func(funName)); + ScopeNode breakScope = _breakScope; _breakScope = null; ScopeNode continueScope = _continueScope; _continueScope = null; + ScopeNode returnScope = _returnScope; _returnScope = null; - FunNode fun = _fun = (FunNode)peep(new FunNode(loc(),sig,_nestedType,null,_code._start)); + int oldUID = _code.UID(); // Used to approximate function size + FunNode fun = (FunNode)peep(new FunNode(loc(),sig, funName, _ref, null, _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). _code.link(fun); - Node rpc = new ParmNode("$rpc",0,TypeRPC.BOT,fun,con(TypeRPC.BOT)).peephole(); - - // Build a multi-exit return point for all function returns - RegionNode r = new RegionNode( null,null,null).init(); - assert r.inProgress(); - PhiNode rmem = new BulkMemPhiNode(ScopeNode.MEM0,r,null).init(); - PhiNode rrez = new PhiNode(ScopeNode.ARG0,Type.BOTTOM,r,null).init(); - ReturnNode ret = new ReturnNode(r, rmem, rrez, rpc, fun).init(); - fun.setRet(ret); - assert ret.inProgress(); - _code._stop.addDef(ret); - + Node rpc = 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. - _scope.push(new Kind.Func()); - ctrl(fun); // Scope control from function - // Unknown callers supply whole memory; field aliases are discovered lazily. - _scope.mem(new ParmNode(ScopeNode.MEM0,1,TypeMem.BOT,fun,con(TypeMem.BOT)).peephole()); + _scope.ctrl(fun); // Scope control from function + // Private mem alias tracking per function + Node defaultMem = new ProjNode(_ref._start,1,ScopeNode.MEM0).peephole(); + Node privMem = new ParmNode(ScopeNode.MEM0,1,TypeMem.BOT,fun,defaultMem).peephole(); + mem(privMem); // All args, "as-if" called externally for( int i=0; i and , local vars are really struct fields and + // get exposed as discovered. This allows late local functions to + // use early declared fields. + if( isInit ) + nvar = updateSelfAsFieldsDiscovered( typeName, nvar ); + } + + ParmNode self = fun.parm(2); + // Last expression is the return + if( ctrl()._type==Type.CONTROL ) { + // Constructors get special return types + if( fun.isClz() ) { + assert last!=null; + } else if( isCtor ) { + last = fun.parm(3); } - - // Pop off the inProgress node on the multi-exit Region merge - assert r.inProgress(); - r ._inputs.pop(); - rmem._inputs.pop(); - rrez._inputs.pop(); - r._loc = loc(); // Final position - assert !r.inProgress(); - - // Force peeps, which have been avoided due to inProgress - ret.setDef(1,rmem.peephole()); - ret.setDef(2,rrez.peephole()); - ret.setDef(0,r.peephole()); - ret = (ReturnNode)ret.peephole(); - - // Function scope ends - _scope.pop(); - _fun = oldfun; - _breakScope = breakScope; + addReturn(last); + // exit path is now dead (nothing live after a "return") + } + if( isCtor ) + upgradeSelfTypeAndStoreFields( typeName, fun.isClz(), self, fun.parm(3), isInit ); + + // Build a return from the _returnScope. + // Can be no returns for never-exit functions + Node rctl = _returnScope==null ? _code.XCTRL : _returnScope.ctrl().peephole(); + Node rmem = rctl==_code.XCTRL ? con(TypeMem.TOP) : _returnScope.mem(); + Node expr = rctl==_code.XCTRL ? con(Type.TOP) : _returnScope._inputs.last().peephole(); + ReturnNode ret = (ReturnNode)peep(new ReturnNode(rctl, rmem, expr, rpc, fun)); + fun.setRet(ret); + // Approximate function size, for inlining heuristics + fun._approxUIDs = _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 + _ref.addFun(_code,fun); + + // Unstack parser state + if( _returnScope != null ) _returnScope.kill(); + _returnScope = returnScope; _continueScope = continueScope; - - // Reset all fields to pre-parse days - for( int i=0; i/ defines the struct and can sharpen fields. + // A named constructor only initializes the already-closed struct. + for( int i=0; i receives the + // broad allocation pointer, while private memory tracks initialized fields. + self._declaredType = self._type = isClz ? TypeMemPtr.make((byte)2,tself,true) : TypeMemPtr.make(constructorRecv(tself)); + FunNode fun = self.fun(); + fun.setSig(fun.sig().makeFrom(self._type,0)); + if( !isClz ) // returns upgraded private memory + smem._declaredType = smem._type = TypeMem.makePrivate(tself); + } + + if( !upgrade ) { + IdentityHashMap exit = null; + if( _returnScope!=null && !_returnScope.ctrl()._type.isHigh() ) { + exit = new IdentityHashMap<>(); + int first = _scope._kinds.at(_scope.depth()-2)._lexSize+2; + for( int i=first; i updates the private memory that got + // passed in - is treated like a normal argument and not like memory. + Node mmm = isClz ? _returnScope.mem(1) : smem; + + + // Store constructor results into fields + for( int i=0; i return memory. + _returnScope.mem(mmm); + //_code.add(mmm); + } + + // Validate each user constructor, or an implicit empty one, before the + // declaration scope goes away. Later fields use their declaration defaults. + private static boolean initialized(Type t) { + return t!=Type.BOTTOM && !t.isHigh() && (!(t instanceof TypeNil tn) || tn.notNull()); + } + + private void checkInitFields(TypeStruct ts, int base) { + if( _returnScope==null || _returnScope.ctrl()._type.isHigh() ) return; + boolean implicit = _ctorExits.isEmpty(); + if( implicit ) _ctorExits.add(new IdentityHashMap<>()); + for( IdentityHashMap exit : _ctorExits ) { + if( exit==null ) continue; + for( Field fld : ts._fields ) { + int idx = fieldVarIdx(base,fld._fname); + if( idx == -1 ) continue; + Var v = _scope.var(idx); + if( !v._uninit || v._fref ) continue; + Type t = exit.getOrDefault(v,_returnScope.in(idx)._type); + if( !initialized(t) ) + throw error("'"+ts._name+"' is not fully initialized, field '"+fld._fname+ + (implicit ? "' needs to be set in a constructor" : + "' is only partially set in the constructor"),v._loc); + } + } + } + + private int fieldVarIdx( int base, String name ) { + for( int i=base; i<_scope.nIns(); i++ ) + if( _scope.var(i)._name == name ) + return i; + return -1; + } + + // Named constructors update field Vars from the enclosing initializer + // scope. Constructor arguments and locals begin at limit and must not + // shadow the field state gathered into private memory. + private int fieldVarIdxBefore( int limit, String name ) { + for( int i=limit-1; i>=0; i-- ) + if( _scope.var(i)._name == name ) + return i; + return -1; + } + + private boolean isConstructorDecl(String name) { + TypeStruct self = _scope.constructorSelf(); + return self != null && name == initFieldName(self._name); + } + + private boolean inExplicitConstructor() { + Kind.Func func = (Kind.Func)_scope._kinds.at(_scope.enclosingFuncOrDecl()); + return isExplicitConstructorName(func._name); + } + + private boolean isExplicitConstructorName(String funName) { + TypeStruct self = _scope.constructorSelf(); + return self != null && funName == (self._name+"."+initFieldName(self._name)).intern(); + } + + private static TypeStruct constructorRecv(TypeStruct self) { + Field[] fs = new Field[self._fields.length]; + for( int i=0; i body }; + private Node parseConstructorDeclaration() { + TypeStruct self = _scope.constructorSelf(); + assert self != null; + String name = requireId(); + String expect = initFieldName(self._name); + if( name != expect ) + throw error("Constructor name '" + name + "' must match type name '" + expect + "'"); + require("="); + Node ctor = constructorFunc(name); + TypeFunPtr sig = (TypeFunPtr)ctor._type; + String clzName = addClzPrefix(self._name); + TypeStruct clz = (TypeStruct)TYPES.get(clzName); + Field old = clz==null ? null : clz.field(""); + if( old != null ) + throw error("Redefining constructor '" + name + "'"); + Field fld = Field.make("",sig,_code.alias(_ref._cname),true); + TYPES.put(clzName,clz==null ? TypeStruct.make(clzName,true,fld) : clz.add(fld)); + return require(ctor,";"); + } + /** * Parses a while statement * @@ -386,7 +654,7 @@ public class Parser { // used as an indicator to switch off peepholes of the region and // associated phis; see {@code inProgress()}. - ctrl(new LoopNode(loc(),ctrl()).peephole()); // Note we set back edge to null here + ctrl(new LoopNode(loc(),null,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). @@ -405,8 +673,8 @@ public class Parser { // IfNode takes current control and predicate Node ifNode = new IfNode(ctrl(), pred.keep()).peephole(); // Setup projection nodes - Node ifT = new CProjNode(ifNode. keep(), 0, "True" ).peephole().keep(); - Node ifF = new CProjNode(ifNode.unkeep(), 1, "False").peephole(); + 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; @@ -459,6 +727,8 @@ public class Parser { // 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(_scope); + exit.balanceLoopFRefs(_scope); head.endLoop(_scope, exit); head.unkeep().kill(); @@ -476,12 +746,12 @@ public class Parser { _xScopes.push( exit ); } _scope = exit; - return ZERO; + return _code.ZERO; } private ScopeNode jumpTo(ScopeNode toScope) { ScopeNode cur = _scope.dup(); - ctrl(XCTRL); // Kill current scope + ctrl(_code.XCTRL); // Kill current scope // Prune nested lexical scopes that have depth > than the loop head // We use _breakScope as a proxy for the loop head scope to obtain the depth while( cur.depth() > _breakScope.depth() ) @@ -499,7 +769,7 @@ public class Parser { private void checkLoopActive() { if (_breakScope == null) throw error("No active loop for a break or continue"); } - private Node parseContinue() { checkLoopActive(); _continueScope = require(jumpTo( _continueScope ),";"); return ZERO; } + private Node parseContinue() { checkLoopActive(); _continueScope = require(jumpTo( _continueScope ),";"); return _code.ZERO; } private Node parseBreak () { checkLoopActive(); // At the time of the break, and loop-exit conditions are only valid if @@ -507,8 +777,8 @@ public class Parser { // conditions here, not the union. _breakScope.removeGuards(_breakScope.ctrl()); _breakScope = require(jumpTo(_breakScope ),";"); - _breakScope.addGuards(_breakScope.ctrl(), null, false); - return ZERO; + _breakScope.addGuards((CFGNode)_breakScope.ctrl(), null, false); + return _code.ZERO; } // Look for an unbalanced `)`, skipping balanced @@ -518,7 +788,7 @@ public class Parser { // Next X char handles skipping complex comments switch( _lexer.nextXChar() ) { case Character.MAX_VALUE: - throw Utils.TODO(); + throw TODO(); case ')': if( --paren<0 ) { posT( pos() - 1 ); @@ -552,8 +822,8 @@ public class Parser { pred.keep(); Node ifNode = new IfNode(ctrl(), pred).peephole(); // Setup projection nodes - Node ifT = new CProjNode(ifNode. keep(), 0, "True" ).peephole().keep(); - Node ifF = new CProjNode(ifNode.unkeep(), 1, "False").peephole().keep(); + 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 = _scope.dup(); // Duplicate current scope @@ -569,7 +839,7 @@ public class Parser { case ":" -> parseAsgn(); // pred ? asgn; case "&&" -> parseLogical(); // pred && expr case "||" -> pred; // pred || expr_is_ignored - default -> throw Utils.TODO(); + default -> throw TODO(); }; lhs.keep(); _scope.removeGuards(ifT); @@ -592,12 +862,14 @@ public class Parser { Node rhs = switch( fside ) { case "else" -> (doRHS=match(fside)) ? parseStatement() : con(lhs._type.makeZero()); case ":" -> (doRHS=match(fside)) ? parseAsgn() : con(lhs._type.makeZero()); - case "&&" -> rhs = pred; - case "||" -> rhs = parseLogical(); - default -> throw Utils.TODO(); + case "&&" -> con(lhs._type.makeZero()); // pred && expr_is_ignored + case "||" -> parseLogical(); // pred || expr + default -> throw TODO(); }; rhs.keep(); _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 = _scope; pred.unkeep(); @@ -617,12 +889,13 @@ public class Parser { // Merge results RegionNode r = ctrl(tScope.mergeScopes(fScope,loc())); - Node ret = peep(new PhiNode("",lhs._type.meet(rhs._type).glb(false),r,lhs.unkeep(),rhs.unkeep())); + Node ret = peep(new PhiNode("",r,lhs.unkeep(),rhs.unkeep())); // Immediately fail e.g. `arg ? 7 : ptr` ParseException err; - if( !fside.equals("else") && (err=ret.err()) !=null ) throw err; + if( !fside.equals("else") && (err=ret.err()) !=null ) throw err; + ret.keep(); r.peephole(); - return ret; + return ret.unkeep(); } /** @@ -636,20 +909,69 @@ public class Parser { */ private Node parseReturn() { var expr = require(parseAsgn(), ";"); - // Force the lazy whole-memory Phi before closing this exit. - _fun.addReturn(ctrl(), _scope.mem(), expr); - ctrl(XCTRL); // Kill control - return expr; + return addReturn(expr); } + private Node addReturn(Node expr) { + expr.keep(); + // Need default memory, since it can be lazy, need to force + // a non-lazy Phi + mem(); // Force a pending lazy bulk-memory Phi + // For and - all fields in scope will be live-on-exit + // and stored into `self` and need to have lazy-phi's inserted. + int lexN = _scope.enclosingFuncOrDecl(); + Kind.Func k = (Kind.Func)_scope._kinds.at(lexN); + if( FunNode.isInit(k._name) ) { + int nestedLexSize = lexN+1 < _scope.depth() ? _scope._kinds.at(lexN+1)._lexSize : _scope.nIns(); + for( int i=k._lexSize; i and - ALL FIELDS IN LAST SCOPE are live + // and need to have lazy-phi's inserted. + + // And fields might not match.... will need matching Var/define with default values + int rlen = _returnScope.nIns()-1; + RegionNode r = ctrl(new RegionNode(null, null,_returnScope.ctrl(), _scope.ctrl()).init().keep()); + _returnScope._merge(_scope, r, rlen); + Node oldExpr = _returnScope.in(rlen); + _returnScope.setDef(rlen,new PhiNode("$expr", r, oldExpr, expr).peephole()); + _code.add(r); + _returnScope.ctrl(r.unkeep()); + } + ctrl(_code.XCTRL); // Kill control + return expr.unkeep(); + } /** Parse: [name '='] expr */ private Node parseAsgn() { int old = pos(); String name = _lexer.matchId(); - int old_pre_equals = pos(); // Just a plain expression, no assignment. // Distinguish `var==expr` from `var=expr` if( name==null || KEYWORDS.contains(name) || !matchOpx('=','=') ) @@ -657,16 +979,13 @@ public class Parser { // Find variable to update Var def = _scope.lookup(name); + if( def==null ) + def = defineOpenConstructorField(name); if( def==null ) throw error("Undefined name '" + name + "'"); - // If a method var, allow nested blocks and methods, but not fcns or other structs. - // Else safety check for accessing fields out of function scope. - if( instance(def) ) { - pos(old_pre_equals); // setup for `self.name = expr` - Node self = _scope.in(_scope.lookup("self")); // Insert self reference - return parsePostfixName(self,name); - } + if( def._extern!=0 ) // Parse the C binding as a memory lvalue + { pos(old); return parseExpression(); } // TOP fields are for late-initialized fields; these have never // been written to, and this must be the final write. Other writes @@ -674,49 +993,91 @@ public class Parser { if( _scope.in(def._idx)._type!=Type.TOP && def._final && // Inside an allocation, final assign is OK, outside nope. // The alloc() call added the allocation scope - !_scope.canInit(def) ) + !(_scope.inConstructor() && def._idx >= _scope.klast()._lexSize) && + !inExplicitConstructor() ) throw error("Cannot reassign final '"+name+"'"); // Parse assignment expression Node expr = parseAsgn(); // Lift expression, based on type - Node lift = liftExpr(expr.keep(), def.type(), true); + Type decl = def.type(); // Declared type + Node lift = convertExpr(expr.keep(), decl).keep(); // Update _scope.update(name,lift); + + // Check for storing into an instance field instead of a local var + int kx = _scope.kindx(def); // Declaration scope + int fx = _scope.enclosingFunction(); // Enclosing function scope + Kind kk = _scope._kinds.at(kx); + Kind fk = _scope._kinds.at(fx); + // Access instance field from 'self' + if( kx+1 == fx && kk instanceof Kind.Func inst && FunNode.isInstance(inst._name) && + fk instanceof Kind.Func method && !inExplicitConstructor() ) { + // Named field offset on an unknown struct type + TypeMemPtr self = (TypeMemPtr)_scope.var(fk._lexSize).type(); + TypeStruct sobj = (TypeStruct)TYPES.get(self._obj._name); + Field fld = sobj.field(name); + int alias = fld._alias; + Node ptr = _scope.in(method._lexSize); + Node off = fldoff(ptr,name); + Node prior = mem().keep(); + Node st = new StoreNode(loc(), name, alias, decl, ctrl(), prior, ptr, off, lift, inExplicitConstructor()).peephole().keep(); + storeMem(st,alias,prior); + st.unkeep(); + prior.unkeep(); + } + lift.unkill(); + + // Return un-lifted expr return expr.unkeep(); } - // Apply declared access permissions; widen floats and narrow integers. + // Widen ints to floats; narrow wide int types. // Early error if types do not match variable. - private Node liftExpr( Node expr, Type t, boolean isLoad ) { - if( expr._type instanceof TypeMemPtr tmp && TYPES.get(tmp._obj._name).isFRef() ) - throw error("Must define forward ref "+tmp._obj._name); - // Read-only access is deep; a fixed binding alone does not remove access. - if( t instanceof TypeMemPtr tmp && tmp.isFinal() ) { - expr = peep(new ReadOnlyNode(expr)); - } + private Node convertExpr( Node expr, Type t ) { if( !expr._type.accessISA(t) ) - throw error("Type " + expr._type.str() + " is not of declared type " + t.str()); + throw error("Type "+expr._type.str()+" is not of declared type "+t.str()); + if( t instanceof TypeMemPtr tmp && tmp.isFinal() ) + expr = 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() ) - expr = peep(new AddNode(peep(new CastNode(t,ctrl(),expr)),off(tmp._obj,"[]"))); - // Auto-widen int to float - expr = widenInt( expr, t ); - // Auto-narrow wide ints to narrow ints. For loads, emit code to force - // the loaded value to match the declared sign/zero bits. For stores, - // just force the type, acting "as if" the store silently truncates. - if( expr._type instanceof TypeFloat && t instanceof TypeInteger ) - expr = peep(new ToIntegerNode(expr)); - Type et = expr._type; - if( isLoad ) { expr = zsMask(expr,t); et = expr._type; } - else if( et instanceof TypeInteger && t instanceof TypeInteger ) et=t; - - // Type is sane - if( et!=Type.BOTTOM && (!et.shallowISA(t) || !et.accessISA(t)) ) - expr = peep(new CastNode(t.isConstant() ? t : t.widen(),null,expr)); - return expr; + return peep(new AddNode(peep(new PtrToIntNode(expr)),off(tmp._obj,"[]"))); + // Widen ints to floats, narrow wide types + return 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. + private 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; + }; + } + + // 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. + private static Type inferredReturnType(Type t) { + return switch( t ) { + case TypeInteger ti -> TypeInteger.BOT; + case TypeFloat tf -> TypeFloat.F64; + default -> t; + }; } private Node widenInt( Node expr, Type t ) { @@ -745,23 +1106,6 @@ public class Parser { return require(n,";"); } - // Widen a reassignable binding without discarding the initializer's - // permissions. Lattice glb includes readonly memory and is too broad here. - private Type inferredType(Type t) { - if( t instanceof TypeMemPtr tmp ) { - if( tmp._obj.isAry() ) { - Type elem = tmp._obj._fields[1]._t; - if( elem instanceof TypeConAry ) - elem = ((TypeMemPtr)TYPES.get(tmp._obj._name))._obj._fields[1]._t; - return typeAry(elem,tmp._obj._fields[1]._final).withAccess(tmp._ro).makeNullable(); - } - Type base = TYPES.get(tmp._obj._name); - TypeMemPtr ptr = (TypeMemPtr)base; - return ptr.withAccess(tmp._ro).makeNullable(); - } - return t.glb(false); - } - // The binding modifier sits immediately before the name. It never // changes permissions on the referenced object. private boolean bindingFinal(Type t) { @@ -780,27 +1124,45 @@ public class Parser { Lexer loc = loc(); String name = requireId(); // Optional initializing expression follows - boolean fld_final = false; // Fixed field independent of pointee access - boolean initialized = match("="); + boolean fld_final = false; // Field is final, but not deeply final + boolean uninit = false; // Required non-null constructor field Node expr; - if( initialized ) { - expr = isExternDecl() - ? externDecl(name,t) - : parseAsgn(); + if( match("=") ) { + if( isExternDecl() ) { + if( !(t instanceof TypeFunPtr) ) { + Node ptr = externData(name,t); + // The lexical binding is a fixed address; its contents are mutable. + if( !_scope.define(name,t,true,ptr,loc) ) + throw error("Redefining name '"+name+"'",loc); + _scope.lookup(name)._extern = _code.externAlias(name); + return _code.ZERO; + } + expr = externDecl(name,t); + t = expr._type; // Upgrade declared type to the exact extern decl type + } else if( isConstructorDecl(name) ) { + expr = constructorFunc(name); + } else { + expr = parseAsgn(); + } // var/val, then type comes from expression if( inferType ) { if( expr._type==Type.NIL ) throw error("a not-null/non-zero expression"); t = expr._type; - if( !xfinal ) t = inferredType(t); // Widen if not final + if( !xfinal ) t = mutableInferredType(t); } + // expr is a constant function - if( t instanceof TypeFunPtr && expr._type instanceof TypeFunPtr tfp && tfp.isConstant() ) { - if( expr instanceof ExternNode ) t = expr._type; // Upgrade declared type to exact function - else _code.link(tfp).setName(name); // Assign debug name to Simple function + if( t instanceof TypeFunPtr decl && expr._type instanceof TypeFunPtr tfp && tfp.isConstant() ) { + t = decl.makeFrom(tfp.fidx()); + FunNode fun = _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. @@ -808,32 +1170,33 @@ public class Parser { throw errorSyntax("=expression"); // Initial value for uninitialized struct fields. expr = switch( t ) { - // Nullable pointers get a NIL; not-null get a TOP which - // signals that they *must* be initialized in the constructor. - case TypeNil tn -> tn.nullable() ? NIL : con(Type.TOP); - case TypeInteger ti -> xfinal ? con(Type.TOP) : ZERO; - case TypeFloat tf -> con(xfinal ? Type.TOP : TypeFloat.FZERO); + // Required pointers retain their declared shape, but include + // null until every constructor path assigns them. + case TypeNil tn -> tn.nullable() ? con(Type.NIL) : con(t.meet(Type.NIL)); + case TypeInteger ti -> xfinal ? con(Type.BOTTOM) : _code.ZERO; + case TypeFloat tf -> 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 con(tt); } }; - // Nullable fields are set in the constructor, but remain shallow final. - // e.g. final pointer to a r/w array - if( t instanceof TypeNil tn && !tn.nullable() && xfinal ) - fld_final = true; + // 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 - Node lift = liftExpr(expr, t, true); + // Do not let an authoritative Convert hide the nullable + // not-yet-initialized state from constructor-local type flow. + Node lift = uninit ? expr : convertExpr(expr, t); - // Lift type to the declaration. This will report as an error later if - // we cannot lift the type. - if( !lift._type.isa(t) ) - lift = peep(new CastNode(t.widen(),null,lift)); // Define a new name if( !_scope.define(name,t,xfinal || fld_final,lift, loc) ) throw error("Redefining name '" + name + "'", loc); - _scope.lookup(name)._init = initialized; + _scope.lookup(name)._uninit = uninit; return lift; } @@ -845,59 +1208,211 @@ public class Parser { * * @return zero */ - private String _nestedType; - private Node parseStruct() { - // "struct" already parsed, so expect the struct name next. - String old = _nestedType; + private Node parseStruct( ) { + // keyword "struct" already parsed, so expect the struct name next. String typeName = requireId(); - if( old!=null ) typeName = old+"."+typeName; - _nestedType = typeName; - // New declared or forward-ref type - TypeStruct ts = TYPES.get(typeName) instanceof TypeMemPtr tmp ? tmp._obj : TypeStruct.open(typeName); - TYPES.put(typeName,TypeMemPtr.make(ts)); - - // A Block scope parse, and inspect the scope afterward for fields. - _scope.push(new Kind.Define(TypeMemPtr.make(ts))); require("{"); - int lexlen = _scope._kinds.last()._lexSize, nvar=lexlen; - while (!peek('}') && !_lexer.isEOF()) { - parseStatement().isKill(); - while( nvar < _scope._vars._len ) { - Var v = _scope.var(nvar++); - if( !v.isFRef() ) { - ts = ts.add( Field.make( v._name, v.type(), _code.getALIAS(), v._final, v._final && v._init && _scope.in( v._idx )._type != Type.TOP ) ); - TYPES.put( typeName, TypeMemPtr.make( ts ) ); - } - } - } - // Count struct declarations - int varlen = _scope._vars._len; - ts = ts.close(); - TYPES.put(typeName,TypeMemPtr.make(ts)); + // create type class:NESTED.typeName; no fields. - // Generate an initializing struct - StructNode s = new StructNode(ts); - for( int i=lexlen; i"); + ts = ctorFld==null + ? TypeStruct.make(clzName,false,fld) + : TypeStruct.make(clzName,false,fld,ctorFld); + TypeFunPtr alloc = makeAllocator((TypeStruct)TYPES.get(fullName),ret,ctorFld); + ts = ts.add(Field.make("",alloc,_code.alias(_ref._cname),true)); + TYPES.put(clzName,ts); + + // Insert a field in the containing class with the nested class type. + // This is basically sugar for "val CLZNAME = " + // and is a nicer version of updateSelfAsFieldsDiscovered. + _scope.define(typeName, sig, true, new FunPtrNode(sig,_code._start,ret).peephole(), loc()); - // Done with struct/block scope - _nestedType = old; require("}"); - require(";"); - _scope.pop(); - return ZERO; + return require(_code.ZERO,";"); + } + + // 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. + private TypeFunPtr makeAllocator(TypeStruct ts, ReturnNode initRet, Field ctorFld) { + TypeFunPtr ctor = ctorFld==null ? null : (TypeFunPtr)ctorFld._t; + int nargs = ctor==null ? 0 : ctor.nargs()-2; // Hide self and selfMem + Type[] atypes = new Type[nargs]; + for( int i=0; i").intern(); + + int oldUID = _code.UID(); + FunNode fun = (FunNode)new FunNode(loc(),sig,name,_ref,null,_ref._start).peephole(); + _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(_ref._start,1,ScopeNode.MEM0).peephole()).peephole(); + Node[] parms = new Node[nargs]; + for( int i=0; i(); + // Record & restore global state set during parsing the code + Node oldCtrl= _scope.ctrl().keep(); + Node oldMem = _scope.mem ().keep(); + + // Make the future clazz/instance struct. + TypeStruct tself = (TypeStruct)TYPES.get(typeName); + if( tself==null ) + TYPES.put(typeName, tself = TypeStruct.make(typeName,true)); + else { + assert tself._open; + TYPES.put(typeName,tself = tself.defined()); + } + + // Signature of the default constructor + TypeFunPtr sig = structInitSig(isClz,tself); + // Function and argument names of default constructor + String fname = (typeName + (isClz ? "." : ".")).intern(); + String[] ids = new String[]{"self", isClz ? "arg" : "#selfMem"}; + + // Struct decls look like function bodies. Parse function body normally. + ReturnNode ret = _parseFunctionBody(fname,sig,loc(),ids); + _ctorExits = oldExits; + // Unwind global state. + ctrl(oldCtrl.unkeep()); + mem (oldMem .unkeep()); + return ret; + } + + // signature: { self arg/selfMem -> BOT/selfMem } + // Self-memory is the rare *private* (never aliased) memory for the new object. + private TypeFunPtr structInitSig( boolean isClz, TypeStruct tself ) { + // Private uninitialized memory from new object, no escaped values. + TypeMem privMem = isClz ? null : TypeMem.make(1,tself,true,isClz,false,null,null); + Type targ = isClz ? TypeInteger.BOT : privMem; + // Return for private memory has to name all escaped fields, which are not known yet. + // Escape ALL fields, and sharpen later. + Type tret = isClz ? Type.BOTTOM : TypeMem.makePrivate(tself); + Type[] targs = new Type[]{ TypeMemPtr.make((byte)2,tself,isClz), targ }; + // FIDX for FREFs is in the global namespace, needs the correct clz name. + String clzBare = tself._name; + int order = 3; // 3 is always the order, 2nd in the file just behind the + if( isClz ) { + assert startsClzPrefix( clzBare ); + clzBare = clzBare.substring(clzPrefix.length()).intern(); + order = 2; // 2 is always the order, first in file and skipping reserved #1 + } + return TypeFunPtr.make1((byte)2, true, targs, tret, _code.fidx(clzBare,order)); + } + + // A class type carries the constructor function as a required final field. + private TypeStruct classStruct( String typeName, TypeFunPtr init, boolean open ) { + return TypeStruct.make(addClzPrefix(typeName),open,Field.make(initFieldName(typeName),init,_code.alias(_ref._cname),true)); + } + + private static String initFieldName( String typeName ) { + if( startsClzPrefix(typeName) ) + typeName = typeName.substring(clzPrefix.length()); + int idx = typeName.lastIndexOf('.'); + return (idx == -1 ? typeName : typeName.substring(idx+1)).intern(); + } + + private TypeStruct latestStruct( TypeStruct ts ) { + Type t = TYPES.get(ts._name); + return t instanceof TypeStruct ts2 ? ts2 : ts; + } + + private 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,_code.alias(_ref._cname),xfinal); + TYPES.put(ts._name,ts = ts.add(fld)); + if( _ctorOpenStruct != null && _ctorOpenStruct._name == ts._name ) + _ctorOpenStruct = ts; + return fld; + } + + private Var defineOpenConstructorField( String name ) { + if( _ctorOpenStruct==null ) return null; + Field fld = fieldOrOpen(_ctorOpenStruct,name,true); + if( fld == null ) return null; + _scope.define(name,fld._t,fld._final,con(Type.TOP),loc()); + return _scope.lookup(name); } @@ -907,38 +1422,135 @@ public class Parser { // ref type position. // t = int|i8|i16|i32|i64|u8|u16|u32|u64|byte|bool | flt|f32|f64 | val | var | struct[?] + + // 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" + private Type type() { - int old1 = pos(); - boolean writable = match("!"); - boolean readonly = !writable && match("~"); // Only type with a leading `{` is a function pointer... if( peek('{') ) return typeFunPtr(); // Otherwise you get a type name + int old1 = pos(); + boolean writable = match("!"); + boolean readonly = !writable && match("~"); String tname = _lexer.matchId(); if( tname==null ) return posT(old1); // Convert the type name to a type. - Type t0 = TYPES.get(tname); + Type t0 = TYPES.get(tname), t1 = t0; // No new types as keywords - if( t0 == null && KEYWORDS.contains(tname) ) - return posT(old1); - if( t0 == Type.BOTTOM || t0 == Type.TOP ) return t0; // var/val type inference + if( KEYWORDS.contains(tname) ) { + if( t0 == null ) return posT(old1); + // Something like "int" or "f64" or "var". + // Can be "int[]" so still need to check array-ness + } else { + if( t0 == Type.BOTTOM || t0 == Type.TOP ) return t0; // var/val type inference + + if( t0 != null ) { + while( true ) { + int old2 = pos(); + if( !match(".") ) break; + String sname = matchId(); + if( sname==null ) { pos(old2); break; } + sname = tname+"."+sname; + Type t = TYPES.get(sname); + if( t==null ) { pos(old2); break; } + tname = sname; + t0 = t; + } + } else { + // Type A.B.C starts with just A. Search our nested type path, + // e.g. path "X.Y.Z", in order: + + // If A==X its now a local type. + // If another dot, repeat for B==Y then C==Z + // Else if AX.B exists, done + // Else AX.B is a local forward ref. + // + // Else its a short cut form, one of: + // X.Y.Z.A + // X.Y.A + // X.A + // Else this all failed, assume a forward ref with A as an external symbol: + // A + + String root = _nestedType; + int ridx = root.indexOf('.'); + if( ridx != -1 ) root = root.substring(0,ridx); + if( tname.equals(root) ) { + boolean localForward = false; + while( true ) { + int old2 = pos(); + if( !match(".") ) break; + String sname = matchId(); + if( sname==null ) { pos(old2); break; } + sname = tname+"."+sname; + Type t = TYPES.get(sname); + if( t==null && !(_nestedType.equals(tname) || _nestedType.startsWith(tname+".")) && !localForward ) { + pos(old2); + break; + } + tname = sname; + t0 = t; + localForward |= t==null; + } + } else { + String nest = _nestedType, fullq = tname; + while( true ) { + fullq = nest+"."+tname; // Full qualified name + t0 = TYPES.get(fullq); + if( t0 != null ) + { tname = fullq; break; } // Search succeeded + // Subtract a layer from nested typenames + int idx = nest.lastIndexOf('.'); + if( idx== -1 ) break; // Search failed; leave as an external symbol + nest = nest.substring(0,idx); + } + if( t0==null ) { + CompUnit cu = ParseAll.findCompUnit(_code,_ref,tname); + if( cu != null ) { + tname = cu._cname; + t0 = TYPES.get(tname); + } + while( true ) { + int old2 = pos(); + if( !match(".") ) break; + String sname = matchId(); + if( sname==null ) { pos(old2); break; } + tname = tname+"."+sname; + t0 = TYPES.get(tname); + } + } else { + while( true ) { + int old2 = pos(); + if( !match(".") ) break; + String sname = matchId(); + if( sname==null ) { pos(old2); break; } + sname = tname+"."+sname; + Type t = TYPES.get(sname); + if( t==null ) { pos(old2); break; } + tname = sname; + t0 = t; + } + } + } + } + + tname = tname.intern(); + // Still no type found? Assume forward reference + t1 = t0 == null + ? TypeStruct.forward(tname) // Null: assume a forward ref type + : t0; + } + + // Structs are always actually references + if( t1 instanceof TypeStruct ts1 ) + t1 = TypeMemPtr.make(ts1); - // Check for subtype. - while( true ) { - int old2 = pos(); - if( !match(".") ) break; - String sname = _lexer.matchId(); - if( sname==null ) { pos(old2); break; } - String tsname = tname+"."+sname; - t0 = TYPES.get(tsname); - if( t0==null ) { pos(old2); t0 = TYPES.get(tname); break; } - tname = tsname; - } - - // Still no type found? Assume forward reference - Type t1 = t0 == null ? TypeMemPtr.make(TypeStruct.open(tname)) :t0; // Null: assume a forward ref type // 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 ) { @@ -950,14 +1562,15 @@ public class Parser { Type t2 = t1; while( true ) { if( match("?") ) { - if( !(t2 instanceof TypeMemPtr tmp) ) + if( t2 instanceof TypeMemPtr tmp ) { + if( tmp.nullable() ) throw error("Type "+t2+" already allows null"); + t2 = tmp.makeNullable(); + } else throw error("Type "+t0+" cannot be null"); - if( tmp.nullable() ) throw error("Type "+t2+" already allows null"); - t2 = tmp.makeNullable(); } else if( match("[~]") ) { - t2 = typeAry(t2,true).makeRO(); + t2 = TypeMemPtr.make(typeAry(t2,true)).makeRO(); } else if( match("[]") ) { - t2 = typeAry(t2,false); + t2 = TypeMemPtr.make(typeAry(t2,false)); } else break; } @@ -969,27 +1582,64 @@ public class Parser { int old2 = pos(); if( !match("!") ) match("~"); String id = _lexer.matchId(); - if( !(peek(',') || peek(';') || match("->")) || id==null ) + if( !(peek(',') || peek(';') || peek('=') || match("->")) || id==null ) return posT(old1); // Reset lexer to reparse pos(old2); // Reset lexer to reparse // Yes a forward ref, so declare it - TYPES.put(tname,((TypeMemPtr)t1).withAccess(false)); + forwardRefType(tname,(TypeStruct)((TypeMemPtr)t1)._obj); // Return the (array, final) type return t2; } - // Make an array type of t - private TypeMemPtr typeAry( Type t, boolean efinal ) { - if( t instanceof TypeMemPtr tmp && tmp.notNull() ) - throw error("Arrays of reference types must always be nullable"); - String tname = "[]"+t.str(); - TypeMemPtr ta = (TypeMemPtr)TYPES.get(tname); - if( ta==null ) - // Remember final version - TYPES.put(tname, ta = TypeMemPtr.make( TypeStruct.makeAry(tname,TypeInteger.U32,_code.getALIAS(),t,_code.getALIAS(),true) )); - // Reuse aliases, but preserve this occurrence's element permissions. - TypeStruct ary = ta._obj; - return TypeMemPtr.make(TypeStruct.makeAry(tname,TypeInteger.U32,ary._fields[0]._alias,t,ary._fields[1]._alias,efinal)); + private TypeMemPtr forwardRefType( String tname, TypeStruct tself ) { + TYPES.put(tname,tself); + String clzName = addClzPrefix( tname ); + TYPES.put(clzName, classStruct(tname,structInitSig(false,tself),true)); + return TypeMemPtr.make(tself); + } + + private TypeMemPtr forwardRefType( String tname ) { + tname = fullTypeName(tname); + return forwardRefType(tname,TypeStruct.forward(tname)); + } + + private String fullTypeName( String tname ) { + String nest = _nestedType, fullq; + while( true ) { + fullq = nest+"."+tname; + if( 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. + private 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 alloc(); trusted runtimes (notably argv construction) + // may fill the private array completely before publishing it. + String tname = ("[]"+t.str()).intern(); + TypeStruct ta = (TypeStruct)TYPES.get(tname); + if( ta==null ) { + // Primitive arrays use the null compunit + String rcname = TYPES.get(t) instanceof TypeStruct ? _ref._cname : ("_."+t).intern(); + ta = TypeStruct.makeAry(tname,TypeInteger.U32,_code.alias(rcname),t,_code.alias(rcname), false ); + 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 ); + } + + private Type implicitSelfType() { + TypeStruct self = _scope.constructorSelf(); + // Ordinary instance methods accept the declared object shape. The + // constructor-only receiver starts at the low/default field values, + // and is built explicitly by constructorFunc(). + return self == null ? TypePtr.PTR : TypeMemPtr.make(self); } // A function type is `{ type... -> type }` or `{ type }`. @@ -998,16 +1648,19 @@ public class Parser { match("{"); // Skip already-peeked '{' Type t0 = type(); // Either return or first arg if( t0==null ) return posT(old); // Not a function - if( match("}") ) // No-arg function { -> type } - return TypeFunPtr.make(match("?"),false,TypeFunPtr.TEMPTY,t0); Ary ts = new Ary<>(Type.class); + // Always reserve a receiver slot. Outside constructor scopes it is + // broad and unused, so call sites can uniformly pass their self. + ts.push(implicitSelfType()); + if( match("}") ) // No-arg function { -> type } + return TypeFunPtr.make(match("?"),ts.asAry(),t0); ts.push(t0); // First argument while( true ) { if( match("->") ) { // End of arguments, parse return Type ret = type(); if( ret==null || !match("}") ) return posT(old); // Not a function - return TypeFunPtr.make(match("?"),false,ts.asAry(),ret); + return TypeFunPtr.make(match("?"),ts.asAry(),ret); } Type t1 = type(); if( t1==null ) return posT(old); // Not a function @@ -1083,7 +1736,7 @@ public class Parser { else if( !match("!=") ) break; lhs.keep(); Node rhs = parseComparison(); - lhs = peep(new BoolNode.EQ(lhs.unkeep(),rhs).widen()); + lhs = peep(new BoolNode.EQ(lhs.unkeep(),rhs)); if( !eq ) lhs = peep(new NotNode(lhs)); } return lhs; @@ -1100,46 +1753,64 @@ public class Parser { */ private Node parseComparison() { Node lhs = parseShift(); - int dir = 0; + int dir = parseCompDir(); + // No compare + if( dir==0 ) return lhs; + lhs.keep(); - while( true ) { - int dir0; - if( false ) ; - else if( match("<=" ) ) dir0 = -1; - else if( match(">=" ) ) dir0 = -2; - else if( match("<" ) ) dir0 = 1; - else if( match(">" ) ) dir0 = 2; - else break; - lhs.keep(); - // Check and record direction - if( dir==0 ) { - dir = Math.abs(dir0); - Node rhs = parseShift(); - lhs = makeCompBool(dir0,lhs.unkeep(),rhs); // Convert to a bool - } else if( dir == Math.abs(dir0) ) { - // e0 < lhs < ??? - Node ifNode = new IfNode(ctrl(), lhs).peephole(); - Node ifT = new CProjNode(ifNode. keep(), 0, "True" ).peephole(); - Node ifF = new CProjNode(ifNode.unkeep(), 1, "False").peephole(); - // False side does nothing - ScopeNode fScope = _scope.dup(); - fScope.ctrl(ifF); - // True side executes next part of range - ctrl(ifT); - _scope.addGuards(ifT,lhs,false); - Node rhs = parseShift(); - _scope.removeGuards(ifT); // TODO: I think should remain true as long as possible - Node next = makeCompBool(dir0, lhs, rhs).keep(); - // Merge result - RegionNode r = ctrl(_scope.mergeScopes(fScope, loc())); - assert next._type.meet(lhs._type).isa( TypeInteger.BOOL ); - lhs = peep(new PhiNode("",TypeInteger.BOOL,r,next.unkeep(),lhs.unkeep())); - r.peephole(); - } else { - throw error("Mixing relational directions in a chained relational test"); - } + // Compare + Node rhs = parseShift().keep(); + Node cmp = makeCompBool(dir,lhs.unkeep(),rhs).keep(); // Convert to a bool + + // Stacked compares? + int dir0 = parseCompDir(); + if( dir0 == 0 ) { + rhs.unkill(); + return cmp.unkeep(); } - return lhs; + + // rhs is keeped() and becomes lhs + // cmp is NOT keeped() and is the last test + Node ifNode = new IfNode(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 = _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 error("Mixing relational directions in a chained relational test"); + // True side parses next arm of test + ctrl(ifT.unkeep()); + lhs = rhs; // lhs is keeped() and is old RHS + rhs = parseShift().keep(); + cmp = makeCompBool(dir,lhs.unkeep(),rhs); // Convert to a bool + ifNode = new IfNode(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 + ctrl(ifF); + fail.mergeScopes(_scope.dup(), loc()).peephole(); + // Check next stacked compare + dir0 = parseCompDir(); + } + rhs.unkill(); + ctrl(ifT.unkeep()); + RegionNode r = fail.mergeScopes(_scope, loc()).init(); + _scope = fail; + return new PhiNode("", r,_code.ZERO,con(1)).peephole(); + } + + private int parseCompDir() { + if( match("<=") ) return -1; // Negative for "equals-or-less" + if( match(">=") ) return -2; // 1 for <, 2 for > + if( match("<" ) ) return 1; // Positive for just "less" + if( match(">" ) ) return 2; + return 0; } private Node makeCompBool( int dir0, Node lhs, Node rhs ) { @@ -1147,10 +1818,9 @@ public class Parser { if( Math.abs(dir0)==2 ) // Swap direction { Node tmp = lhs; lhs = rhs; rhs = tmp; } lhs = peep(dir0 < 0 ? new BoolNode.LE(lhs,rhs) : new BoolNode.LT(lhs,rhs)); - return peep(lhs.widen()); + return peep(lhs); } - /** * Parse an additive expression * @@ -1171,7 +1841,7 @@ public class Parser { ParseException err; if( (err=lhs.err()) != null ) throw err; - lhs = peep(lhs.widen()); + lhs = peep(lhs); } return lhs; } @@ -1192,7 +1862,7 @@ public class Parser { else if( match("-") ) lhs = new SubNode(lhs,null); else break; lhs.setDef(2,parseMultiplication()); - lhs = peep(lhs.widen()); + lhs = peep(lhs); } return lhs; } @@ -1213,7 +1883,7 @@ public class Parser { else if( match("/") ) lhs = new DivNode(lhs,null); else break; lhs.setDef(2,parseUnary()); - lhs = peep(lhs.widen()); + lhs = peep(lhs); } return lhs; } @@ -1230,16 +1900,16 @@ public class Parser { // Pre-dec/pre-inc int old = pos(); if( match("--") || match("++") ) { - int delta = _lexer.peek(-1)=='+' ? 1 : -1; // Pre vs post + int delta = _lexer.peek(-1)=='+' ? 1 : -1; // Inc vs Dec String name = _lexer.matchId(); if( name!=null ) { Var n = _scope.lookup(name); if( n != null && !(n.type() instanceof TypeMemPtr) ) { + if( n._extern!=0 ) + return parsePostfixName(_scope.in(n),name,delta); if( n._final ) throw error("Cannot reassign final '"+n._name+"'"); - Node expr = n.type() instanceof TypeFloat - ? peep(new AddFNode(_scope.in(n),con(TypeFloat.constant(delta)))) - : zsMask(peep(new AddNode(_scope.in(n),con(delta))),n.type()); + Node expr = zsMask(peep(new AddNode(_scope.in(n),con(delta))),n.type()); _scope.update(n,expr); return expr; } @@ -1247,7 +1917,7 @@ public class Parser { // Reset, try again pos(old); } - if (match("-")) return peep(new MinusNode(parseUnary()).widen()); + if (match("-")) return peep(new MinusNode(parseUnary())); if (match("!")) return peep(new NotNode(parseUnary())); // Else be a primary expression return parsePrimary(); @@ -1259,71 +1929,118 @@ public class Parser { * 
      *     primaryExpr : integerLiteral | "string" | 'char' | true | false | null |
      *                   new Type | '(' expression ')' | Id['++','--'] |
-     *                   [static.]* Id
+     *                   type['.' Id]*
      *
* @return a primary {@link Node}, never {@code null} */ private Node parsePrimary() { if( _lexer.isNumber(_lexer.peek()) ) return parseLiteral(); - if( _lexer.peek('"') ) return newString(parseString()); + if( _lexer.peek('"') ) return parsePostfix(newString(parseString())); if( matchx("true" ) ) return con(1); - if( matchx("false") ) return ZERO; - if( matchx("null" ) ) return NIL; + if( matchx("false") ) return _code.ZERO; + if( matchx("null" ) ) return con(Type.NIL); if( match ("'" ) ) return parseChar(); if( match ("(" ) ) return parsePostfix(require(parseAsgn(), ")")); if( matchx("new" ) ) return parsePostfix(alloc()); if( match ("{" ) ) return parsePostfix(require(func(),"}")); - // Parse static variable lookup: `type.fld` in the type namespace - // CNC: not a full type parse, just a typename parse int pos = pos(); - Type t = type(); - if( t!=null ) { - if( peek('.') ) - // A namespace lookup is not a reference declaration. - return parsePostfix(con(TYPES.get(((TypeMemPtr)t)._obj._name))); - //pos(pos); // TODO: not a `type.fld` - //return null; - throw Utils.TODO(); - } - // Expect an identifier now - - // - if null, make fref, normal var handling - // - if final constant, normal var handling - // - if method var, scan skipping blocks & methods, must hit correct struct no fcns - // - if normal var, scan skipping blocks, allowing last fcn - // - NO fcns nested in methods, NO methods nested in fcns - String id = _lexer.matchId(); if( id == null || KEYWORDS.contains(id) ) throw errorSyntax("an identifier or expression"); + int pos2 = pos(); + // Attempt a local var lookup first Var var = _scope.lookup(id); - if( var==null ) { - // If missing, assume a forward reference - _scope.define(id, FRefNode.FREF_TYPE, true, XCTRL, loc()); - var = _scope.lookup(id); - } + // Not a local var, try again as a type name + pos(pos); + Type t = type(); + if( t!=null ) { + // Static typename lookup + if( peek('.') ) // type.fld, which is really a field lookup in the class object + return parsePostfix(con(t)); + // Direct reference to a type. Convert the instance + // type to a class type name + if( !(t instanceof TypeMemPtr tmp) ) { + //return new FRefNode(addClzPrefix(tmp._obj._name), loc()).peephole(); + // Not a local var, but yes a bare type... disallow a local + // FREF and return null, not-a-primary parse. + pos(pos); + return null; + } + } - // If a method var, allow nested blocks and methods, but not fcns or other structs. - // Else safety check for accessing fields out of function scope. - if( instance(var) ) { - Node self = _scope.in(_scope.lookup("self")); // Insert self reference - return parsePostfixName(self,id); + // Insert FREF outside enclosing Kind.Func scope. + pos(pos2); + t = FRefNode.FREF_TYPE; + // Check if this is a class. + CompUnit cu = ParseAll.findCompUnit(_code,_ref,id); + if( cu!=null ) { + // Must be a final class-type + String clzName = addClzPrefix(cu._cname); + TypeStruct clz = (TypeStruct)TYPES.get(clzName); + if( clz == null ) + TYPES.put(clzName,clz = TypeStruct.make(clzName,true)); + t = TypeMemPtr.make((byte)2,clz,true); + } + // Define the FRef + var = _scope.defineFRef(id,t,true,loc()); + _frefs.push((FRefNode)_scope.in(var)); } // Load local value Node rvalue = _scope.in(var); - if( rvalue._type == Type.BOTTOM ) - if( rvalue instanceof FRefNode ) - return parsePostfix(rvalue); - else throw error("Cannot read uninitialized field '"+id+"'"); + if( var._extern!=0 ) + return parsePostfixName(rvalue,id,0); + if( var._fref ) + return parsePostfix(rvalue); + // Required constructor fields begin as their declared pointer type + // widened to include null. Inside the explicit constructor, any read + // before all paths replace that value observes a partially initialized + // object. Ordinary methods run only after construction is complete; + // their enclosing declaration scope still carries the same Var marker. + if( inExplicitConstructor() && var._uninit && rvalue._type instanceof TypeNil tn && tn.nullable() ) + throw error("Field '"+id+"' might not be initialized",var._loc); + + // Check for an instance field load + int kx = _scope.kindx(var); // Declaration scope + int fx = _scope.enclosingFunction(); // Enclosing function scope + Kind kk = _scope._kinds.at(kx); + Kind fk = _scope._kinds.at(fx); + // Access instance field from 'self' + if( kx+1 == fx && kk instanceof Kind.Func inst && FunNode.isInstance(inst._name) && fk instanceof Kind.Func method ) + return parsePostfixName(_scope.in(method._lexSize),id,0); + + // 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 && // 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 error("Variable '"+var._name+"' is out of function scope and must be a final constant"); + + // var.idx==2 is self argument, 3 is args, 4 or more are now static globals + if( var._idx >= 4 ) { + // Read from global scope. + // Surely a nicer way to get the top-level scope compile name? + Var clzptr = _scope.var( 2 ); + // Get the most recent sharpen global + TypeStruct clz = (TypeStruct) TYPES.get( ((TypeMemPtr) clzptr.type())._obj._name ); + TypeMemPtr clztmp = TypeMemPtr.make( (byte) 2, clz, true ); + return parsePostfixName( con( clztmp ), id,0 ); + //return parsePostfixName(_scope.in(2),id); + } + } // Check for assign-update, x += e0; char ch = _lexer.matchOperAssign(); - if( ch==0 ) // Normal primary, check for postfix updates - return parsePostfix(rvalue); + if( ch==0 ) { // Normal primary, check for postfix updates + int selfx = _scope.kindFcn(var)._lexSize; + // Might be a method call from inside a method, so no explicit "self". + // Pass the in-scope "self" + return parsePostfixMethod(rvalue,_scope.in(_scope.update(_scope.var(selfx),null))); + } // Assign-update direct into Scope if( var._final ) throw error("Cannot reassign final '"+var._name+"'"); @@ -1332,33 +2049,6 @@ public class Parser { return postfix(ch) ? rvalue.unkeep() : op; } - // true if instance variable lookup (var is in any number of nested blocks, - // then an instance function then inside a struct declaration). - private boolean instance(Var var ) { - // If a method var, allow nested blocks and methods, but not fcns or other structs - Kind kind = _scope.kind(var); - if( kind instanceof Kind.Define ) { - for( int i = _scope.depth()-1; i>=0 && var._idx < _scope._kinds.at(i)._lexSize; i-- ) { - Kind xkind = _scope._kinds.at(i); - if( xkind instanceof Kind.Block ) continue; - if( xkind instanceof Kind.Func ) { - if( _scope._kinds.at(i-1)==kind ) - return true; // Instance variable: lookup in a method in a decl - } - throw Utils.TODO(); - } - } else { - // If a normal var, allow any nested blocks, and a last fcn - - // but not functions further out (which involves capture). - Node def = _scope.in(var._idx); - for( int i = _scope.depth()-1; i>=0 && var._idx < _scope._kinds.at(i)._lexSize; i-- ) - if( _scope._kinds.at(i) instanceof Kind.Func && - !(def instanceof FRefNode) && !(var._final && def._type.isConstant()) ) - throw error("Variable '"+var._name+"' is out of function scope and must be a final constant"); - } - return false; - } - // 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. @@ -1381,17 +2071,17 @@ public class Parser { case '-' -> new SubNode(lhs,rhs); case '*' -> new MulNode(lhs,rhs); case '/' -> new DivNode(lhs,rhs); - case '&' -> new AndNode(loc(),lhs,rhs); - case '|' -> new OrNode(loc(),lhs,rhs); + case '|' -> new OrNode(null,lhs,rhs); + case '&' -> new AndNode(null,lhs,rhs); case '^' -> new XorNode(loc(),lhs,rhs); case Lexer.SHL -> new ShlNode(loc(),lhs,rhs); case Lexer.SAR -> new SarNode(loc(),lhs,rhs); case Lexer.SHR -> new ShrNode(loc(),lhs,rhs); - default -> throw Utils.TODO(); + default -> throw TODO(); }; // Convert to float ops, or narrow int types; error if not declared type. // Also, if postfix LHS is still keep() - return liftExpr(peep(op.widen()),t,true); + return convertExpr(peep(op),t); } @@ -1400,131 +2090,119 @@ public class Parser { */ private Node alloc() { Type t = type(); - if( t==null ) throw error("Expected a type"); + if( t==null ) { + String tname = _lexer.matchId(); + if( tname==null || KEYWORDS.contains(tname) ) + throw error("Expected a type"); + t = forwardRefType(tname); + } // Parse ary[ length_expr ] if( match("[") ) { if( !t.makeZero().isa(t) ) - throw error("Cannot allocate a non-nullable, since arrays always zero/null fill"); - Node len = parseAsgn(); - if( !(len._type instanceof TypeInteger) ) - throw error("Cannot allocate an array with length "+len._type); + throw error("Cannot allocate a non-nullable, since arrays are always zero/null filled"); + Node len = parseAsgn().keep(); require("]"); - TypeMemPtr tmp = typeAry(t,false); - return newArray(tmp._obj,len); - } - - if( !(t instanceof TypeMemPtr tmp) ) - throw error("Cannot allocate a "+t.str()); - - // Parse new struct { default_initialization } - StructNode s = INITS.get(tmp._obj._name); - if( s==null ) throw error("Unknown struct type '" + tmp._obj._name + "'"); - - Field[] fs = s._ts._fields; - // if the object is fully initialized, we can skip a block here. - // Check for constructor block: - boolean hasConstructor = match("{"); - Ary init=s._inputs; int idx=0; - if( hasConstructor ) { - idx = _scope.nIns(); - // Push a scope, and pre-assign all struct fields. - _scope.push(new Kind.Block()); - Lexer loc = loc(); - for( int i=0; i 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 ? fullTypeName(ts._name) : ts._name; + Type resolved = TYPES.get(typeName); + if( resolved instanceof TypeStruct rts ) ts = rts; + TypeStruct clz = (TypeStruct)TYPES.get(addClzPrefix(typeName)); + if( clz==null ) + throw error("Unknown struct type '" + ts._name + "'"); + Field afld = clz.field(""); + Node alloc; + if( afld != null ) { + TypeFunPtr tfp = (TypeFunPtr)afld._t; + FunNode fun = _code.link(tfp); + alloc = fun==null + ? new FRefNode((addClzPrefix(typeName)+".").intern(),loc()) + : new FunPtrNode(tfp,_code._start,fun.ret()).peephole(); + } else { + if( !ts._fref ) + throw error("Constructor arguments for '" + ts._name + "' but no constructor is defined"); + Type[] sig = new Type[ctorArgs._len]; + for( int i=0; i").intern(),loc(), + TypeFunPtr.make(false,sig,TypeMemPtr.make(ts))); + } + Ary args = new Ary<>(Node.class); + args.add(ctrl()); args.add(mem()); + for( Node arg : ctorArgs ) args.add(arg.unkeep()); + args.add(alloc); + return functionCall(args); + } + + private Ary constructorArgs() { + Ary args = new Ary<>(Node.class); + if( !match("(") ) + return args; + while( !peek(')') ) { + Node arg = parseAsgn(); + if( arg==null ) break; + args.push(arg.keep()); + if( !match(",") ) break; + } + require(")"); + return args; } + private Node allocArray(TypeStruct ts, Node len) { + Field lenFld = ts.field("#" ); + Field bodyFld = ts.field("[]"); - /** - * Return a NewNode initialized memory. - * @param obj is the declared type, with GLB fields - * @param init is a collection of initialized fields - */ - private Node newStruct( TypeStruct obj, Node size, int idx, Ary init ) { - Field[] fs = obj._fields; - if( fs==null ) - throw error("Unknown struct type '" + obj._name + "'"); - Node prior = mem().keep(); - MemMergeNode input = new MemMergeNode((Node)null); - for( Field f : fs ) if( !f._one ) input.alias(f._alias,prior); - // Allocation zeroes its fields; nonzero initializers become explicit Stores. - Node[] ns = new Node[3]; - ns[0] = ctrl(); - ns[1] = input.peephole(); - ns[2] = size; - Node nnn = new NewNode(TypeMemPtr.make(obj),ns).peephole().keep(); - Node ptr = new ProjNode(nnn,0,obj._name).peephole().keep(); - Node out = new ProjNode(nnn,1,"$mem").peephole().keep(); - MemMergeNode after = new MemMergeNode(prior); - for( Field f : fs ) if( !f._one ) after.alias(f._alias,out); - mem(after.peephole()); - out.unkeep(); - nnn.unkeep(); - prior.unkill(); - for( int i=0; i ALTMP = new Ary<>(Node.class); - private Node newArray(TypeStruct ary, Node len) { - ConFldOffNode base = off(ary, "[]"); - int scale= ary.aryScale(); - Node size = peep(new AddNode(base,peep(new ShlNode(null,len.keep(),con(scale))))); - ALTMP.clear(); ALTMP.add(len.unkeep()); ALTMP.add(con(ary._fields[1]._t.makeZero())); - return newStruct(ary,size,0,ALTMP); + // TODO: Allow add-on "constructor" to init the array elements + + Node prior = mem(); + Node esc = peep(new EscapeNode(lenFld,self,st,prior)); + mem(mergeAlias(prior,lenFld._alias,esc)); + prior = mem(); + esc = peep(new EscapeNode(bodyFld,self,smem,prior)); + mem(mergeAlias(prior,bodyFld._alias,esc)); + smem.unkeep(); + return self.unkeep(); } + private Node newString(String s) { - TypeMemPtr tmp = typeAry(TypeInteger.U8,true); - int lenAlias = tmp._obj.field("#" )._alias; - int elemAlias = tmp._obj.field("[]")._alias; - TypeConAryB con = TypeConAryB.make(s); - Type elem = con.elem(); + TypeStruct ts = typeAry(TypeInteger.U8,true); + int lenAlias = ts.field("#" )._alias; + int elemAlias = ts.field("[]")._alias; + TypeConAryB body = TypeConAryB.make(s); + TypeInteger slen = TypeInteger.constant(s.length()); // Make a TMP, not-null (byte)2, singleton (true) (requires text // strings are hash-interned), with a TypeStruct having a constant // array body. - TypeMemPtr str = TypeMemPtr.make((byte)2,TypeStruct.makeAry("[]u8", TypeInteger.constant(s.length()), lenAlias, con, elemAlias, true),true); + TypeMemPtr str = TypeMemPtr.make((byte)2,TypeStruct.makeAry("[]u8", slen, lenAlias, body, elemAlias, true),true); assert str.isConstant(); return con(str.makeRO()); } - // Memory is one hidden SSA variable, including across branches and loops. - private Node mem() { return _scope.mem(); } - private void mem(Node n) { _scope.mem(n); } - - private void store(String name, int alias, Type glb, Node ptr, Node off, Node val, boolean init, Node ctrl) { - if( !init && ptr._type instanceof TypeMemPtr view && view._ro && ctrl()._type!=Type.XCONTROL ) - throw error("Cannot modify final field '"+name+"'"); - Node prior = mem().keep(); - Node st = new StoreNode(loc(),name,alias,glb,prior,ptr,off,val,init); - st.setDef(0,ctrl); - st = st.peephole(); - mem(new MemMergeNode(prior,alias,st).peephole()); - prior.unkill(); - } - /** * Parse postfix expression; this can be a field expression, an array * lookup or a postfix operator like '#' @@ -1537,15 +2215,33 @@ public class Parser { * expr '(' [args,]* ')' // Function call * */ + private 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( match("(") ) { + expr = parsePostfix(require(functionCall(expr,self),")")); + } else if( expr != self ) + self.isKill(); // Not a method call, no need for self + return parsePostfix(expr); + } private Node parsePostfix(Node expr) { String name; if( match(".") ) name = requireId(); else if( match("#") ) name = "#"; else if( match("[") ) name = "[]"; - else if( match("(") ) return parsePostfix(require(functionCall(expr,null),")")); + // Can get here without an explicit receiver: "f()" or + // "self.method()(next)(next)(next)". Pass the current function self. + else if( match("(") ) return parsePostfix(require(functionCall(expr,defaultSelf()),")")); else return expr; // No postfix - return parsePostfixName(expr,name); + return parsePostfixName(expr,name,0); + } + + private Node defaultSelf() { + int selfx = _scope._kinds.at(_scope.enclosingFuncOrDecl())._lexSize; + return _scope.in(_scope.update(_scope.var(selfx),null)); } /** @@ -1558,87 +2254,111 @@ public class Parser { * expr ('[' expr ']')* [ [op]= expr ] // Array reference * */ - private Node parsePostfixName(Node expr, String name) { - - if( expr._type==Type.NIL ) - throw error("Accessing unknown field '" + name + "' from 'null'"); - - // Sanity check expr for being a reference - if( !(expr._type instanceof TypeMemPtr ptr) ) - throw error( "Expected "+(name=="#" || name=="[]" ? "array" : "reference")+" but found " + expr._type.str() ); - - // Find the field from the Type. Lookup in the base object field names. - TypeMemPtr ptr2 = (TypeMemPtr)TYPES.get(ptr._obj._name); - if( !ptr._obj.isAry() ) - ptr = ptr.makeFrom((TypeStruct)ptr._obj.join(ptr2._obj)); // Resolve the shape, retaining access. - TypeStruct base = ptr._obj; - int fidx = base.find(name); - if( fidx == -1 ) - throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); - - // Get field type and layout offset from base type and field index fidx - Field f = base._fields[fidx]; // Field from field index - Type tf = f._t; - if( tf instanceof TypeMemPtr ftmp && ftmp.isFRef() ) - tf = ftmp.makeFrom(((TypeMemPtr)(TYPES.get(ftmp._obj._name)))._obj); - if( base.isAry() && tf instanceof TypeConAry con ) - tf = con.elem(); + // pre is +/-1 for a prefix update, otherwise parse a postfix operation. + private Node parsePostfixName(Node expr, String name, int pre) { + // Keep expr across possible updates expr.keep(); + + // Get the best known TypeStruct from a pointer type. + TypeStruct ts = null, ts2; + if( expr._type instanceof TypeMemPtr tmp && (ts2=((TypeStruct)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 = 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 = 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 && !startsClzPrefix(ts._name) ) { + Type clz0 = TYPES.get(addClzPrefix(ts._name)); + if( clz0 instanceof TypeStruct clz && (fld = latestStruct(clz).field(name)) != null ) { + expr.unkeep(); + ts = latestStruct(clz); + expr = con(TypeMemPtr.make((byte)2,ts,true)).keep(); + } + } + if( fld==null && ts!=null ) + fld = fieldOrOpen(ts,name,false); + if( fld==null && ts!=null && !latestStruct(ts)._open ) + throw error("Accessing unknown field '"+name+"' from '*"+ts._name+"'"); + // 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.equals("[]") // If field is an array body - // Array index math - ? peep(new AddNode(off(base,"[]"),peep(new ShlNode(null,require(parseAsgn(),"]"),con(base.aryScale()))))) - // Struct field offsets are hardwired - : off(base,name)).keep(); + Node off = (name=="[]" + // Array element math, with unknown base offset and shift amount. + ? peep(new AddNode(fldoff(expr,"[]"),peep(new ShlNode(null,require(parseAsgn(),"]"),fldoff(expr,"<<"))))) + // Named field offset on an unknown struct type + : fldoff(expr,name)).keep(); // Disambiguate "obj.fld==x" boolean test from "obj.fld=x" field assignment - if( matchOpx('=','=') ) { + if( pre==0 && matchOpx('=','=') ) { + // Field assignment Node val = parseAsgn().keep(); - Node lift = liftExpr( val, tf, false ); + // Lift value for store + Node lift = fld==null ? val : new ConvertNode(fld._t,val).peephole(); + // Memory for store, post assignment expression + Node mem = mem(); + // Store to field + mem.keep(); + if( expr._type instanceof TypeMemPtr view && view._ro && ctrl()._type!=Type.XCONTROL ) + throw error("Cannot modify final field '"+name+"'"); + Node st = new StoreNode(loc(), name, alias, decl, ctrl(), mem, expr.unkeep(), off.unkeep(), lift, false).peephole().keep(); + storeMem(st,alias,mem); + st.unkeep(); + mem.unkeep(); - store(name,f._alias,tf,expr.unkeep(),off.unkeep(),lift,false,base.isAry() ? ctrl() : null); return val.unkeep(); // "obj.a = expr" returns the expression while updating memory } + // Memory for load + Node mem = mem(); + // Loading from a constant array, the declared type is the + // meet-over-elements and not the array itself. + if( name=="[]" && decl instanceof TypeConAry conary ) + decl = conary.elem(); + // Load field - Node load = f._one && INITS.containsKey( base._name ) - ? INITS.get(base._name).in(base.find(name)) - : new LoadNode(loc(),name, f._alias, tf, mem(), expr, off); - // Arrays include control, as a proxy for a safety range check - // Structs don't need this; they only need a NPE check which is - // done via the type system. - if( base.isAry() && !name.equals("#") ) load.setDef(0,ctrl()); - load = peep(load); + Node load = peep(new LoadNode(loc(),name, alias, ctrl(), mem, expr, off)); // Check for assign-update, "ptr.fld += expr" or "ary[idx]++" - char ch = _lexer.matchOperAssign(); + char ch = pre==0 ? _lexer.matchOperAssign() : (char)pre; if( ch!=0 ) { - Node op = opAssign(ch,load,tf); - store(name,f._alias,tf,expr.unkeep(),off.unkeep(),op,false,base.isAry() ? ctrl() : null); - load = postfix(ch) ? load.unkeep() : op; - // And use the original loaded value as the result - return load; - //throw Utils.TODO(); // NO POSTFIX AFTER STORE, JUST RETURN - } else { - off.unkill(); - // Method call: Loaded a function from a named field, AND the base - // field type is final. - if( load._type instanceof TypeFunPtr && name!="[]" && - !(load instanceof ExternNode) && - ((TypeMemPtr)TYPES.get(base._name))._obj.field(name)._final && - // And calling a function - match("(") ) { - return parsePostfix(require(functionCall(load,expr),")")); - } + if( fld!=null && decl==Type.BOTTOM ) + throw error( "'" + ts._name + "' is not fully initialized, field '" + fld._fname + "' needs to be set in a constructor" ); + Node op = opAssign(ch,load, decl ).keep(); + mem.keep(); + if( expr._type instanceof TypeMemPtr view && view._ro && ctrl()._type!=Type.XCONTROL ) + throw error("Cannot modify final field '"+name+"'"); + Node st = new StoreNode(loc(), name, alias, decl, ctrl(), mem, expr.unkeep(), off.unkeep(), op, false).peephole().keep(); + storeMem(st,alias,mem); + st.unkeep(); + mem.unkeep(); - // Drop expr, keeping load alive - load.keep(); - expr.unkill(); - load.unkeep(); + op.unkeep(); // A narrow Store may have folded away the expression's conversion. + if( postfix(ch) ) load.unkeep(); + return pre==0 && postfix(ch) ? load : op; } - - return parsePostfix(load); + off.unkill(); + // Might be a method call, so pass expr as 'self' + return parsePostfixMethod(load,expr.unkeep()); } @@ -1675,15 +2395,9 @@ public class Parser { Ary ts = new Ary<>(Type.class); Ary ids = new Ary<>(String.class); java.util.BitSet finals = new java.util.BitSet(); - - // Defined in constructor? Add `self` argument. "static" calls still - // add a `self` they just ignore it. - if( _scope._kinds.last() instanceof Kind.Define define ) { - // Upgrade defined struct to latest fields - TypeMemPtr tmp = (TypeMemPtr)TYPES.get(define._tmp._obj._name); - ts .push(tmp); - ids.push("self"); - } + Type self = implicitSelfType(); + ts.push(self); + ids.push(self == TypePtr.PTR ? "#self" : "self"); // Parse other arguments _lexer.skipWhiteSpace(); @@ -1699,9 +2413,44 @@ public class Parser { } require("->"); // Make a concrete function type, with a fidx - TypeFunPtr tfp = _code.makeFun(TypeFunPtr.make(false,false,ts.asAry(),Type.BOTTOM)); + TypeFunPtr tfp = TypeFunPtr.make1((byte)2,true,ts.asAry(),Type.BOTTOM,_code.fidx(_ref._cname)); ReturnNode ret = parseFunctionBody(tfp,loc,finals,ids.asAry()); - return new FunPtrNode(ret._fun.sig(),ret).peephole(); + return new FunPtrNode(tfp,_code._start,ret).peephole(); + } + + private Node constructorFunc(String name) { + require("{"); + Ary ts = new Ary<>(Type.class); + Ary ids = new Ary<>(String.class); + java.util.BitSet finals = new java.util.BitSet(); + TypeStruct self = _scope.constructorSelf(); + assert self != null; + ts.push(TypeMemPtr.make(constructorRecv(self))); + ids.push("self"); + // Explicit constructors use the same hidden allocation arguments as + // : public memory is the call memory edge (index 1), followed by + // self (index 2) and the private, unescaped object memory (index 3). + ts.push(TypeMem.makePrivate(self)); + ids.push("#selfMem"); + + _lexer.skipWhiteSpace(); + Lexer loc = loc(); + while( true ) { + Type t = type(); + if( t==null ) break; + finals.set(ids.size(),bindingFinal(t)); + String id = requireId(); + ts .push(t ); + ids.push(id); + match(","); + } + require("->"); + TypeFunPtr tfp = TypeFunPtr.make1((byte)2,true,ts.asAry(),TypeMem.makePrivate(self),_code.fidx(_ref._cname)); + Node[] preParse = _scope.save(); + ReturnNode ret = _parseFunctionBody((self._name+"."+name).intern(),tfp,loc,finals,ids.asAry()); + _scope.restore(preParse); + require("}"); + return new FunPtrNode(tfp,_code._start,ret).peephole(); } /** @@ -1713,15 +2462,13 @@ public class Parser { private Node functionCall(Node fcn, Node self) { if( fcn._type == Type.NIL ) throw error("Calling a null function pointer"); - if( !(fcn instanceof FRefNode) && !fcn._type.isa(TypeFunPtr.BOT) ) - throw error("Expected a function but got "+fcn._type.glb(false).str()); fcn.keep(); // Keep while parsing args Ary args = new Ary<>( Node.class ); args.push(null); // Space for ctrl,mem args.push(null); if( self != null ) // Method call has a self - args.push(self); + args.push(self.keep()); while( !peek(')') ) { Node arg = parseAsgn(); if( arg==null ) break; @@ -1730,11 +2477,15 @@ public class Parser { } // Control & memory after parsing args args.set(0,ctrl().keep()); - args.set(1,_scope.mem().keep()); + args.set(1,mem().keep()); args.push(fcn); // Function pointer // Unkeep them all for( Node arg : args ) arg.unkeep(); + return functionCall(args); + } + + private Node functionCall( Ary args ) { // Dead into the call? Skip all the node gen if( ctrl()._type == Type.XCONTROL ) { for( Node arg : args ) @@ -1746,14 +2497,16 @@ public class Parser { // Into the call CallNode call = (CallNode)new CallNode(loc(), args.asAry()).peephole(); // Post-call setup - CallEndNode cend = (CallEndNode)new CallEndNode(call).peephole(); + CallEndNode cend = (CallEndNode)new CallEndNode(call,TypeRPC.constant(_code.rpc(_ref._cname))).peephole(); call.peephole(); // Rerun peeps after CallEnd, allows early inlining + cend = (CallEndNode)cend.keep().peephole(); // TODO: Might inline // Control from CallEnd ctrl(new CProjNode(cend,0,ScopeNode.CTRL).peephole()); - // A call may update any alias, so its memory result is the new whole state. - _scope.mem(new ProjNode(cend,1,ScopeNode.MEM0).peephole()); + // Memory from CallEnd + Node mem = new ProjNode(cend,1,ScopeNode.MEM0).peephole(); + mem(mem); // Call result - return new ProjNode(cend,2,"#2").peephole(); + return new ProjNode(cend.unkeep(),2,"#2").peephole(); } // Just after parsing "type foo = " can parse `"C"` @@ -1765,10 +2518,27 @@ public class Parser { return false; } // External linked constant - private Node externDecl( String ex, Type t ) { - if( t instanceof TypeFunPtr tfp ) // Generic TFP from type parse - t = _code.makeFun(tfp); // Get a FIDX, becomes a constant - return new ExternNode(t,ex).peephole(); + private ConstantNode externDecl( String ex, Type t ) { + if( t instanceof TypeFunPtr tfp ) { // Generic TFP from type parse + int fidx = _code.fidx(_ref._cname); // Get a FIDX + tfp = tfp.makeFrom(fidx); // Become a constant + _code.externFunc(fidx,ex); // Map fidx to extern name + t = tfp; + } + return (ExternNode)(new ExternNode(t,ex).peephole()); + } + + // A lexical C binding has a singleton namespace with one external field. + // The namespace occupies no storage; its field offset supplies the address. + private Node externData(String name, Type t) { + if( !(t instanceof TypeInteger) && !(t instanceof TypeFloat) ) + throw error("C data binding requires an integer or float type"); + String cname = ("C:"+name).intern(); + TypeStruct ts = TypeStruct.make(cname,false,Field.make(name,t,_code.externAlias(name),false,true)); + Type old = TYPES.putIfAbsent(cname,ts); + if( old!=null && old!=ts ) + throw error("Conflicting types for C data '"+name+"'"); + return con(TypeMemPtr.make((byte)2,ts,true)); } /** @@ -1776,13 +2546,20 @@ public class Parser { * * 
      *     integerLiteral: [1-9][0-9]* | [0]
-     *     floatLiteral: [digits].[digits]?[e [digits]]?
+     *     floatLiteral: [digits].[digits]?[e [digits]]?[f]?
      *
*/ private ConstantNode parseLiteral() { return con(_lexer.parseNumber()); } - public static Node con( long con ) { return con==0 ? ZERO : con(TypeInteger.constant(con)); } - public static ConstantNode con( Type t ) { return (ConstantNode)new ConstantNode(t).peephole(); } - public static ConFldOffNode off( TypeStruct base, String fname ) { return (ConFldOffNode)(new ConFldOffNode(base._name,fname).peephole()); } + ConstantNode con( long con ) { return _code.con(con); } + ConstantNode con( Type t ) { return _code.con(t ); } + // Field offset for a known type (but unknown offset) + public static ConFldOffNode off( TypeStruct ts, String fname ) { + return (ConFldOffNode)(new ConFldOffNode(ts,fname).peephole()); + } + // Field offset for an unknown type + public Node fldoff( Node n, String name ) { + return new FldOffNode(n,name,loc()).peephole(); + } public Node peep( Node n ) { // Peephole, then improve with lexically scoped guards return _scope.upcastGuard(n.peephole()); @@ -1832,6 +2609,14 @@ public class Parser { return require(con(TypeInteger.constant(c)),"'"); } + private boolean noLowerCase(String s) { + for( int i=0; i 0 ) { if( len > 1 && _input[old]=='0' ) throw error("Syntax error: integer values cannot start with '0'",this); long i = Long.parseLong(new String(_input,old,len)); return TypeInteger.constant(i); } - return TypeFloat.constant(Double.parseDouble(new String(_input,old,-len))); + return TypeFloat.constant(Double.parseDouble(new String(_input,old,n))); } private String parseNumberString() { int old = _position; int len = Math.abs(isLongOrDouble()); + if( peek()=='f' ) { + nextChar(); + len++; + } return new String(_input,old,len); } @@ -2104,7 +2903,7 @@ public class Parser { private String parseId() { int start = _position; while (isIdLetter(nextChar())) ; - return new String(_input, start, --_position - start); + return new String(_input, start, --_position - start).intern(); } // @@ -2139,9 +2938,9 @@ public class Parser { } } - ParseException errorSyntax(String syntax) { return _errorSyntax("expected "+syntax); } + ParseException errorSyntax(String syntax) { return _errorSyntax("expected `"+syntax+"`"); } private ParseException _errorSyntax(String msg) { - return error("Syntax error, "+msg+": " + _lexer.getAnyNextToken()); + return error("Syntax error, "+msg+" but found `" + _lexer.getAnyNextToken()+"`"); } ParseException error(String msg) { return error(msg,_lexer); } public static ParseException error(String msg, Lexer loc) { return new ParseException(msg,loc); } -- cgit v1.2.3