From f66ab11456244b12c48ee9231cec5c8b54b47efe Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Mon, 10 Aug 2026 11:11:18 -0700 Subject: Chapter 29: Tech Debt Cleanup 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/IterPeeps.java | 351 --- src/main/java/com/seaofnodes/simple/Parser.java | 3197 -------------------- src/main/java/com/seaofnodes/simple/README.md | 15 + src/main/java/com/seaofnodes/simple/Var.java | 54 - .../simple/codegen/ClassInitDependencies.java | 9 +- .../com/seaofnodes/simple/codegen/CodeGen.java | 3 +- .../com/seaofnodes/simple/codegen/CompUnit.java | 2 +- .../com/seaofnodes/simple/codegen/Encoding.java | 2 +- .../simple/codegen/GlobalCodeMotion.java | 2 +- .../com/seaofnodes/simple/codegen/IterPeeps.java | 349 +++ .../seaofnodes/simple/codegen/ListScheduler.java | 2 +- .../java/com/seaofnodes/simple/codegen/Opto.java | 2 +- .../com/seaofnodes/simple/codegen/ParseAll.java | 3 +- .../com/seaofnodes/simple/codegen/Serialize.java | 2 +- .../com/seaofnodes/simple/codegen/StaticData.java | 2 +- .../com/seaofnodes/simple/codegen/TypeCheck.java | 2 +- .../java/com/seaofnodes/simple/node/AndNode.java | 5 +- .../java/com/seaofnodes/simple/node/ArithNode.java | 11 +- .../java/com/seaofnodes/simple/node/BoolNode.java | 2 +- .../java/com/seaofnodes/simple/node/CFGNode.java | 1 + .../com/seaofnodes/simple/node/CLInitNode.java | 13 +- .../com/seaofnodes/simple/node/CallEndNode.java | 2 +- .../java/com/seaofnodes/simple/node/CallNode.java | 13 +- .../com/seaofnodes/simple/node/ConFldOffNode.java | 2 +- .../com/seaofnodes/simple/node/ConvertNode.java | 2 +- .../java/com/seaofnodes/simple/node/CtrlNode.java | 2 +- .../java/com/seaofnodes/simple/node/FRefNode.java | 11 +- .../com/seaofnodes/simple/node/FldOffNode.java | 7 +- .../java/com/seaofnodes/simple/node/FunNode.java | 7 +- .../java/com/seaofnodes/simple/node/LoadNode.java | 5 +- .../java/com/seaofnodes/simple/node/LoopNode.java | 5 +- .../com/seaofnodes/simple/node/MemMergeNode.java | 1 + .../java/com/seaofnodes/simple/node/MemOpNode.java | 9 +- .../java/com/seaofnodes/simple/node/MinusNode.java | 2 +- .../java/com/seaofnodes/simple/node/NeverNode.java | 2 +- .../java/com/seaofnodes/simple/node/NewNode.java | 2 +- src/main/java/com/seaofnodes/simple/node/Node.java | 4 +- .../java/com/seaofnodes/simple/node/OrNode.java | 5 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 1 + .../com/seaofnodes/simple/node/PtrToIntNode.java | 2 +- .../com/seaofnodes/simple/node/RegionNode.java | 9 +- .../com/seaofnodes/simple/node/ReturnNode.java | 2 +- .../java/com/seaofnodes/simple/node/SarNode.java | 5 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 11 +- .../java/com/seaofnodes/simple/node/ShlNode.java | 5 +- .../java/com/seaofnodes/simple/node/ShrNode.java | 5 +- .../java/com/seaofnodes/simple/node/StartNode.java | 2 +- .../java/com/seaofnodes/simple/node/StoreNode.java | 6 +- .../java/com/seaofnodes/simple/node/SubNode.java | 2 +- .../java/com/seaofnodes/simple/node/TypeNode.java | 2 +- .../java/com/seaofnodes/simple/node/XCtrlNode.java | 2 +- .../java/com/seaofnodes/simple/node/XorNode.java | 5 +- .../com/seaofnodes/simple/parser/Allocations.java | 199 ++ .../com/seaofnodes/simple/parser/ControlFlow.java | 96 + .../com/seaofnodes/simple/parser/Conversions.java | 72 + .../com/seaofnodes/simple/parser/Declarations.java | 164 + .../com/seaofnodes/simple/parser/Expressions.java | 394 +++ .../com/seaofnodes/simple/parser/Functions.java | 346 +++ .../java/com/seaofnodes/simple/parser/Lexer.java | 384 +++ .../java/com/seaofnodes/simple/parser/Parser.java | 298 ++ .../java/com/seaofnodes/simple/parser/README.md | 26 + .../com/seaofnodes/simple/parser/References.java | 369 +++ .../com/seaofnodes/simple/parser/Statements.java | 272 ++ .../java/com/seaofnodes/simple/parser/Structs.java | 411 +++ .../java/com/seaofnodes/simple/parser/Types.java | 244 ++ .../java/com/seaofnodes/simple/parser/Var.java | 54 + .../com/seaofnodes/simple/parser/package-info.java | 14 + src/main/java/com/seaofnodes/simple/type/Type.java | 1 + .../com/seaofnodes/simple/type/TypeStruct.java | 11 +- 69 files changed, 3826 insertions(+), 3698 deletions(-) delete mode 100644 src/main/java/com/seaofnodes/simple/IterPeeps.java delete mode 100644 src/main/java/com/seaofnodes/simple/Parser.java create mode 100644 src/main/java/com/seaofnodes/simple/README.md delete mode 100644 src/main/java/com/seaofnodes/simple/Var.java create mode 100644 src/main/java/com/seaofnodes/simple/codegen/IterPeeps.java create mode 100644 src/main/java/com/seaofnodes/simple/parser/Allocations.java create mode 100644 src/main/java/com/seaofnodes/simple/parser/ControlFlow.java create mode 100644 src/main/java/com/seaofnodes/simple/parser/Conversions.java create mode 100644 src/main/java/com/seaofnodes/simple/parser/Declarations.java create mode 100644 src/main/java/com/seaofnodes/simple/parser/Expressions.java create mode 100644 src/main/java/com/seaofnodes/simple/parser/Functions.java create mode 100644 src/main/java/com/seaofnodes/simple/parser/Lexer.java create mode 100644 src/main/java/com/seaofnodes/simple/parser/Parser.java create mode 100644 src/main/java/com/seaofnodes/simple/parser/README.md create mode 100644 src/main/java/com/seaofnodes/simple/parser/References.java create mode 100644 src/main/java/com/seaofnodes/simple/parser/Statements.java create mode 100644 src/main/java/com/seaofnodes/simple/parser/Structs.java create mode 100644 src/main/java/com/seaofnodes/simple/parser/Types.java create mode 100644 src/main/java/com/seaofnodes/simple/parser/Var.java create mode 100644 src/main/java/com/seaofnodes/simple/parser/package-info.java (limited to 'src/main/java/com') diff --git a/src/main/java/com/seaofnodes/simple/IterPeeps.java b/src/main/java/com/seaofnodes/simple/IterPeeps.java deleted file mode 100644 index a018c3ee..00000000 --- a/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ /dev/null @@ -1,351 +0,0 @@ -package com.seaofnodes.simple; - -import com.seaofnodes.simple.codegen.CodeGen; -import com.seaofnodes.simple.codegen.Opto; -import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeInteger; -import com.seaofnodes.simple.util.Ary; -import com.seaofnodes.simple.node.*; -import java.util.Arrays; -import java.util.BitSet; -import java.util.IdentityHashMap; -import java.util.Random; - -/** - * The IterPeeps runs after parsing. It iterates the peepholes to a fixed point - * so that no more peepholes apply. This should be linear because peepholes rarely - * (never?) increase code size. The graph should monotonically reduce in some - * dimension, which is usually size. It might also reduce in e.g. number of - * MulNodes or Load/Store nodes, swapping out more "expensive" Nodes for cheaper - * ones. - *
- * The theoretical overall worklist is mindless just grabbing the next thing and - * doing it. If the graph changes, put the neighbors on the worklist. - *
- * Lather, Rinse, Repeat until the worklist runs dry. - *

- * The main issues we have to deal with: - * - *

    - *
  • Nodes have uses; replacing some set of Nodes with another requires more graph - * reworking. Not rocket science, but it can be fiddly. Its helpful to have a - * small set of graph munging utilities, and the strong invariant that the graph - * is stable and correct between peepholes. In our case `Node.subsume` does - * most of the munging, building on our prior stable Node utilities.
    • - * - *
  • Changing a Node also changes the graph "neighborhood". The neighbors need to - * be checked to see if THEY can also peephole, and so on. After any peephole - * or graph update we put a Nodes uses and defs on the worklist.
    • - * - *
  • Our strong invariant is that for all Nodes, either they are on the worklist - * OR no peephole applies. This invariant is easy to check, although expensive. - * Basically the normal "iterate peepholes to a fixed point" is linear, and this - * check is linear at each peephole step... so quadratic overall. It's a useful - * assert, but one we can disable once the overall algorithm is stable - and - * then turn it back on again when some new set of peepholes is misbehaving. - * The code for this is turned on in `IterPeeps.iterate` as `assert - * progressOnList(stop);`
    • - *
- */ -public class IterPeeps { - - public final WorkList _work; - final WorkList _workInline; - private int _cnt; - - public IterPeeps( long seed ) { - _work = new WorkList<>(seed); - _workInline = new WorkList<>(seed); - } - - @SuppressWarnings("unchecked") - public N add( N n ) { return (N)_work.push(n); } - - public void addAll( Ary ary ) { _work.addAll(ary); } - - /** - * Iterate peepholes and inlining to a fixed point - */ - public void iterate( CodeGen code ) { - boolean didInline = false; - Ary defer = new Ary<>(Node.class); - while( true ) { - // Clean up everything that does not grow the code - iteratePeeps(code); - - // Pick an inline candidate, no real heuristic, first come, first served - boolean inlined = false; - CallEndNode cend; - while( (cend=_workInline.pop()) != null) { - if( cend.isDead() ) continue; - if( cend.loadForInline() ) { inlined=true; break; } - byte inline = cend.maybeInline(); - if( inline == -1 ) defer.add(cend); - if( inline > 0 ) { - inlined = true; - break; - } - } - // Inlined, run peeps until clean again - if( inlined ) { didInline = true; continue; } - // No more candidates, check the defer list - if( !didInline ) break; // No more progress, so all the "maybe inline after cleanup" do not progress - // Some inlining happened, retry all the "try again after cleanup" calls - didInline = false; - code.addAll(defer); - defer.clear(); - } - } - - // Run all the code-reduction and type-lifting peeps as possible - private void iteratePeeps( CodeGen code ) { - assert !CodeGen.expensiveAssert(0) || (progressOnList(code, _work) && schedulableUses(code)); - - Node n; - while( (n=_work.pop()) != null ) { - if( n.isDead() ) continue; - _cnt++; // Useful for debugging, searching which peephole broke things - var obs = code._obs; // Collect peephole neighbors for graph display - if( obs != null ) obs.before(n); - Node x = n.peepholeOpt(); - if( n instanceof CallEndNode cend ) - _workInline.push(cend); - if( x != null ) { - assert !x.isDead(); // Peepholes return alive answers - // peepholeOpt can return brand-new nodes, needing an initial type set - if( x._type==null ) x.setType(x.compute()); - // Changes require neighbors onto the worklist - if( x != n || !(x instanceof ConstantNode) ) { - // All outputs of n (changing node) not x (prior existing node). - for( Node z : n._outputs ) _work.push(z); - // Everybody gets a free "go again" in case they didn't get - // made in their final form. - _work.push(x); - // A self-returning peephole can have rewritten its input - // edges. The new defs gained a user and may have - // backwards, user-sensitive peepholes of their own. - for( Node z : x._inputs ) _work.push(z); - // If the result is not self, revisit all inputs (because - // there's a new user), and replace in the graph. - if( x != n ) { - //for( Node z : n. _inputs ) _work.push(z); - for( Node z : x._outputs ) _work.push(z); - n.subsume(x); - } - } - // If there are distant neighbors, move to worklist - n.moveDepsToWorklist(); - // Very expensive assert. - assert !CodeGen.expensiveAssert(_cnt) || (progressOnList(code, _work) && schedulableUses(code)); - } - boolean unused = n.isUnused(); - if( unused ) { - assert !(n instanceof StopNode); // StopNodes can die if all code in the compunit dies - n.kill(); // Just plain dead - } - if( obs != null ) obs.after(n, x!=null ? x : unused ? n : null, true); - } - assert !CodeGen.expensiveAssert(0) || schedulableUses(code); - - } - - // Visit ALL nodes and confirm the invariant: - // Either you are on the _work worklist OR running `iter()` makes no progress. - - // This invariant ensures that no progress is missed, i.e., when the - // worklist is empty we have indeed done all that can be done. To help - // with debugging, the {@code assert} is broken out in a place where it is easy to - // stop if a change is found. - - // Also, the normal usage of `iter()` may attempt peepholes with distance - // neighbors and these should fail, but will then try to add dependencies - // {@link #Node.addDep} which is a side effect in an assert. The {@link - // #midAssert} is used to stop this side effect. - // Pessimistic solver assert - public static boolean progressOnList(CodeGen code, WorkList list ) { - code._midAssert = true; - Node changed = code._stop.walk( n -> { - // Ignore most in-progress things - if( n.iskeep() ) return null; - // Types must be forwards, even if on the worklist. - Type nval = n.compute(); - assert nval.isa(n._type) : "Non-monotonic peep: "+n+"#"+n._nid+" old="+n._type+" new="+nval+" inputs="+inputTypes(n)+" peep="+n; - if( list.on(n) ) - return null; // On worklist is ok! - if( n instanceof CallEndNode cend ) { - if( code._iter._workInline.on(cend) ) - return null; // On inline worklist is ok! - assert cend.maybeInline() <= 0 : "Inline fired and not on worklist, CallEndNode#"+cend._nid; - } - // Off list: must be live, in GVN table, and no peeps. - assert n.nOuts() > 0 : "Unused live node: "+n; - assert code._gvn.get(n)==n : "Not in GVN table: "+n; - Node m = n.peepholeOpt(); - assert m==null : "Peep fired and not on worklist, "+n.getClass().getSimpleName()+"#"+n._nid+" -> "+m; - return m; - }); - code._midAssert = false; - return changed==null; - } - - private static String inputTypes(Node n) { - StringBuilder sb = new StringBuilder("["); - for( Node in : n._inputs ) - sb.append(in==null ? "null" : in.getClass().getSimpleName()+"#"+in._nid+"="+in+":"+in._type+":keep="+in.iskeep()).append(','); - return sb.append(']').toString(); - } - - // GCM assumes every movable node can be placed no earlier than its inputs - // and no later than the LCA of its uses. Catch graphs where a use escapes - // above an input-defined branch before the later scheduling pass walks off - // the top of the idom tree. - private static final IdentityHashMap earlyCache = new IdentityHashMap<>(); - private static final BitSet VISIT = new BitSet(); - public static boolean schedulableUses(CodeGen code) { - earlyCache.clear(); - Node bad = code._stop.walk( n -> { - if( n.iskeep() || n.isDead() || n.isConst() || - n instanceof CFGNode || n instanceof PhiNode || n instanceof ProjNode ) - return null; - assert VISIT.isEmpty(); - CFGNode early = CFGNode.earlyCFG(n,earlyCache,VISIT); - VISIT.clear(); - if( early == null ) return null; - CFGNode lca = null; - for( Node use : n._outputs ) { - CFGNode ublk = useBlock(n,use); - if( ublk != null ) - lca = ublk.domLCA(lca,null); - } - if( lca == null ) return null; - if( !early.sameFun(lca) ) return null; - assert early.dominates(lca,null) : badSchedule(n,early,lca); - return null; - }); - return bad == null; - } - - private static CFGNode useBlock(Node n, Node use) { - if( use == null ) - return null; - if( use instanceof PhiNode phi ) { - CFGNode found = null; - for( int i=1; i= phi.region().nIns() ) - return null; - found = phi.region().cfg(i).domLCA(found,null); - } - return found; - } - return CFGNode.safeCFG(use); - } - - private static String badSchedule(Node n, CFGNode early, CFGNode lca) { - StringBuilder sb = new StringBuilder("Unschedulable data node ") - .append(n.getClass().getSimpleName()).append('#').append(n._nid) - .append(" early=").append(cfg(early)) - .append(" use-lca=").append(cfg(lca)) - .append(" node=").append(n).append("\ninputs:"); - for( int i=0; i { - - private Node[] _es; - private int _len; - private final BitSet _on; // Bit set if Node._nid is on WorkList - private final Random _R; // For randomizing pull from the WorkList - private final long _seed; - - /* Useful stat - how many nodes are processed in the post parse iterative opt */ - private long _totalWork = 0; - - public WorkList() { this(123); } - WorkList(long seed) { - _es = new Node[1]; - _len=0; - _on = new BitSet(); - _seed = seed; - _R = new Random(); - _R.setSeed(_seed); - } - - /** - * Pushes a Node on the WorkList, ensuring no duplicates - * If Node is null it will not be added. - */ - public E push( E x ) { - if( x==null ) return null; - int idx = x._nid; - if( !_on.get(idx) ) { - _on.set(idx); - if( _len==_es.length ) - _es = Arrays.copyOf(_es,_len<<1); - _es[_len++] = x; - _totalWork++; - } - return x; - } - - public void addAll( Ary ary ) { - for( E n : ary ) - push(n); - } - public void addAll( E[] es ) { - for( E n : es ) - push(n); - } - - - /** - * True if Node is on the WorkList - */ - public boolean on( E x ) { return _on.get(x._nid); } - - /** - * Removes a random Node from the WorkList; null if WorkList is empty - */ - public E pop() { - if( _len == 0 ) return null; - int idx = _R.nextInt(_len); - E x = (E)_es[idx]; - _es[idx] = _es[--_len]; // Compress array - _es[_len] = null; - _on.clear(x._nid); - return x; - } - - public boolean isEmpty() { return _len==0; } - public void clear() { - Arrays.fill(_es,0,_len,null); - _len = 0; - _on.clear(); - _R.setSeed(_seed); - _totalWork = 0; - } - } -} diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java deleted file mode 100644 index 83bef882..00000000 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ /dev/null @@ -1,3197 +0,0 @@ -package com.seaofnodes.simple; - -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.BAOS; -import com.seaofnodes.simple.node.ScopeNode.Kind; - -import static com.seaofnodes.simple.util.Utils.TODO; - -import java.util.*; - -/** - * The Parser converts a Simple source program to the Sea of Nodes intermediate - * representation directly in one pass. There is no intermediate Abstract - * Syntax Tree structure. - *

- * This is a simple recursive descent parser. All lexical analysis is done here as well. - */ -public class Parser { - - // 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 - * we handle branching. See {@link #parseIf()}. - *

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

- * We keep a list of all ScopeNodes so that we can show them in graphs. - * @see #parseIf() - * @see #_xScopes - */ - public ScopeNode _scope; - - /** - * List of keywords disallowed as identifiers - */ - public static final HashSet KEYWORDS = new HashSet<>(){{ - add("bool"); - add("break"); - add("byte"); - add("continue"); - add("else"); - add("f32"); - add("f64"); - add("false"); - add("flt"); - add("i16"); - add("i32"); - add("i64"); - add("i8"); - add("if"); - add("int"); - add("new"); - add("null"); - add("return"); - add("struct"); - add("true"); - add("u1"); - add("u16"); - add("u32"); - add("u8"); - add("while"); - }}; - - /** - * We clone ScopeNodes when control flows branch; it is useful to have - * a list of all active ScopeNodes for purposes of visualization of the SoN graph - */ - public final Stack _xScopes = new Stack<>(); - - 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 - // Layouts needed by field accesses in this source file. Resolve after - // parsing, since a later local struct declaration can satisfy the use. - public final LinkedHashSet _requiredTypes = new LinkedHashSet<>(); - 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 final HashMap TYPES = new HashMap<>(); - public static final HashMap INIT_TYPES = - new HashMap<>() {{ - put("bool",TypeInteger.U1 ); - put("byte",TypeInteger.U8 ); - put("f32" ,TypeFloat .F32); - put("f64" ,TypeFloat .F64); - put("flt" ,TypeFloat .F64); - put("i16" ,TypeInteger.I16); - put("i32" ,TypeInteger.I32); - put("i64" ,TypeInteger.BOT); - put("i8" ,TypeInteger.I8 ); - put("int" ,TypeInteger.BOT); - put("u1" ,TypeInteger.U1 ); - put("u16" ,TypeInteger.U16); - put("u32" ,TypeInteger.U32); - put("u8" ,TypeInteger.U8 ); - put("val" ,Type.TOP); // Marker type, indicates type inference - put("var" ,Type.BOTTOM); // Marker type, indicates type inference - }}; - - - public 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); } - // 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); - _frefs = new Ary<>(FRefNode.class); - _requiredTypes.clear(); - // Starting Scope has control, memory, initial arguments - _scope = new ScopeNode(); - _scope.define(ScopeNode.CTRL, Type.CONTROL , false, null, _lexer); - _scope.define(ScopeNode.MEM0, TypeMem.BOT , false, null, _lexer); - // Track active scopes for Graph display - _xScopes.push(_scope); - ctrl(_code.XCTRL); - mem(con(TypeMem.BOT)); - - // File-level struct declaration - _ref = ref; - _nestedType = ref._cname; - String typeName = addClzPrefix(ref._cname); - - ReturnNode clzret = parseStruct( true, typeName ); - - if( !_lexer.isEOF() ) throw _errorSyntax("unexpected"); - - // 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); - } - - // The class being published - ref._clz = (TypeStruct)TYPES.get(typeName); - - // Clean up and reset - _xScopes.pop(); - _scope.kill(); - _scope = null; - _frefs = null; - - return frefs; - } - - - /** - * Parses a function body, assuming the header is parsed. - */ - 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) { - // 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) { - Constructor outerCtor=_pendingCtor; - _pendingCtor=null; - 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 - _scope.push(new Kind.Func(funName,isCtor && !funName.endsWith("."))); - ScopeNode breakScope = _breakScope; _breakScope = null; - ScopeNode continueScope = _continueScope; _continueScope = null; - ScopeNode returnScope = _returnScope; _returnScope = null; - - 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,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.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 ); - } - - if( isInit ) finishConstructor(); - _pendingCtor=outerCtor; - - 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); - } - 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; - _breakScope = breakScope; - _scope.pop(); - - return ret; - } - - private int updateSelfAsFieldsDiscovered( String typeName, int nvar ) { - int lex = _scope.klast()._lexSize + 2/*Skip self and selfMem*/; - // Load self type in and out of the TYPES hashtable. - TypeStruct tself = (TypeStruct)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 < _scope.nIns() ) { - Var v = _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(),_code.alias(_ref._cname),v._final) - : old.makeFrom(v.type()); - tself = tself.addOrUpdate(fld); - } - TYPES.put(typeName,tself); - return nvar; - } - - - void upgradeSelfTypeAndStoreFields( String typeName, boolean isClz, ParmNode self, ParmNode smem, boolean upgrade ) { - int lex = _scope.klast()._lexSize; - assert _scope.var(lex)._name=="self"; - TypeStruct tself = (TypeStruct)TYPES.get(typeName); - int base = lex+2; // Skip ctrl, mem - if( upgrade ) { - // Default / defines the struct and can sharpen fields. - // A named constructor only initializes the already-closed struct. - for( int i=0; i receives the - // broad allocation pointer, while private memory tracks initialized fields. - self._declaredType = self._type = isClz ? TypeMemPtr.make((byte)2,tself,true) : TypeMemPtr.make(constructorRecv(tself)); - FunNode fun = self.fun(); - fun.setSig(fun.sig().makeFrom(self._type,0)); - if( !isClz ) // returns upgraded private memory - smem._declaredType = smem._type = TypeMem.makePrivate(tself); - } - - if( !upgrade ) { - IdentityHashMap exit = null; - if( _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 - * '{' statements '}' - * - * Does not parse the opening or closing '{}' - * @return a {@link Node} or {@code null} - */ - private Node parseBlock(Kind kind) { - // Enter a new scope - _scope.push(kind); - Node last = _code.ZERO; - while (!peek('}') && !_lexer.isEOF()) { - _code.add(last); - last = parseStatement(); - } - // Exit scope - last.keep(); - _scope.pop(); - return last.unkeep(); - } - - /** - * Parses a statement - * - * 

-     *     returnStatement | declStatement | blockStatement | ifStatement | expressionStatement
-     *
- * @return a {@link Node} or {@code null} - */ - private Node parseStatement() { - if( matchx("return") ) return parseReturn(); - else if (matchx("if") ) return parseIf(); - else if (matchx("while") ) return parseWhile(); - else if (matchx("for") ) return parseFor(); - else if (matchx("break") ) return parseBreak(); - else if (matchx("continue")) return parseContinue(); - else if (matchx("struct") ) return parseStruct(); - else if (inStructDeclaration() && matchx("new")) return parseConstructorDeclaration(); - else if (matchx(";") ) return _code.ZERO; // Empty statement - // Break ambiguity around leading function types and starting a block - else if (peek('{') && !isTypeFun() ) { - match("{"); - return require(parseBlock(new Kind.Block()),"}"); - } - // Declaration or normal assignment/expression - else return parseDeclarationStatement(); - } - - private boolean inStructDeclaration() { - return _scope.klast() instanceof Kind.Func fun && FunNode.isInstance(fun._name); - } - - // Constructor declaration: new TypeName = { args -> body }; - private record Constructor(String name, Lexer body) {} - private Constructor _pendingCtor; - - 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("="); - if( _pendingCtor!=null ) throw error("Redefining constructor '"+name+"'"); - _pendingCtor=new Constructor(name,loc()); - // Parse the body after all field declarations are known, so self.x - // and x share a local slot even when x is declared below this body. - require("{"); - int depth=1; - while( depth>0 ) { - _lexer.skipWhiteSpace(); - if( _lexer.isEOF() ) throw error("Unclosed constructor body"); - char ch=_lexer.nextChar(); - if( ch=='{' ) depth++; - else if( ch=='}' ) depth--; - else if( ch=='"' || ch=='\'' ) { - char quote=ch; - while( !_lexer.isEOF() ) { - ch=_lexer.nextChar(); - if( ch=='\\' ) _lexer.nextChar(); - else if( ch==quote ) break; - } - } - } - require(";"); - return _code.ZERO; - } - - private void finishConstructor() { - if( _pendingCtor==null ) return; - Constructor ctor=_pendingCtor; - _pendingCtor=null; - Lexer after=_lexer; - _lexer=new Lexer(ctor.body()); - defineConstructor(ctor.name()); - _lexer=after; - } - - private void defineConstructor(String name) { - TypeStruct self=_scope.constructorSelf(); - 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)); - require(ctor,";"); - } - - /** - * Parses a while statement - * - * 
-     *     while ( expression ) statement
-     *
- * @return a {@link Node}, never {@code null} - */ - private Node parseWhile() { - require("("); - return parseLooping(false); - } - - - /** - * Parses a for statement - * - * 
-     *     for( var x=init; test; incr ) body
-     *
- * @return a {@link Node}, never {@code null} - */ - private Node parseFor() { - // { var x=init,y=init,...; - // while( test ) { - // body; - // next; - // } - // } - require("("); - _scope.push(new Kind.Block()); // Scope for the index variables - if( !match(";") ) // Can be empty init "for(;test;next) body" - parseDeclarationStatement(); // Non-empty init - Node rez = parseLooping(true); - _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()}. - - 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). - // We create phis eagerly for all the names we find, see dup(). - - // Save the current scope as the loop head - ScopeNode head = _scope.keep(); - // Clone the head Scope to create a new Scope for the body. - // Create phis eagerly as part of cloning - _xScopes.push(_scope = _scope.dup(true)); // The true argument triggers creating phis - - // Parse predicate - var pred = peek(';') ? con(1) : parseAsgn(); - require( doFor ? ";" : ")" ); - - // IfNode takes current control and predicate - Node ifNode = new IfNode(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 = pos(); - skipAsgn(); - nextEnd = pos(); - 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. - ctrl(ifF); - _xScopes.push(_breakScope = _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 - ctrl(ifT.unkeep()); // set ctrl token to ifTrue projection - _scope.addGuards(ifT,pred.unkeep(),false); // Up-cast predicate - parseStatement().isKill(); // Parse loop body - _scope.removeGuards(ifT); - - // Merge the loop bottom into other continue statements - if (_continueScope != null) { - _continueScope = jumpTo(_continueScope); - _scope.kill(); - _scope = _continueScope; - } - - // Now append the next code onto the body code - if( doFor ) { - int old = pos(nextPos); - if( !peek(')') ) - parseAsgn(); - if( pos() != nextEnd ) - throw errorSyntax( "Unexpected code after expression" ); - 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(_scope); - exit.balanceLoopFRefs(_scope); - head.endLoop(_scope, exit); - head.unkeep().kill(); - - _xScopes.pop(); // Cleanup - _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( !_xScopes.isEmpty() ) { - _xScopes.pop(); - _xScopes.push( exit ); - } - _scope = exit; - return _code.ZERO; - } - - private ScopeNode jumpTo(ScopeNode toScope) { - ScopeNode cur = _scope.dup(); - 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() ) - cur.pop(); - // If this is a continue then first time the target is null - // So we just use the pruned current scope as the base for the - // "continue" - if( toScope == null ) - return cur; - // toScope is either the break scope, or a scope that was created here - assert toScope.depth() <= _breakScope.depth(); - toScope.ctrl(toScope.mergeScopes(cur,loc()).peephole()); - return toScope; - } - - 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 _code.ZERO; } - private Node parseBreak () { - checkLoopActive(); - // At the time of the break, and loop-exit conditions are only valid if - // they are ALSO valid at the break. It is the intersection of - // conditions here, not the union. - _breakScope.removeGuards(_breakScope.ctrl()); - _breakScope = require(jumpTo(_breakScope ),";"); - _breakScope.addGuards((CFGNode)_breakScope.ctrl(), null, false); - return _code.ZERO; - } - - // Look for an unbalanced `)`, skipping balanced - private void skipAsgn() { - int paren=0; - while( true ) - // Next X char handles skipping complex comments - switch( _lexer.nextXChar() ) { - case Character.MAX_VALUE: - throw TODO(); - case ')': - if( --paren<0 ) { - posT( pos() - 1 ); - return; // Leave the `)` behind - } - break; - case '(': paren ++; break; - default: break; - } - } - - - /** - * Parses a statement - * - * 
-     *     if ( expression ) statement [else statement]
-     *
- * @return a {@link Node}, never {@code null} - */ - private Node parseIf() { - // Parse predicate - require("("); - var pred = require(parseAsgn(), ")"); - return parseTrinary(pred,"else"); - } - - // Parse a conditional expression, merging results. - private Node parseTrinary( Node pred, String fside ) { - // IfNode takes current control and predicate - pred.keep(); - Node ifNode = new IfNode(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 = _scope.dup(); // Duplicate current scope - fScope.ctrl(ifF); // The pending arm already starts at False - _xScopes.push(fScope); // For graph visualization we need all scopes - - // Parse the true side - ctrl(ifT.unkeep()); // set ctrl token to ifTrue projection - _scope.addGuards(ifT,pred,false); // Up-cast predicate - // Parse true-side flavor - Node lhs = switch( fside ) { - case "else" -> parseStatement(); // if( pred ) stmts; - case ":" -> parseAsgn(); // pred ? asgn; - case "&&" -> parseLogical(); // pred && expr - case "||" -> pred; // pred || expr_is_ignored - default -> throw TODO(); - }; - lhs.keep(); - _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(_scope); - - ScopeNode tScope = _scope; - - // Parse the false side - _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;` - _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=match(fside)) ? parseStatement() : con(lhs._type.makeZero()); - case ":" -> (doRHS=match(fside)) ? parseAsgn() : con(lhs._type.makeZero()); - 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(); - - // Check the trinary widening int/flt - if( !fside.equals("else") ) { - rhs = widenInt( rhs.unkeep(), lhs._type ).keep(); - lhs = widenInt( lhs.unkeep(), rhs._type ).keep(); - } - - _scope = tScope; - _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 = ctrl(tScope.mergeScopes(fScope,loc())); - 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; - ret.keep(); - r.peephole(); - return ret.unkeep(); - } - - /** - * Parses a return statement; "return" already parsed. - * The $ctrl edge is killed. - * - * 
-     *     'return' expr ;
-     *
- * @return an expression {@link Node}, never {@code null} - */ - private Node parseReturn() { - var expr = require(parseAsgn(), ";"); - 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(); - // Just a plain expression, no assignment. - // Distinguish `var==expr` from `var=expr` - if( name==null || KEYWORDS.contains(name) || !matchOpx('=','=') ) - { pos(old); return parseExpression(); } - - // Find variable to update - Var def = _scope.lookup(name); - if( def==null ) - def = defineOpenConstructorField(name); - if( def==null ) - throw error("Undefined name '" + 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 - // outside the constructor need to check the final bit. - 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) ) - throw error("Cannot reassign final '"+name+"'"); - checkSharedFunction(def); - - // Parse assignment expression - Node expr = parseAsgn(); - - // Lift expression, based on type - 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(); - } - - // Widen ints to floats; narrow wide int types. - // Early error if types do not match variable. - 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()); - 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() ) - 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; - }; - } - - private Type constructorFieldType(Type t) { - if( t instanceof TypeMemPtr ptr && ptr._obj.isConAry() ) { - TypeStruct declared=(TypeStruct)TYPES.get(ptr._obj._name); - TypeStruct shape=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. - 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 ) { - return (expr._type instanceof TypeInteger || expr._type==Type.NIL) && t instanceof TypeFloat - ? peep(new ToFloatNode(expr)) : expr; - } - - /** - * Parse declaration or expression statement - * declStmt = type var['=' exprAsgn][, var['=' exprAsgn]]* ';' | exprAsgn ';' - *

- * exprAsgn = var '=' exprAsgn | expr - */ - private Node parseDeclarationStatement() { - int old = pos(); - Type t = type(); - if( peek('.') ) // Ambiguity static vars: "type.var", parse as expression - { pos(old); t=null; } - if( t == null ) - return require(parseAsgn(),";"); - - // now parse var['=' asgnexpr] in a loop - Node n = parseDeclaration(t); - while( match(",") ) - n = parseDeclaration(t); - return require(n,";"); - } - - // The binding modifier sits immediately before the name. It never - // changes permissions on the referenced object. - private boolean bindingFinal(Type t) { - if( match("!") ) return false; - if( 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 = loc(); - String name = requireId(); - // Optional initializing expression follows - boolean fld_final = false; // Field is final, but not deeply final - boolean uninit = false; // Required non-null constructor field - Node expr; - if( 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 = 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( _scope.klast() instanceof Kind.Func fun && FunNode.isInstance(fun._name) && !(t instanceof TypeFunPtr) ) - t = constructorFieldType(t); - } - - // expr is a constant function - if( t instanceof TypeFunPtr decl && expr._type instanceof TypeFunPtr tfp && tfp.isConstant() ) { - t = decl.makeFrom(tfp.fidx()); - FunNode fun = _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() )) && !_scope.inConstructor() ) - throw 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() ? 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); } - }; - // 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 : convertExpr(expr, t); - - // Define a new name - if( !_scope.define(name,t,xfinal || fld_final,lift, loc) ) - throw error("Redefining name '" + name + "'", loc); - _scope.lookup(name)._uninit = uninit; - return lift; - } - - - /** - * Parse a struct declaration, and return the following statement. - * Structs cannot be redefined, but can be nested. - * - * @return zero - */ - private Node parseStruct( ) { - // keyword "struct" already parsed, so expect the struct name next. - String typeName = requireId(); - require("{"); - - // create type class:NESTED.typeName; no fields. - - String old = _nestedType; - String fullName = _scope.depth()==1 && _nestedType.endsWith(typeName) ? old : (old+"."+typeName).intern(); - _nestedType = fullName; // Recursive structs start with this as their basename - - ReturnNode ret = parseStruct( false, fullName ); - - _nestedType = old; - - // Insert a field into class:NESTED.typeName of "val typeName = fcn-ptr-to-init" - // Function does malloc internally. - // Future self: means subtyping has to deal with "who does the malloc" - String clzName = addClzPrefix(fullName); - TypeFunPtr sig = ret.fun().sig(); - TypeStruct ts = (TypeStruct)TYPES.get(clzName); - String initName = initFieldName(fullName); - Field oldFld = ts==null ? null : ts.field(initName); - Field fld = oldFld==null - ? Field.make(initName,sig,_code.alias(_ref._cname),true) - : oldFld.makeFrom(sig); - Field ctorFld = ts==null ? null : ts.field(""); - // A same-named struct shares its file's class object and flag. - Field flag = ts==null ? null : ts.field("$init"); - ts = ctorFld==null - ? TypeStruct.make(clzName,false,fld) - : TypeStruct.make(clzName,false,fld,ctorFld); - if( flag!=null ) ts=ts.add(flag); - TypeFunPtr alloc = 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()); - - require("}"); - 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()); - } - - // Class object keeps a runtime flag to signal the has run. - if( isClz ) - TYPES.put(typeName,tself=tself.add(Field.make("$init",TypeInteger.BOOL,_code.alias(_ref._cname),false))); - - // 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)); - } - - 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); - } - - - // Parse and return a type or null. Valid types always are followed by an - // 'id' which the caller must parse. This lets us distinguish forward ref - // types (which ARE valid here) from local vars in an (optional) forward - // ref type position. - - // 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() { - // 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), t1 = t0; - // No new types as keywords - 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); - - // 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 posT(old1); - - // Nest arrays and '?' as needed - Type t2 = t1; - while( true ) { - if( match("?") ) { - 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"); - } else if( match("[~]") ) { - t2 = TypeMemPtr.make(typeAry(t2,true)).makeRO(); - } else if( 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 = pos(); - if( !match("!") ) match("~"); - String id = _lexer.matchId(); - 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 - forwardRefType(tname,(TypeStruct)((TypeMemPtr)t1)._obj); - // Return the (array, final) type - return t2; - } - - private TypeMemPtr forwardRefType( String tname, TypeStruct tself ) { - TYPES.put(tname,tself); - String clzName = addClzPrefix( tname ); - // Only a struct declaration publishes an instance initializer. A - // forward type may name a file with just , so do not invent - // a constructor field (or overwrite an already parsed class). - TYPES.putIfAbsent(clzName,TypeStruct.make(clzName,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 }`. - private Type typeFunPtr() { - int old = pos(); // Record lexer position - match("{"); // Skip already-peeked '{' - Type t0 = type(); // Either return or first arg - if( t0==null ) return posT(old); // Not a function - Ary ts = new Ary<>(Type.class); - // Always reserve a receiver slot. Outside constructor scopes it is - // broad and unused, so call sites can uniformly pass their self. - ts.push(implicitSelfType()); - if( 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("?"),ts.asAry(),ret); - } - Type t1 = type(); - if( t1==null ) return posT(old); // Not a function - ts.push(t1); - } - } - - // True if a TypeFunPtr, without advancing parser - private boolean isTypeFun() { - int old = pos(); - if( typeFunPtr()==null ) return false; - pos(old); - return true; - } - - /** - * Parse an expression of the form: - * - * 

-     *     expr : bitwise [? expr [: expr]]
-     *
- * @return an expression {@link Node}, never {@code null} - */ - private Node parseExpression() { - Node expr = parseLogical(); - return match("?") ? parseTrinary(expr,":") : expr; - } - - /** - * Parse an bitwise expression - * - * 
-     *     bitwise : compareExpr (('&' | '|' | '^') compareExpr)*
-     *
- * @return a bitwise expression {@link Node}, never {@code null} - */ - - private Node parseLogical() { - Node lhs = parseBitwise(); - while (true) { - if( false ) ; - else if( match("&&") ) lhs = parseTrinary(lhs, "&&"); - else if( match("||") ) lhs = parseTrinary(lhs, "||"); - else break; - } - return lhs; - } - - private Node parseBitwise() { - Node lhs = parseEquality(); - while( true ) { - if( false ) ; - else if( matchOp('&') ) lhs = new AndNode(loc(),lhs,null); - else if( matchOp('|') ) lhs = new OrNode(loc(),lhs,null); - else if( match ("^") ) lhs = new XorNode(loc(),lhs,null); - else break; - lhs.setDef(2,parseEquality()); - lhs = peep(lhs); - } - return lhs; - } - - - /** - * Parse an eq/ne expression - */ - private Node parseEquality() { - Node lhs = parseComparison(); - while( true ) { - boolean eq = false; - if( match("==") ) eq = true; - else if( !match("!=") ) break; - lhs.keep(); - Node rhs = parseComparison(); - lhs = peep(new BoolNode.EQ(lhs.unkeep(),rhs)); - if( !eq ) lhs = peep(new NotNode(lhs)); - } - return lhs; - } - - /** - * Parse an expression of the form: - * - * 
-     *     expr : shiftExpr < shiftExpr <= shiftExpr...
-     *     expr : shiftExpr > shiftExpr >= shiftExpr...
-     *
- * @return an comparator expression {@link Node}, never {@code null} - */ - private Node parseComparison() { - Node lhs = parseShift(); - int dir = parseCompDir(); - // No compare - if( dir==0 ) return lhs; - lhs.keep(); - - // Compare - Node rhs = parseShift().keep(); - Node cmp = makeCompBool(dir,lhs.unkeep(),rhs).keep(); // Convert to a bool - - // Stacked compares? - int dir0 = parseCompDir(); - if( dir0 == 0 ) { - rhs.unkill(); - return cmp.unkeep(); - } - - // Keep the middle operand separately from the boolean result. - // The next test compares adjacent operands, not that boolean. - Node ifNode = new IfNode(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; // Reuse the previous RHS exactly once - rhs = parseShift().keep(); - cmp = makeCompBool(dir0,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,con(0),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 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 peep(cmp); - } - - /** - * Parse an additive expression - * - * 
-     *     shiftExpr : additiveExpr (('<<' | '>>' | '>>>') additiveExpr)*
-     *
- * @return a shift expression {@link Node}, never {@code null} - */ - private Node parseShift() { - Node lhs = parseAddition(); - while( true ) { - if( false ) ; - else if( match("<<") ) lhs = new ShlNode(loc(),lhs,null); - else if( match(">>>")) lhs = new ShrNode(loc(),lhs,null); - else if( match(">>") ) lhs = new SarNode(loc(),lhs,null); - else break; - lhs.setDef(2,parseAddition()); - ParseException err; - if( (err=lhs.err()) != null ) - throw err; - lhs = peep(lhs); - } - return lhs; - } - - /** - * Parse an additive expression - * - * 
-     *     additiveExpr : multiplicativeExpr (('+' | '-') multiplicativeExpr)*
-     *
- * @return an add expression {@link Node}, never {@code null} - */ - private Node parseAddition() { - Node lhs = parseMultiplication(); - while( true ) { - if( false ) ; - else if( match("+") ) lhs = new AddNode(lhs,null); - else if( match("-") ) lhs = new SubNode(lhs,null); - else break; - lhs.setDef(2,parseMultiplication()); - lhs = peep(lhs); - } - return lhs; - } - - /** - * Parse an multiplicativeExpr expression - * - * 
-     *     multiplicativeExpr : unaryExpr (('*' | '/') unaryExpr)*
-     *
- * @return a multiply expression {@link Node}, never {@code null} - */ - private Node parseMultiplication() { - var lhs = parseUnary(); - while( true ) { - if( false ) ; - else if( match("*") ) lhs = new MulNode(lhs,null); - else if( match("/") ) lhs = new DivNode(lhs,null); - else break; - lhs.setDef(2,parseUnary()); - lhs = peep(lhs); - } - return lhs; - } - - /** - * Parse a unary minus expression. - * - * 
-     *     unaryExpr : ('-') unaryExpr | '!') unaryExpr | postfixExpr | primaryExpr | '--' Id | '++' Id
-     *
- * @return a unary expression {@link Node}, never {@code null} - */ - private Node parseUnary() { - // Pre-dec/pre-inc - int old = pos(); - if( match("--") || match("++") ) { - int delta = _lexer.peek(-1)=='+' ? 1 : -1; // Inc vs Dec - int start = pos(); - String name = _lexer.matchId(); - Var var = name==null ? null : _scope.lookup(name); - if( var!=null && !(var.type() instanceof TypeMemPtr) ) { - if( var._extern==0 && var._final && !_scope.canInit(var) ) - throw error("Cannot reassign final '"+var._name+"'"); - // Resolve fields just as a read or postfix update does. Updating - // their declaration's local slot would silently lose the Store. - pos(start); - return parsePrimary(delta); - } - // Reset, try again - pos(old); - } - if (match("-")) return peep(new MinusNode(parseUnary())); - if (match("!")) return peep(new NotNode(parseUnary())); - // Else be a primary expression - return parsePrimary(); - } - - /** - * Parse a primary expression: - * - * 
-     *     primaryExpr : integerLiteral | "string" | 'char' | true | false | null |
-     *                   new Type | '(' expression ')' | Id['++','--'] |
-     *                   type['.' Id]*
-     *
- * @return a primary {@link Node}, never {@code null} - */ - private Node parsePrimary() { return parsePrimary(0); } - - // pre is +/-1 for a prefix update of a known name, zero otherwise. - private Node parsePrimary(int pre) { - if( _lexer.isNumber(_lexer.peek()) ) return parseLiteral(); - if( _lexer.peek('"') ) return parsePostfix(newString(parseString())); - if( matchx("true" ) ) return con(1); - 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(),"}")); - - int pos = pos(); - // Expect an identifier now - 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 ) { - // 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; - } - } - - // 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( var._extern!=0 ) - return parsePostfixName(rvalue,id,pre); - if( var._fref ) - return parsePostfix(rvalue); - // A constructor may read the unfinished object, but each field it - // reads must already be initialized on every path. Read the current - // local value; other fields may still be waiting for their first write. - if( inExplicitConstructor() && var._uninit && missingInit(rvalue,new BitSet()) ) - 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 && !inExplicitConstructor() ) - return parsePostfixName(_scope.in(method._lexSize),id,pre); - - // Check for a function-escaping variable; these require true - // closures. Final constants are OK; final vars require a hidden var - // argument; not-final fields can just use an explicit struct arg. - if( kx < fx && !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 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,pre ); - //return parsePostfixName(_scope.in(2),id); - } - } - - // Check for assign-update, x += e0; - char ch = pre==0 ? _lexer.matchOperAssign() : (char)pre; - 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 && !_scope.canInit(var) ) - throw error("Cannot reassign final '"+var._name+"'"); - checkSharedFunction(var); - Node op = opAssign(ch,rvalue, var.type() ); - _scope.update(var,op); - if( postfix(ch) ) rvalue.unkeep(); - return pre==0 && postfix(ch) ? rvalue : op; - } - - // 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. - private Node opAssign( char ch, Node lhs, Type t ) { - // RHS of the update. - lhs.keep(); // Alive across parseAsgn - Node rhs = - (byte)ch == 1 ? con( 1) : // var++ - (byte)ch == -1 ? con(-1) : // var-- - parseAsgn(); // var op= rhs - if( !postfix(ch) ) lhs.unkeep(); // Allow to die in next peep - // 4 cases: - // int + int ==>> narrow int - // int + flt ==>> error, caller must fail assigning flt into int - // flt + int ==>> use float op, wrap toFloat() - // flt + flt ==>> use float op - Node op = switch(ch) { - case 1, (char)-1, - '+' -> new AddNode(lhs,rhs); - case '-' -> new SubNode(lhs,rhs); - case '*' -> new MulNode(lhs,rhs); - case '/' -> new DivNode(lhs,rhs); - case '|' -> new OrNode(null,lhs,rhs); - case '&' -> new AndNode(null,lhs,rhs); - case '^' -> new XorNode(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 TODO(); - }; - // Convert to float ops, or narrow int types; error if not declared type. - // Also, if postfix LHS is still keep() - return convertExpr(peep(op),t); - } - - - /** - Parse an allocation - */ - private Node alloc() { - Type t = 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 are always zero/null filled"); - Node len = parseAsgn().keep(); - require("]"); - return allocArray(typeAry(t,false),len); - } else { - if( !(t instanceof TypeMemPtr tmp) ) - throw error("Cannot allocate a "+t.str()); - return allocStruct(tmp._obj); - } - } - - private Node allocStruct(TypeStruct ts) { - Ary ctorArgs = constructorArgs(); - // A field declaration can leave a short forward type name in TYPES. - // Allocation happens in lexical context, so resolve that short name - // to the completed nested type before selecting its class helper. - String typeName = ts._name.indexOf('.') == -1 ? 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("[]"); - - ConFldOffNode base = off(ts, "[]"); - int scale = ts.aryScale(); - Node size = peep(new AddNode(base,peep(new ShlNode(null,len,con(scale))))); - - // Build a NewNode; takes in and puts out all aliases. - NewNode nnn = new NewNode(ts, 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 = peep(new StoreNode(null, "#", 1, TypeInteger.U32, null, smem, self, off(ts,"#"), len.unkeep(), true)); - - // 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) { - 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", slen, lenAlias, body, elemAlias, true),true); - assert str.isConstant(); - return con(str.makeRO()); - } - - /** - * Parse postfix expression; this can be a field expression, an array - * lookup or a postfix operator like '#' - * - * 
-     *     expr ('.' FIELD)* [ = expr ]       // Field reference
-     *     expr '#'                           // Postfix unary read operator
-     *     expr ['++' | '--' ]                // Postfix unary write operator
-     *     expr ('[' expr ']')* = [ = expr ]  // Array reference
-     *     expr '(' [args,]* ')'              // Function call
-     *
- */ - 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) { - _lexer.skipWhiteSpace(); - Lexer site = loc(); - String name; - if( match(".") ) name = requireId(); - else if( match("#") ) name = "#"; - else if( match("[") ) name = "[]"; - // 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,0,site); - } - - private boolean privateSelf(Node ptr) { - while( ptr instanceof ConvertNode || ptr instanceof ReadOnlyNode || ptr instanceof GuardNode ) ptr=ptr.in(1); - Node self=defaultSelf(); - while( self instanceof ConvertNode || self instanceof ReadOnlyNode || self instanceof GuardNode ) self=self.in(1); - return ptr==self; - } - - // An explicit self.x read sees the same current value as bare x. Loading - // the allocation here would miss updates still held in local SSA values. - private Node privateField(String name, int pre) { - int idx=fieldVarIdxBefore(_scope._kinds.at(_scope.enclosingFuncOrDecl())._lexSize,name); - if( idx<0 ) throw error("Cannot resolve field '"+name+"'"); - Var v=_scope.var(idx); - if( pre==0 && matchOpx('=','=') ) { - checkSharedFunction(v); - Node value=parseAsgn().keep(); - _scope.update(v,convertExpr(value,v.type())); - return value.unkeep(); - } - Node value=_scope.in(_scope.update(v,null)); - if( v._uninit && missingInit(value,new BitSet()) ) - throw error("Field '"+name+"' might not be initialized",v._loc); - char ch=pre==0 ? _lexer.matchOperAssign() : (char)pre; - if( ch!=0 ) { - checkSharedFunction(v); - Node op=opAssign(ch,value,v.type()); - _scope.update(v,op); - if( pre!=0 && postfix(ch) ) value.unkeep(); - return pre==0 && postfix(ch) ? value.unkeep() : op; - } - return parsePostfixMethod(value,defaultSelf()); - } - - private void checkSharedFunction(Var v) { - if( _scope.canInit(v) && v._final && v.type() instanceof TypeFunPtr t && t.isConstant() ) - throw error("Cannot reassign shared function '"+v._name+"'"); - } - - // A loop Phi is temporarily bottom before its backedge is parsed. That is - // not an unwritten field: follow its live inputs to the actual defaults. - private boolean missingInit(Node value, BitSet seen) { - if( value==null || seen.get(value._nid) ) return false; - seen.set(value._nid); - if( value instanceof PhiNode phi && !(value instanceof ParmNode) ) { - for( int i=1; i - * expr ['++' | '--' ] // Postfix unary write operator - * expr [ [op]= expr ] // Field reference - * expr ('[' expr ']')* [ [op]= expr ] // Array reference - * - */ - - // pre is +/-1 for a prefix update, otherwise parse a postfix operation. - private Node parsePostfixName(Node expr, String name, int pre) { - return parsePostfixName(expr,name,pre,loc()); - } - - private Node parsePostfixName(Node expr, String name, int pre, Lexer site) { - if( inExplicitConstructor() && privateSelf(expr) ) return privateField(name,pre); - // Keep expr across possible updates - expr.keep(); - - // Get the best known TypeStruct from a pointer type. - TypeStruct ts = null, ts2; - if( expr._type instanceof TypeMemPtr tmp && (ts2=((TypeStruct)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+"'"); - - // 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)_scope._kinds.at(_scope.enclosingFuncOrDecl()); - if( (ts==null || ts==TypeStruct.BOT || ts.isHigh() || startsClzPrefix(ts._name)) && - !(ts!=null && (ts._name+".").equals(func._name)) ) - 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. - ? 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( pre==0 && matchOpx('=','=') ) { - // Field assignment - Node val = parseAsgn().keep(); - // 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(); - - 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 = peep(new LoadNode(loc(),name, alias, ctrl(), mem, expr, off)); - - // Check for assign-update, "ptr.fld += expr" or "ary[idx]++" - char ch = pre==0 ? _lexer.matchOperAssign() : (char)pre; - if( ch!=0 ) { - 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(); - - 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; - } - off.unkill(); - // Might be a method call, so pass expr as 'self' - return parsePostfixMethod(load,expr.unkeep()); - } - - - // zero/sign extend. "i" is limited to either classic unsigned (min==0) or - // classic signed (min=minus-power-of-2); max=power-of-2-minus-1. - private Node zsMask(Node val, Type t ) { - if( val._type instanceof TypeFloat && t instanceof TypeInteger ) - val = new ToIntegerNode(val).peephole(); - if( !(val._type instanceof TypeInteger tval && t instanceof TypeInteger t0 && !tval.isa(t0)) ) { - if( !(val._type instanceof TypeFloat tval && t instanceof TypeFloat t0 && !tval.isa(t0)) ) - return val; - // Float rounding - return peep(new RoundF32Node(val)); - } - if( t0._min==0 ) // Unsigned - return peep(new AndNode(null,val,con(t0._max))); - // Signed extension - int shift = Long.numberOfLeadingZeros(t0._max)-1; - Node shf = con(shift); - if( shf._type==TypeInteger.ZERO ) - return val; - return peep(new SarNode(null,peep(new ShlNode(null,val,shf.keep())),shf.unkeep())); - } - - /** - * Parse a function body; the caller will parse the surrounding "{}" - * - * 
-     *     { [type arg,]* -> expr }
-     *     { expr } // The no-argument function
-     *
- */ - private Node func() { - Ary ts = new Ary<>(Type.class); - Ary ids = new Ary<>(String.class); - java.util.BitSet finals = new java.util.BitSet(); - Type self = implicitSelfType(); - ts.push(self); - ids.push(self == TypePtr.PTR ? "#self" : "self"); - - // Parse other arguments - _lexer.skipWhiteSpace(); - Lexer loc = loc(); // First argument location - while( true ) { - Type t = type(); // Arg type - if( t==null ) break; - finals.set(ids.size(),bindingFinal(t)); - String id = requireId(); - ts .push(t ); // Push type/arg pairs - ids.push(id); - match(","); - } - require("->"); - // Make a concrete function type, with a fidx - 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(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(); - } - - /** - * Parse function call arguments; caller will parse the surrounding "()" - * 
-     *   ( arg* )
-     *
- */ - private Node functionCall(Node fcn, Node self) { - Lexer site = loc(); - site._position--; // Opening '('; arguments can contain nested calls. - if( fcn._type == Type.NIL ) - throw error("Calling a null function pointer"); - fcn.keep(); // Keep while parsing args - - Ary args = new Ary<>( Node.class ); - args.push(null); // Space for ctrl,mem - args.push(null); - if( self != null ) // Method call has a self - args.push(self.keep()); - while( !peek(')') ) { - Node arg = parseAsgn(); - if( arg==null ) break; - args.push(arg.keep()); - if( !match(",") ) break; - } - // Control & memory after parsing args - args.set(0,ctrl().keep()); - args.set(1,mem().keep()); - args.push(fcn); // Function pointer - // Unkeep them all - for( Node arg : args ) - arg.unkeep(); - return functionCall(args,site); - } - - private Node functionCall( Ary args ) { - return functionCall(args,loc()); - } - - private Node functionCall( Ary args, Lexer site ) { - // Dead into the call? Skip all the node gen - if( ctrl()._type == Type.XCONTROL ) { - for( Node arg : args ) - if( arg.isUnused() ) - arg.kill(); - return con(Type.TOP); - } - - // Into the call - CallNode call = (CallNode)new CallNode(site, args.asAry()).peephole(); - // Post-call setup - CallEndNode cend = (CallEndNode)new CallEndNode(call,TypeRPC.constant(_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()); - // Memory from CallEnd - Node mem = new ProjNode(cend,1,ScopeNode.MEM0).peephole(); - mem(mem); - // Call result - return new ProjNode(cend.unkeep(),2,"#2").peephole(); - } - - // Just after parsing "type foo = " can parse `"C"` - private boolean isExternDecl( ) { - int old = pos(); - String s = parseString(); - if( "C".equals(s) ) return true; - 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 = _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)); - } - - /** - * Parse integer literal - * - * 
-     *     integerLiteral: [1-9][0-9]* | [0]
-     *     floatLiteral: [digits].[digits]?[e [digits]]?[f]?
-     *
- */ - private ConstantNode parseLiteral() { return con(_lexer.parseNumber()); } - ConstantNode con( long con ) { return _code.con(con); } - ConstantNode con( Type t ) { return _code.con(t ); } - private void classInit(Lexer site, Node ptr) { - // Ordinary load machinery resolves the flag alias and offset when - // the receiver is still a forward reference. - Field flag = ptr._type instanceof TypeMemPtr tmp ? tmp._obj.field("$init") : null; - int alias = flag==null ? 1 : flag._alias; - Node ready = new LoadNode(site,"$init",alias,null,mem(),ptr,fldoff(ptr,"$init")).peephole(); - CLInitNode init = new CLInitNode(site,ctrl(),mem(),ptr,ready).peephole().keep(); - ctrl(new CProjNode(init,0,ScopeNode.CTRL).peephole()); - Node bulk = new ProjNode(init,1,ScopeNode.MEM0).peephole().keep(); - flag = init.flag(); - mem(flag==null ? bulk : mergeAlias(bulk,flag._alias, - new ProjNode(init,2,memName(flag._alias)).peephole())); - bulk.unkeep(); - init.unkeep(); - } - - // Field offset for a known type (but unknown offset) - public static ConFldOffNode off( TypeStruct ts, String fname ) { - return (ConFldOffNode)(new ConFldOffNode(ts,fname).peephole()); - } - // Field offset for an unknown type - public Node fldoff( Node n, String name ) { - if( n._type instanceof TypeMemPtr ptr && ptr._obj._fref ) - _requiredTypes.add(ptr._obj._name); - return new FldOffNode(n,name,loc()).peephole(); - } - public Node peep( Node n ) { - // Peephole, then improve with lexically scoped guards - return _scope.upcastGuard(n.peephole()); - } - - // Parse a string or null - private String parseString() { - if( !peek('"') ) return null; - _lexer.inc(); - StringBuilder sb = new StringBuilder(); - while( !_lexer.isEOF() ) { - char c = _lexer.nextChar(); - if( c=='"' ) return sb.toString(); - if( c!='\\' ) { - sb.append(c); - continue; - } - if( _lexer.isEOF() ) - throw error("Unclosed string"); - sb.append(escapedChar("string")); - } - throw error("Unclosed string"); - } - - private char escapedChar(String kind) { - char esc = _lexer.nextChar(); - return switch( esc ) { - case '0' -> '\u0000'; - case 'n' -> '\n'; - case 't' -> '\t'; - case 'r' -> '\r'; - case '\\' -> '\\'; - case '"' -> '"'; - case '\'' -> '\''; - default -> throw error("Unknown "+kind+" escape \\\\"+esc); - }; - } - - // Already parsed "'" - private Node parseChar() { - if( _lexer.isEOF() ) throw error("Unclosed character"); - char c = _lexer.nextChar(); - if( c=='\\' ) { - if( _lexer.isEOF() ) throw error("Unclosed character"); - c = escapedChar("character"); - } - return require(con(TypeInteger.constant(c)),"'"); - } - - private boolean noLowerCase(String s) { - for( int i=0; i N require(N n, String syntax) { - if (match(syntax)) return n; - throw errorSyntax(syntax); - } - - //////////////////////////////////// - // Lexer components - - // 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 static class Lexer { - - // Input buffer; an array of text bytes read from a file or a string - private final byte[] _input; - public final CompUnit _cu; // Original source, retained across inlining. - // Tracks current position in input buffer - private int _position = 0; - - // - private int _line_number = 1; - // Start of current line - private int _line_start = 0; - - /** True when this location precedes {@code that} in the same source. */ - public boolean before(Lexer that) { - return that != null && (_cu!=null ? _cu==that._cu : _input==that._input) && _position < that._position; - } - - public String position() { return _line_number+":"+(_position-_line_start+1); } - public int pos() { return _position; } - - /** - * Record the source text for lexing - */ - public Lexer(String source) { - this(source.getBytes()); - } - - /** - * Direct from disk file source - */ - public Lexer(byte[] buf) { - _input = buf; - _cu = null; - } - - private Lexer(CompUnit cu) { - _input = cu._src.getBytes(); - _cu = cu; - } - - // Imported location: source text is only needed when reporting an error. - private Lexer(CompUnit cu, int pos) { - _input = null; - _cu = cu; - _position = pos; - } - - - public static void gather(Lexer loc, HashMap strs) { - if( loc==null || loc._cu==null ) return; - Serialize.gather(strs,loc._cu._cname); - String file=loc._cu.sourceFile(); - if( file!=null ) Serialize.gather(strs,file); - } - - public static void packed(Lexer loc, BAOS out, HashMap strs) { - if( loc==null || loc._cu==null ) { out.packed4(0); return; } - out.packed4(loc._position+1); - out.packed4(strs.get(loc._cu._cname)); - String file=loc._cu.sourceFile(); - out.packed4(file==null ? 0 : strs.get(file)); - } - - public static Lexer unpack(BAOS in, String[] strs) { - int pos=in.packed4(); - if( pos==0 ) return null; - String owner=strs[in.packed4()]; - String file=strs[in.packed4()]; - CompUnit cu=CodeGen.CODE._compunits.get(owner.replace('.','/')); - assert cu!=null : owner; - if( !file.isEmpty() ) cu._sourceFile=file; - return new Lexer(cu,pos-1); - } - - /** - * Copy a lexer from a lexer - */ - private 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 - private boolean isEOF() { - return _position >= _input.length; - } - - // Peek next character, or report EOF - private 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 - */ - private void skipWhiteSpace() { - while( true ) { - if( isWhiteSpace() ) inc(); - // Skip // to end of line - else if( _position+2 < _input.length && - _input[_position ] == '/' && - _input[_position+1] == '/') { - inc(); inc(); - while( !isEOF() && _input[_position] != '\n' ) - inc(); - } else if( _position+2 < _input.length && - _input[_position ] == '/' && - _input[_position+1] == '*') { - // Skip /*comment*/ - while( !isEOF() && !(_input[_position-1] == '*' && _input[_position] == '/')) - inc(); - inc(); - } else break; - } - } - - // Next non-white-space character, or EOF - public char nextXChar() { skipWhiteSpace(); return nextChar(); } - - // 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; - } - - private 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 - private Type parseNumber() { - int old = _position; - int len = isLongOrDouble(); - boolean f32 = peek()=='f'; - if( f32 ) nextChar(); - int n = Math.abs(len); - if( f32 ) - return TypeFloat.constant(Float.parseFloat(new String(_input,old,n))); - if( len > 0 ) { - if( len > 1 && _input[old]=='0' ) - throw error("Syntax error: integer values cannot start with '0'",this); - long i = Long.parseLong(new String(_input,old,len)); - return TypeInteger.constant(i); - } - return TypeFloat.constant(Double.parseDouble(new String(_input,old,n))); - } - private String parseNumberString() { - int old = _position; - int len = Math.abs(isLongOrDouble()); - if( peek()=='f' ) { - nextChar(); - len++; - } - return new String(_input,old,len); - } - - // Return +len that ends a long - // Return -len that ends a double - private int isLongOrDouble() { - int old = _position; - char c; - while( Character.isDigit(c=nextChar()) ) ; - if( !(c=='e' || c=='.') ) - return --_position - old; - if( peek() == '-' ) nextChar(); - while( Character.isDigit(c=nextChar()) || c=='e' || c=='.' ) ; - return -(--_position - old); - } - - // First letter of an identifier - private boolean isIdStart(char ch) { - return Character.isAlphabetic(ch) || ch == '_'; - } - - // All characters of an identifier, e.g. "_x123" - private boolean isIdLetter(char ch) { - return Character.isLetterOrDigit(ch) || ch == '_'; - } - - private String parseId() { - int start = _position; - while (isIdLetter(nextChar())) ; - return new String(_input, start, --_position - start).intern(); - } - - // - private boolean isPunctuation(char ch) { - return "=;[]<>()+-/*&|^".indexOf(ch) != -1; - } - - private String parsePunctuation() { - int start = _position; - return new String(_input, start, 1); - } - - // Next oper= character, or 0. - // As a convenience, mark "++" as a char 1 and "--" as char -1 (65535) - // Distinct tags for the multi-character compound operators. - static final char SHL = 2, SAR = 3, SHR = 4; - - public char matchOperAssign() { - skipWhiteSpace(); - if( match("<<=" ) ) return SHL; - if( match(">>>=") ) return SHR; - if( match(">>=" ) ) return SAR; - if( _position+2 >= _input.length ) return 0; - char ch0 = (char)_input[_position]; - if( "+-/*&|^".indexOf(ch0) == -1 ) return 0; - char ch1 = (char)_input[_position+1]; - if( ch1 == '=' ) { _position += 2; return ch0; } - if( isIdLetter((char)_input[_position+2]) ) return 0; - if( ch0 == '+' && ch1 == '+' ) { _position += 2; return (char) 1; } - if( ch0 == '-' && ch1 == '-' ) { _position += 2; return (char)-1; } - return 0; - } - } - - ParseException errorSyntax(String syntax) { return _errorSyntax("expected `"+syntax+"`"); } - private ParseException _errorSyntax(String msg) { - return error("Syntax error, "+msg+" but found `" + _lexer.getAnyNextToken()+"`"); - } - ParseException error(String msg) { return error(msg,_lexer); } - public static ParseException error(String msg, Lexer loc) { return new ParseException(msg,loc); } - - public static class ParseException extends RuntimeException { - public final Lexer _loc; - // file:line:charoff err - //String msg = "src:"+_line_number+":"+(_position-_line_start)+" "+errorMessage; - ParseException( String msg, Lexer loc ) { super(msg); _loc = loc; } - } - -} diff --git a/src/main/java/com/seaofnodes/simple/README.md b/src/main/java/com/seaofnodes/simple/README.md new file mode 100644 index 00000000..613f66b4 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/README.md @@ -0,0 +1,15 @@ +# Compiler source layout + +| Directory | Contents | +| --- | --- | +| `parser/` | Recursive-descent grammar routines, lexing, name resolution, and construction of the initial IR. `Var` describes a lexical binding. See the [grammar map](../../../../../../docs/chapter29/29-grammar.md). | +| `node/` | Sea-of-Nodes IR nodes: graph edges, type computation, and local peephole rewrites. | +| `node/cpus/` | Machine-specific nodes and instruction selection support for `arm`, `riscv`, and `x86_64_v2`. | +| `codegen/` | Compilation driver and passes: module loading, optimization, scheduling, register allocation, serialization, and machine-code emission. `IterPeeps` runs the peephole worklist. | +| `type/` | The type lattice, type interning, and representations of values, structs, functions, and memory. | +| `print/` | IR/assembly printers and adapters for the shared graph viewer. | +| `util/` | General-purpose collections, bit sets, byte buffers, and other small utilities. | + +The root package retains `sys.java`, which loads the default Simple namespace. +Java tests, the command-line driver, and the IR evaluator live under +`src/test/java`; the Simple standard library lives under `src/main/smp`. diff --git a/src/main/java/com/seaofnodes/simple/Var.java b/src/main/java/com/seaofnodes/simple/Var.java deleted file mode 100644 index af371d21..00000000 --- a/src/main/java/com/seaofnodes/simple/Var.java +++ /dev/null @@ -1,54 +0,0 @@ -package com.seaofnodes.simple; - -import com.seaofnodes.simple.type.*; -import com.seaofnodes.simple.util.Utils; - - -/** - * The tracked fields are now complex enough to deserve a array-of-structs layout - */ -public class Var { - - public final String _name; // Declared name - // These fields are not final for forward reference late updates or - // promotions. - public int _idx; // index in containing scope - private Type _type; // Declared type - public boolean _final; // Final field - public boolean _fref; // Forward ref - // Parser-only definite-initialization marker. The current binding's - // nullable type carries the path-sensitive state through SSA merges. - public boolean _uninit; - public int _extern; // C storage alias; zero for ordinary variables - public Parser.Lexer _loc; // Source location - - public Var(int idx, String name, Type type, boolean xfinal, Parser.Lexer loc ) { - this(idx,name,type,xfinal,loc,false); - } - public Var(int idx, String name, Type type, boolean xfinal, Parser.Lexer loc, boolean fref) { - _idx = idx; - _name = name; - _type = type; - _final = xfinal; - _fref = fref; - _loc = loc; - } - public Type type() { return _type; } - public Type _type() { return _type; } // ScopeNode printer needs to have no side effects - - // Forward reference variables (not types) must be BOTTOM and - // distinct from inferred variables - public boolean isFRef() { return _fref; } - - public void defFRef( Type type, boolean xfinal, Parser.Lexer loc ) { - assert isFRef() && xfinal; - _type = type; - _final = true; - _fref = false; - _loc = loc; - } - - @Override public String toString() { - return (_fref ? "FREF " : "")+(_uninit ? "UNINIT " : "")+_type.toString()+(_final ? " ": " !")+_name; - } -} diff --git a/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java b/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java index 9a544685..3547b86c 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java +++ b/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.codegen; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Lexer; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.*; @@ -76,7 +77,7 @@ public class ClassInitDependencies { // Return the outgoing init edge set for this function private static int[] walk( CodeGen code, FunNode fun, Ary work, IntHashMap iset, BitSet visit, - Ary sites) { + Ary sites) { if( fun.summary()!=null ) return fun.summary()._classDependencyFIDXs; // Walk function body, looking for outgoing init edges assert iset .isEmpty(); // int hash set for de-dup @@ -164,7 +165,7 @@ public class ClassInitDependencies { Ary work = new Ary<>(CFGNode.class); IntHashMap iset = new IntHashMap(0); BitSet visit = new BitSet(); - Ary sites = new Ary<>(Parser.Lexer.class); + Ary sites = new Ary<>(Lexer.class); for( int i=idx; i<_sp; i++ ) { int src = _stk[i]; FunNode fun = _code.link(src); @@ -175,7 +176,7 @@ public class ClassInitDependencies { for( int dst : _edgess[src] ) if( members.get(dst) ) { sb.p("\n ").p(name(src)).p(" -> ").p(name(dst)); - Parser.Lexer loc = sites.atX(dst); + Lexer loc = sites.atX(dst); if( loc!=null && loc._cu!=null ) sb.p('\n').p(SourceError.format(loc._cu,loc.pos(),"cyclic class initialization")); else if( fun!=null && fun.isClz() && dst!=0 && fun._compunit._par==_code.link(dst)._compunit ) diff --git a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 67176710..bdb510b4 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -1,8 +1,7 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.graph.GraphObserver; -import com.seaofnodes.simple.IterPeeps; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.print.*; import com.seaofnodes.simple.type.*; diff --git a/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java b/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java index 8b303008..2b091b3c 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java +++ b/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java @@ -1,6 +1,6 @@ package com.seaofnodes.simple.codegen; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeStruct; diff --git a/src/main/java/com/seaofnodes/simple/codegen/Encoding.java b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java index 067f431a..8b868218 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/Encoding.java +++ b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java @@ -1,6 +1,6 @@ package com.seaofnodes.simple.codegen; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.print.IRPrinter; import com.seaofnodes.simple.type.*; diff --git a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index a1ac4e67..86cb2e98 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -1,6 +1,6 @@ package com.seaofnodes.simple.codegen; -import com.seaofnodes.simple.IterPeeps.WorkList; +import com.seaofnodes.simple.codegen.IterPeeps.WorkList; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; diff --git a/src/main/java/com/seaofnodes/simple/codegen/IterPeeps.java b/src/main/java/com/seaofnodes/simple/codegen/IterPeeps.java new file mode 100644 index 00000000..543a69df --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/codegen/IterPeeps.java @@ -0,0 +1,349 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.node.*; +import java.util.Arrays; +import java.util.BitSet; +import java.util.IdentityHashMap; +import java.util.Random; + +/** + * The IterPeeps runs after parsing. It iterates the peepholes to a fixed point + * so that no more peepholes apply. This should be linear because peepholes rarely + * (never?) increase code size. The graph should monotonically reduce in some + * dimension, which is usually size. It might also reduce in e.g. number of + * MulNodes or Load/Store nodes, swapping out more "expensive" Nodes for cheaper + * ones. + *
+ * The theoretical overall worklist is mindless just grabbing the next thing and + * doing it. If the graph changes, put the neighbors on the worklist. + *
+ * Lather, Rinse, Repeat until the worklist runs dry. + *

+ * The main issues we have to deal with: + * + *

    + *
  • Nodes have uses; replacing some set of Nodes with another requires more graph + * reworking. Not rocket science, but it can be fiddly. Its helpful to have a + * small set of graph munging utilities, and the strong invariant that the graph + * is stable and correct between peepholes. In our case `Node.subsume` does + * most of the munging, building on our prior stable Node utilities.
    • + * + *
  • Changing a Node also changes the graph "neighborhood". The neighbors need to + * be checked to see if THEY can also peephole, and so on. After any peephole + * or graph update we put a Nodes uses and defs on the worklist.
    • + * + *
  • Our strong invariant is that for all Nodes, either they are on the worklist + * OR no peephole applies. This invariant is easy to check, although expensive. + * Basically the normal "iterate peepholes to a fixed point" is linear, and this + * check is linear at each peephole step... so quadratic overall. It's a useful + * assert, but one we can disable once the overall algorithm is stable - and + * then turn it back on again when some new set of peepholes is misbehaving. + * The code for this is turned on in `IterPeeps.iterate` as `assert + * progressOnList(stop);`
    • + *
+ */ +public class IterPeeps { + + public final WorkList _work; + final WorkList _workInline; + private int _cnt; + + public IterPeeps( long seed ) { + _work = new WorkList<>(seed); + _workInline = new WorkList<>(seed); + } + + @SuppressWarnings("unchecked") + public N add( N n ) { return (N)_work.push(n); } + + public void addAll( Ary ary ) { _work.addAll(ary); } + + /** + * Iterate peepholes and inlining to a fixed point + */ + public void iterate( CodeGen code ) { + boolean didInline = false; + Ary defer = new Ary<>(Node.class); + while( true ) { + // Clean up everything that does not grow the code + iteratePeeps(code); + + // Pick an inline candidate, no real heuristic, first come, first served + boolean inlined = false; + CallEndNode cend; + while( (cend = _workInline.pop()) != null) { + if( cend.isDead() ) continue; + if( cend.loadForInline() ) { inlined = true; break; } + byte inline = cend.maybeInline(); + if( inline == -1 ) defer.add(cend); + if( inline > 0 ) { + inlined = true; + break; + } + } + // Inlined, run peeps until clean again + if( inlined ) { didInline = true; continue; } + // No more candidates, check the defer list + if( !didInline ) break; // No more progress, so all the "maybe inline after cleanup" do not progress + // Some inlining happened, retry all the "try again after cleanup" calls + didInline = false; + code.addAll(defer); + defer.clear(); + } + } + + // Run all the code-reduction and type-lifting peeps as possible + private void iteratePeeps( CodeGen code ) { + assert !CodeGen.expensiveAssert(0) || (progressOnList(code, _work) && schedulableUses(code)); + + Node n; + while( (n = _work.pop()) != null ) { + if( n.isDead() ) continue; + _cnt++; // Useful for debugging, searching which peephole broke things + var obs = code._obs; // Collect peephole neighbors for graph display + if( obs != null ) obs.before(n); + Node x = n.peepholeOpt(); + if( n instanceof CallEndNode cend ) + _workInline.push(cend); + if( x != null ) { + assert !x.isDead(); // Peepholes return alive answers + // peepholeOpt can return brand-new nodes, needing an initial type set + if( x._type==null ) x.setType(x.compute()); + // Changes require neighbors onto the worklist + if( x != n || !(x instanceof ConstantNode) ) { + // All outputs of n (changing node) not x (prior existing node). + for( Node z : n._outputs ) _work.push(z); + // Everybody gets a free "go again" in case they didn't get + // made in their final form. + _work.push(x); + // A self-returning peephole can have rewritten its input + // edges. The new defs gained a user and may have + // backwards, user-sensitive peepholes of their own. + for( Node z : x._inputs ) _work.push(z); + // If the result is not self, revisit all inputs (because + // there's a new user), and replace in the graph. + if( x != n ) { + //for( Node z : n. _inputs ) _work.push(z); + for( Node z : x._outputs ) _work.push(z); + n.subsume(x); + } + } + // If there are distant neighbors, move to worklist + n.moveDepsToWorklist(); + // Very expensive assert. + assert !CodeGen.expensiveAssert(_cnt) || (progressOnList(code, _work) && schedulableUses(code)); + } + boolean unused = n.isUnused(); + if( unused ) { + assert !(n instanceof StopNode); // StopNodes can die if all code in the compunit dies + n.kill(); // Just plain dead + } + if( obs != null ) obs.after(n, x!=null ? x : unused ? n : null, true); + } + assert !CodeGen.expensiveAssert(0) || schedulableUses(code); + + } + + // Visit ALL nodes and confirm the invariant: + // Either you are on the _work worklist OR running `iter()` makes no progress. + + // This invariant ensures that no progress is missed, i.e., when the + // worklist is empty we have indeed done all that can be done. To help + // with debugging, the {@code assert} is broken out in a place where it is easy to + // stop if a change is found. + + // Also, the normal usage of `iter()` may attempt peepholes with distance + // neighbors and these should fail, but will then try to add dependencies + // {@link #Node.addDep} which is a side effect in an assert. The {@link + // #midAssert} is used to stop this side effect. + // Pessimistic solver assert + public static boolean progressOnList(CodeGen code, WorkList list ) { + code._midAssert = true; + Node changed = code._stop.walk( n -> { + // Ignore most in-progress things + if( n.iskeep() ) return null; + // Types must be forwards, even if on the worklist. + Type nval = n.compute(); + assert nval.isa(n._type) : "Non-monotonic peep: "+n+"#"+n._nid+" old="+n._type+" new="+nval+" inputs="+inputTypes(n)+" peep="+n; + if( list.on(n) ) + return null; // On worklist is ok! + if( n instanceof CallEndNode cend ) { + if( code._iter._workInline.on(cend) ) + return null; // On inline worklist is ok! + assert cend.maybeInline() <= 0 : "Inline fired and not on worklist, CallEndNode#"+cend._nid; + } + // Off list: must be live, in GVN table, and no peeps. + assert n.nOuts() > 0 : "Unused live node: "+n; + assert code._gvn.get(n)==n : "Not in GVN table: "+n; + Node m = n.peepholeOpt(); + assert m==null : "Peep fired and not on worklist, "+n.getClass().getSimpleName()+"#"+n._nid+" -> "+m; + return m; + }); + code._midAssert = false; + return changed==null; + } + + private static String inputTypes(Node n) { + StringBuilder sb = new StringBuilder("["); + for( Node in : n._inputs ) + sb.append(in==null ? "null" : in.getClass().getSimpleName()+"#"+in._nid+"="+in+":"+in._type+":keep="+in.iskeep()).append(','); + return sb.append(']').toString(); + } + + // GCM assumes every movable node can be placed no earlier than its inputs + // and no later than the LCA of its uses. Catch graphs where a use escapes + // above an input-defined branch before the later scheduling pass walks off + // the top of the idom tree. + private static final IdentityHashMap earlyCache = new IdentityHashMap<>(); + private static final BitSet VISIT = new BitSet(); + public static boolean schedulableUses(CodeGen code) { + earlyCache.clear(); + Node bad = code._stop.walk( n -> { + if( n.iskeep() || n.isDead() || n.isConst() || + n instanceof CFGNode || n instanceof PhiNode || n instanceof ProjNode ) + return null; + assert VISIT.isEmpty(); + CFGNode early = CFGNode.earlyCFG(n,earlyCache,VISIT); + VISIT.clear(); + if( early == null ) return null; + CFGNode lca = null; + for( Node use : n._outputs ) { + CFGNode ublk = useBlock(n,use); + if( ublk != null ) + lca = ublk.domLCA(lca,null); + } + if( lca == null ) return null; + if( !early.sameFun(lca) ) return null; + assert early.dominates(lca,null) : badSchedule(n,early,lca); + return null; + }); + return bad == null; + } + + private static CFGNode useBlock(Node n, Node use) { + if( use == null ) + return null; + if( use instanceof PhiNode phi ) { + CFGNode found = null; + for( int i = 1; i= phi.region().nIns() ) + return null; + found = phi.region().cfg(i).domLCA(found,null); + } + return found; + } + return CFGNode.safeCFG(use); + } + + private static String badSchedule(Node n, CFGNode early, CFGNode lca) { + StringBuilder sb = new StringBuilder("Unschedulable data node ") + .append(n.getClass().getSimpleName()).append('#').append(n._nid) + .append(" early=").append(cfg(early)) + .append(" use-lca=").append(cfg(lca)) + .append(" node=").append(n).append("\ninputs:"); + for( int i = 0; i { + + private Node[] _es; + private int _len; + private final BitSet _on; // Bit set if Node._nid is on WorkList + private final Random _R; // For randomizing pull from the WorkList + private final long _seed; + + /* Useful stat - how many nodes are processed in the post parse iterative opt */ + private long _totalWork = 0; + + public WorkList() { this(123); } + WorkList(long seed) { + _es = new Node[1]; + _len=0; + _on = new BitSet(); + _seed = seed; + _R = new Random(); + _R.setSeed(_seed); + } + + /** + * Pushes a Node on the WorkList, ensuring no duplicates + * If Node is null it will not be added. + */ + public E push( E x ) { + if( x==null ) return null; + int idx = x._nid; + if( !_on.get(idx) ) { + _on.set(idx); + if( _len==_es.length ) + _es = Arrays.copyOf(_es,_len<<1); + _es[_len++] = x; + _totalWork++; + } + return x; + } + + public void addAll( Ary ary ) { + for( E n : ary ) + push(n); + } + public void addAll( E[] es ) { + for( E n : es ) + push(n); + } + + + /** + * True if Node is on the WorkList + */ + public boolean on( E x ) { return _on.get(x._nid); } + + /** + * Removes a random Node from the WorkList; null if WorkList is empty + */ + public E pop() { + if( _len == 0 ) return null; + int idx = _R.nextInt(_len); + E x = (E)_es[idx]; + _es[idx] = _es[--_len]; // Compress array + _es[_len] = null; + _on.clear(x._nid); + return x; + } + + public boolean isEmpty() { return _len==0; } + public void clear() { + Arrays.fill(_es,0,_len,null); + _len = 0; + _on.clear(); + _R.setSeed(_seed); + _totalWork = 0; + } + } +} diff --git a/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java b/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java index 3b1d3182..c3b603e5 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java +++ b/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java @@ -1,6 +1,6 @@ package com.seaofnodes.simple.codegen; -import com.seaofnodes.simple.IterPeeps.WorkList; +import com.seaofnodes.simple.codegen.IterPeeps.WorkList; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; diff --git a/src/main/java/com/seaofnodes/simple/codegen/Opto.java b/src/main/java/com/seaofnodes/simple/codegen/Opto.java index 511e0027..aa997204 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/Opto.java +++ b/src/main/java/com/seaofnodes/simple/codegen/Opto.java @@ -1,7 +1,7 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.node.*; -import com.seaofnodes.simple.IterPeeps.WorkList; +import com.seaofnodes.simple.codegen.IterPeeps.WorkList; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; diff --git a/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java b/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java index 1d9731fc..1218c956 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java +++ b/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple.codegen; -import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.print.*; import com.seaofnodes.simple.type.*; diff --git a/src/main/java/com/seaofnodes/simple/codegen/Serialize.java b/src/main/java/com/seaofnodes/simple/codegen/Serialize.java index 98350a95..76829151 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/Serialize.java +++ b/src/main/java/com/seaofnodes/simple/codegen/Serialize.java @@ -1,6 +1,6 @@ package com.seaofnodes.simple.codegen; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.*; diff --git a/src/main/java/com/seaofnodes/simple/codegen/StaticData.java b/src/main/java/com/seaofnodes/simple/codegen/StaticData.java index a4147576..f813fab5 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/StaticData.java +++ b/src/main/java/com/seaofnodes/simple/codegen/StaticData.java @@ -1,6 +1,6 @@ package com.seaofnodes.simple.codegen; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.BAOS; diff --git a/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java b/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java index a5eaa5ca..c9e53311 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java +++ b/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java @@ -1,6 +1,6 @@ package com.seaofnodes.simple.codegen; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.util.Ary; diff --git a/src/main/java/com/seaofnodes/simple/node/AndNode.java b/src/main/java/com/seaofnodes/simple/node/AndNode.java index f02007bc..a1c6bba1 100644 --- a/src/main/java/com/seaofnodes/simple/node/AndNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AndNode.java @@ -1,11 +1,12 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Lexer; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; public class AndNode extends ArithNode { - public AndNode(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs, (byte)1); } + public AndNode(Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs, (byte)1); } @Override public Tag serialTag() { return Tag.And; } @Override public String op() { return "&"; } diff --git a/src/main/java/com/seaofnodes/simple/node/ArithNode.java b/src/main/java/com/seaofnodes/simple/node/ArithNode.java index e2a88944..16e9ec8d 100644 --- a/src/main/java/com/seaofnodes/simple/node/ArithNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ArithNode.java @@ -1,8 +1,9 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.parser.Lexer; import com.seaofnodes.print.ExprPrinter; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.BAOS; @@ -13,12 +14,12 @@ import java.util.IdentityHashMap; public abstract class ArithNode extends Node implements ModeNode { // Source location for late reported errors - Parser.Lexer _loc; + Lexer _loc; // Mode is 0 for unknown, 1 for int, 2 for flt byte _mode; - public ArithNode( Parser.Lexer loc, Node lhs, Node rhs) { super(null, lhs, rhs); _loc = loc; } - public ArithNode( Parser.Lexer loc, Node lhs, Node rhs, byte mode) { this(loc,lhs,rhs); _mode=mode; } + public ArithNode( Lexer loc, Node lhs, Node rhs) { super(null, lhs, rhs); _loc = loc; } + public ArithNode( Lexer loc, Node lhs, Node rhs, byte mode) { this(loc,lhs,rhs); _mode=mode; } @Override public void packed(BAOS baos, HashMap strs, HashMap types, IdentityHashMap anodes) { baos.packed1(_mode); } @@ -65,7 +66,7 @@ public abstract class ArithNode extends Node implements ModeNode { // Check that a settled mode agrees with all data inputs. Takes the Node // instead of a varargs list both to avoid allocation and to keep this ready // to become shared mode-aware Node behavior later. - static Parser.ParseException nodeErr(Node n, Parser.Lexer loc, String op, byte mode, boolean allowFloat) { + static Parser.ParseException nodeErr(Node n, Lexer loc, String op, byte mode, boolean allowFloat) { Type bad = null; for( int i=1; i strs, HashMap types, IdentityHashMap anodes ) { - Parser.Lexer.packed(_loc,baos,strs); + Lexer.packed(_loc,baos,strs); } - @Override public void gather(HashMap strs) { Parser.Lexer.gather(_loc,strs); } + @Override public void gather(HashMap strs) { Lexer.gather(_loc,strs); } public CLInitNode(CLInitNode init) { super(init); diff --git a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index b7b26265..4056e24e 100644 --- a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -2,7 +2,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.BAOS; diff --git a/src/main/java/com/seaofnodes/simple/node/CallNode.java b/src/main/java/com/seaofnodes/simple/node/CallNode.java index 29d4f6aa..fcadd0e4 100644 --- a/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -1,8 +1,9 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.parser.Lexer; import com.seaofnodes.print.ExprPrinter; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.codegen.Iter; import com.seaofnodes.simple.type.Type; @@ -21,9 +22,9 @@ import java.util.IdentityHashMap; public class CallNode extends CFGNode { // Source location for late reported errors - public final Parser.Lexer _loc; + public final Lexer _loc; - public CallNode(Parser.Lexer loc, Node... nodes) { + public CallNode(Lexer loc, Node... nodes) { super(nodes); _loc = loc; CodeGen.CODE._calls.add(this); @@ -33,12 +34,12 @@ public class CallNode extends CFGNode { @Override public Tag serialTag() { return Tag.Call; } public void packed( BAOS baos, HashMap strs, HashMap types, IdentityHashMap anodes ) { baos.packed1(nIns()); - Parser.Lexer.packed(_loc,baos,strs); + Lexer.packed(_loc,baos,strs); } - @Override public void gather(HashMap strs) { Parser.Lexer.gather(_loc,strs); } + @Override public void gather(HashMap strs) { Lexer.gather(_loc,strs); } static Node make( BAOS bais, String[] strs ) { int nIns = bais.packed1(); - return new CallNode(Parser.Lexer.unpack(bais,strs),new Node[nIns]); + return new CallNode(Lexer.unpack(bais,strs),new Node[nIns]); } @Override protected ExprPrinter _print1(ExprPrinter p) { diff --git a/src/main/java/com/seaofnodes/simple/node/ConFldOffNode.java b/src/main/java/com/seaofnodes/simple/node/ConFldOffNode.java index 284220ea..cb99b4dd 100644 --- a/src/main/java/com/seaofnodes/simple/node/ConFldOffNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ConFldOffNode.java @@ -2,7 +2,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; diff --git a/src/main/java/com/seaofnodes/simple/node/ConvertNode.java b/src/main/java/com/seaofnodes/simple/node/ConvertNode.java index 7f5398ef..a969fb4e 100644 --- a/src/main/java/com/seaofnodes/simple/node/ConvertNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ConvertNode.java @@ -2,7 +2,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.type.*; import java.util.HashMap; diff --git a/src/main/java/com/seaofnodes/simple/node/CtrlNode.java b/src/main/java/com/seaofnodes/simple/node/CtrlNode.java index 62140873..277e03dc 100644 --- a/src/main/java/com/seaofnodes/simple/node/CtrlNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CtrlNode.java @@ -3,7 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.codegen.CodeGen; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.type.Type; public class CtrlNode extends CFGNode { diff --git a/src/main/java/com/seaofnodes/simple/node/FRefNode.java b/src/main/java/com/seaofnodes/simple/node/FRefNode.java index 644f1434..3906f7be 100644 --- a/src/main/java/com/seaofnodes/simple/node/FRefNode.java +++ b/src/main/java/com/seaofnodes/simple/node/FRefNode.java @@ -1,9 +1,10 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.parser.Lexer; import com.seaofnodes.print.ExprPrinter; -import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.Var; +import com.seaofnodes.simple.parser.Parser; +import com.seaofnodes.simple.parser.Var; import com.seaofnodes.simple.type.Type; /** @@ -22,10 +23,10 @@ import com.seaofnodes.simple.type.Type; public class FRefNode extends ConstantNode { public static final Type FREF_TYPE = Type.BOTTOM; public String _name; - public final Parser.Lexer _loc; // Source location + public final Lexer _loc; // Source location - public FRefNode( String name, Parser.Lexer loc ) { this(name,loc,FREF_TYPE); } - public FRefNode( String name, Parser.Lexer loc, Type type ) { + public FRefNode( String name, Lexer loc ) { this(name,loc,FREF_TYPE); } + public FRefNode( String name, Lexer loc, Type type ) { super(type); _name = name; _loc = loc; diff --git a/src/main/java/com/seaofnodes/simple/node/FldOffNode.java b/src/main/java/com/seaofnodes/simple/node/FldOffNode.java index a9f8d692..223ca79e 100644 --- a/src/main/java/com/seaofnodes/simple/node/FldOffNode.java +++ b/src/main/java/com/seaofnodes/simple/node/FldOffNode.java @@ -1,8 +1,9 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.parser.Lexer; import com.seaofnodes.print.ExprPrinter; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.SB; @@ -17,8 +18,8 @@ import java.util.HashMap; public class FldOffNode extends TypeNode { public final String _fname; // Field name - public final Parser.Lexer _loc; // - public FldOffNode( Node base, String fname, Parser.Lexer loc ) { super(TypeInteger.BOT,base); _fname = fname; _loc=loc; } + public final Lexer _loc; // + public FldOffNode( Node base, String fname, Lexer loc ) { super(TypeInteger.BOT,base); _fname = fname; _loc=loc; } @Override public Tag serialTag() { throw Utils.TODO("should not reach here"); } @Override public String label() { diff --git a/src/main/java/com/seaofnodes/simple/node/FunNode.java b/src/main/java/com/seaofnodes/simple/node/FunNode.java index 6a8d5d50..d76d80b5 100644 --- a/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Lexer; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.BAOS; @@ -27,14 +28,14 @@ public class FunNode extends RegionNode { public CompUnit _compunit; // Defined in source file public final boolean _extern; // External function; no code, name only - private FunNode( Parser.Lexer loc, Node[] nodes, TypeFunPtr sig, String name, CompUnit compunit, boolean ext ) { + private FunNode( Lexer loc, Node[] nodes, TypeFunPtr sig, String name, CompUnit compunit, boolean ext ) { super(loc,nodes); _name = name; _sig = sig; _extern = ext; _compunit = compunit; } - public FunNode( Parser.Lexer loc, TypeFunPtr sig, String name, CompUnit compunit, Node... nodes ) { this(loc,nodes,sig,name,compunit,false); } + public FunNode( Lexer loc, TypeFunPtr sig, String name, CompUnit compunit, Node... nodes ) { this(loc,nodes,sig,name,compunit,false); } public FunNode( FunNode fun ) { super( fun, fun._loc ); _sig = fun.sig(); diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java index c58bba39..9aa8b311 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -1,8 +1,9 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.parser.Lexer; import com.seaofnodes.print.ExprPrinter; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.codegen.GlobalBits; import com.seaofnodes.simple.type.*; @@ -24,7 +25,7 @@ public class LoadNode extends MemOpNode { * @param ptr The ptr to the struct base from where we load a field * @param off The offset inside the struct base */ - public LoadNode(Parser.Lexer loc, String name, int alias, Node ctrl, Node mem, Node ptr, Node off) { + public LoadNode(Lexer loc, String name, int alias, Node ctrl, Node mem, Node ptr, Node off) { super(loc, name, alias, true, Type.BOTTOM, ctrl, mem, ptr, off); } LoadNode( BAOS bais, String[] strs, Type[] types, GlobalBits fileAliases, GlobalBits aliases ) { diff --git a/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/src/main/java/com/seaofnodes/simple/node/LoopNode.java index 45f7a6fa..c4d55335 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Lexer; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMem; @@ -10,7 +11,7 @@ import java.util.HashMap; import java.util.IdentityHashMap; public class LoopNode extends RegionNode { - public LoopNode( Parser.Lexer loc, Node xctrl, Node entry ) { super(loc,xctrl,entry,null); } + public LoopNode( Lexer loc, Node xctrl, Node entry ) { super(loc,xctrl,entry,null); } public LoopNode( LoopNode loop ) { super(loop); } @Override public Tag serialTag() { return Tag.Loop; } public void packed( BAOS baos, HashMap strs, HashMap types, IdentityHashMap anodes ) { } diff --git a/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java index dfe8794d..aa3f6d57 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.parser.Var; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.*; diff --git a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index bfbd46c3..24ca6157 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -1,8 +1,9 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.parser.Lexer; import com.seaofnodes.print.ExprPrinter; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.codegen.GlobalBits; import com.seaofnodes.simple.type.*; @@ -40,16 +41,16 @@ public abstract class MemOpNode extends TypeNode { // Field name. public final String _name; // Source location for late reported errors - public final Parser.Lexer _loc; + public final Lexer _loc; - public MemOpNode(Parser.Lexer loc, String name, int alias, boolean isLoad, Type decl, Node ctrl, Node mem, Node ptr, Node off) { + public MemOpNode(Lexer loc, String name, int alias, boolean isLoad, Type decl, Node ctrl, Node mem, Node ptr, Node off) { super(decl, ctrl, mem, ptr, off); _name = name; _alias = alias; _loc = loc; _isLoad = isLoad; } - public MemOpNode(Parser.Lexer loc, String name, int alias, boolean isLoad, Type decl, Node ctrl, Node mem, Node ptr, Node off, Node value) { + public MemOpNode(Lexer loc, String name, int alias, boolean isLoad, Type decl, Node ctrl, Node mem, Node ptr, Node off, Node value) { this(loc, name, alias, isLoad, decl, ctrl, mem, ptr, off); addDef(value); } diff --git a/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 9c99fc6b..4f4343d4 100644 --- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -1,7 +1,7 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.Utils; diff --git a/src/main/java/com/seaofnodes/simple/node/NeverNode.java b/src/main/java/com/seaofnodes/simple/node/NeverNode.java index ba1dab8c..f7b5a58a 100644 --- a/src/main/java/com/seaofnodes/simple/node/NeverNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NeverNode.java @@ -2,7 +2,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeTuple; diff --git a/src/main/java/com/seaofnodes/simple/node/NewNode.java b/src/main/java/com/seaofnodes/simple/node/NewNode.java index fe80f690..d4df7a0b 100644 --- a/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NewNode.java @@ -1,7 +1,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.BAOS; diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 515b29f4..cbd35592 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -2,8 +2,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.BaseNode; -import com.seaofnodes.simple.IterPeeps; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.codegen.IterPeeps; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.codegen.GlobalBits; import com.seaofnodes.simple.print.IRPrinter; diff --git a/src/main/java/com/seaofnodes/simple/node/OrNode.java b/src/main/java/com/seaofnodes/simple/node/OrNode.java index 9d50d1a9..c7dcc75e 100644 --- a/src/main/java/com/seaofnodes/simple/node/OrNode.java +++ b/src/main/java/com/seaofnodes/simple/node/OrNode.java @@ -1,11 +1,12 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Lexer; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; public class OrNode extends ArithNode { - public OrNode( Parser.Lexer loc, Node lhs, Node rhs) { super(loc,lhs, rhs, (byte)1); } + public OrNode( Lexer loc, Node lhs, Node rhs) { super(loc,lhs, rhs, (byte)1); } @Override public Tag serialTag() { return Tag.Or; } @Override public String label() { return "Or"; } diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 3cf6f854..75d3ff13 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.*; diff --git a/src/main/java/com/seaofnodes/simple/node/PtrToIntNode.java b/src/main/java/com/seaofnodes/simple/node/PtrToIntNode.java index d3d38060..d528b53b 100644 --- a/src/main/java/com/seaofnodes/simple/node/PtrToIntNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PtrToIntNode.java @@ -1,7 +1,7 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.type.TypeMemPtr; diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 8883ba8e..8d0d56e9 100644 --- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -1,8 +1,9 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.parser.Lexer; import com.seaofnodes.print.ExprPrinter; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.util.BAOS; @@ -10,10 +11,10 @@ import java.util.*; public class RegionNode extends CFGNode { // Source location for late discovered errors - public Parser.Lexer _loc; + public Lexer _loc; - public RegionNode(Parser.Lexer loc, Node... nodes) { super(nodes); _loc = loc; } - public RegionNode(RegionNode r, Parser.Lexer loc) { super(r); _loc = loc; } + public RegionNode(Lexer loc, Node... nodes) { super(nodes); _loc = loc; } + public RegionNode(RegionNode r, Lexer loc) { super(r); _loc = loc; } public RegionNode(RegionNode r) { super(r); if( r!=null ) _loc = r._loc; } @Override public Tag serialTag() { return Tag.Region; } public void packed( BAOS baos, HashMap strs, HashMap types, IdentityHashMap anodes ) { baos.packed1(nIns()); } diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 311a7ea4..182adb19 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -2,7 +2,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.codegen.Encoding; import com.seaofnodes.simple.codegen.RegMask; diff --git a/src/main/java/com/seaofnodes/simple/node/SarNode.java b/src/main/java/com/seaofnodes/simple/node/SarNode.java index 737b531f..2e70f345 100644 --- a/src/main/java/com/seaofnodes/simple/node/SarNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SarNode.java @@ -1,11 +1,12 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Lexer; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; public class SarNode extends ArithNode { - public SarNode(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs, (byte)1); } + public SarNode(Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs, (byte)1); } @Override public Tag serialTag() { return Tag.Sar; } @Override public String op() { return ">>"; } diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 694d5dcb..ff3d8b4d 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -1,8 +1,9 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.parser.Lexer; import com.seaofnodes.print.ExprPrinter; -import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.Var; +import com.seaofnodes.simple.parser.Parser; +import com.seaofnodes.simple.parser.Var; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.codegen.CompUnit; import com.seaofnodes.simple.codegen.ParseAll; @@ -232,7 +233,7 @@ public class ScopeNode extends MemMergeNode { /** * Create a new variable name in the current scope */ - public boolean define( String name, Type declaredType, boolean xfinal, Node init, Parser.Lexer loc ) { + public boolean define( String name, Type declaredType, boolean xfinal, Node init, Lexer loc ) { assert _kinds.isEmpty() || name!=MEM0 ; // Later scopes do not define memory if( depth() > 0 ) for( int i=_vars.size()-1; i>=klast()._lexSize; i-- ) { @@ -260,7 +261,7 @@ public class ScopeNode extends MemMergeNode { // lexical scope. Scope pops promote it outwards "as if" the final constant // had been declared before the using scope. - public Var defineFRef( String id, Type t, boolean xfinal, Parser.Lexer loc ) { + public Var defineFRef( String id, Type t, boolean xfinal, Lexer loc ) { Var var = new Var(nIns(),id,t,xfinal,loc,true); FRefNode fref = new FRefNode(id,loc).init(); fref._type = fref._con = t; @@ -375,7 +376,7 @@ public class ScopeNode extends MemMergeNode { * @param that The ScopeNode to be merged into this * @return A new node representing the merge point */ - public RegionNode mergeScopes(ScopeNode that, Parser.Lexer loc) { + public RegionNode mergeScopes(ScopeNode that, Lexer loc) { RegionNode r = ctrl(new RegionNode(loc,null,ctrl(), that.ctrl()).keep()); this._merge(that,r); that.kill(); // Kill merged scope diff --git a/src/main/java/com/seaofnodes/simple/node/ShlNode.java b/src/main/java/com/seaofnodes/simple/node/ShlNode.java index f657cf51..fffc71f0 100644 --- a/src/main/java/com/seaofnodes/simple/node/ShlNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ShlNode.java @@ -1,12 +1,13 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Lexer; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; public class ShlNode extends ArithNode { - public ShlNode(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs, (byte)1); } + public ShlNode(Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs, (byte)1); } @Override public Tag serialTag() { return Tag.Shl; } @Override public String op() { return "<<"; } diff --git a/src/main/java/com/seaofnodes/simple/node/ShrNode.java b/src/main/java/com/seaofnodes/simple/node/ShrNode.java index e93ea0e8..1bf86f90 100644 --- a/src/main/java/com/seaofnodes/simple/node/ShrNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ShrNode.java @@ -1,11 +1,12 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Lexer; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; public class ShrNode extends ArithNode { - public ShrNode(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs, (byte)1); } + public ShrNode(Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs, (byte)1); } @Override public Tag serialTag() { return Tag.Shr; } @Override public String op() { return ">>>"; } diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java index a7ea4ac1..78bd8219 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -3,7 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.codegen.CodeGen; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Utils; import java.util.Arrays; diff --git a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 5fa0b99f..96e15a58 100644 --- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -1,5 +1,7 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.parser.Parser; +import com.seaofnodes.simple.parser.Lexer; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.*; @@ -29,10 +31,10 @@ public class StoreNode extends MemOpNode { * @param off The offset inside the struct base * @param value Value to be stored */ - public StoreNode(Parser.Lexer loc, String name, int alias, Type decl, Node ctrl, Node mem, Node ptr, Node off, Node value, boolean init) { + public StoreNode(Lexer loc, String name, int alias, Type decl, Node ctrl, Node mem, Node ptr, Node off, Node value, boolean init) { this(loc,name,alias,decl,ctrl,mem,ptr,off,value,init,(byte)0); } - private StoreNode(Parser.Lexer loc, String name, int alias, Type decl, Node ctrl, Node mem, Node ptr, Node off, Node value, boolean init, byte size) { + private StoreNode(Lexer loc, String name, int alias, Type decl, Node ctrl, Node mem, Node ptr, Node off, Node value, boolean init, byte size) { super(loc, name, alias, false, decl, ctrl, mem, ptr, off, value); _init = init; _size = size; diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java index 8eb1f4cc..c2e285c9 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -1,6 +1,6 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; import java.util.BitSet; diff --git a/src/main/java/com/seaofnodes/simple/node/TypeNode.java b/src/main/java/com/seaofnodes/simple/node/TypeNode.java index 3ab2d6f9..38b0b288 100644 --- a/src/main/java/com/seaofnodes/simple/node/TypeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/TypeNode.java @@ -1,6 +1,6 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.Utils; diff --git a/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java b/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java index 32e1deb9..d727ce2b 100644 --- a/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java +++ b/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java @@ -3,7 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.codegen.CodeGen; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.type.Type; public class XCtrlNode extends CFGNode { diff --git a/src/main/java/com/seaofnodes/simple/node/XorNode.java b/src/main/java/com/seaofnodes/simple/node/XorNode.java index c825f396..85fb3259 100644 --- a/src/main/java/com/seaofnodes/simple/node/XorNode.java +++ b/src/main/java/com/seaofnodes/simple/node/XorNode.java @@ -1,11 +1,12 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Lexer; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; public class XorNode extends ArithNode { - public XorNode(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs, (byte)1); } + public XorNode(Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs, (byte)1); } @Override public Tag serialTag() { return Tag.Xor; } @Override public String op() { return "^"; } diff --git a/src/main/java/com/seaofnodes/simple/parser/Allocations.java b/src/main/java/com/seaofnodes/simple/parser/Allocations.java new file mode 100644 index 00000000..c5b8566b --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/parser/Allocations.java @@ -0,0 +1,199 @@ +package com.seaofnodes.simple.parser; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.Ary; + +/** Allocation expressions and declaration-side allocation helper graphs. */ +final class Allocations { + private final Parser P; + + Allocations(Parser P) { this.P = P; } + + /** + Parse an allocation + */ + Node parseNew() { + Type t = P.types.parseType(); + if( t==null ) { + String tname = P._lexer.matchId(); + if( tname==null || Parser.KEYWORDS.contains(tname) ) + throw P.error("Expected a type"); + t = P.types.forwardRefType(tname); + } + // Parse ary[ length_expr ] + if( P.match("[") ) { + if( !t.makeZero().isa(t) ) + throw P.error("Cannot allocate a non-nullable, since arrays are always zero/null filled"); + Node len = P.expressions.parseAssignment().keep(); + P.require("]"); + return allocArray(P.types.typeAry(t,false),len); + } else { + if( !(t instanceof TypeMemPtr tmp) ) + throw P.error("Cannot allocate a "+t.str()); + return allocStruct(tmp._obj); + } + } + + private Node allocStruct(TypeStruct ts) { + Ary ctorArgs = constructorArgs(); + // A field declaration can leave a short forward type name in TYPES. + // Allocation happens in lexical context, so resolve that short name + // to the completed nested type before selecting its class helper. + String typeName = ts._name.indexOf('.') == -1 ? P.types.fullTypeName(ts._name) : ts._name; + Type resolved = Parser.TYPES.get(typeName); + if( resolved instanceof TypeStruct rts ) ts = rts; + TypeStruct clz = (TypeStruct)Parser.TYPES.get(Parser.addClzPrefix(typeName)); + if( clz==null ) + throw P.error("Unknown struct type '" + ts._name + "'"); + Field afld = clz.field(""); + Node alloc; + if( afld != null ) { + TypeFunPtr tfp = (TypeFunPtr)afld._t; + FunNode fun = P._code.link(tfp); + alloc = fun==null + ? new FRefNode((Parser.addClzPrefix(typeName)+".").intern(),P.loc()) + : new FunPtrNode(tfp,P._code._start,fun.ret()).peephole(); + } else { + if( !ts._fref ) + throw P.error("Constructor arguments for '" + ts._name + "' but no constructor is defined"); + Type[] sig = new Type[ctorArgs._len]; + for( int i = 0; i").intern(),P.loc(), + TypeFunPtr.make(false,sig,TypeMemPtr.make(ts))); + } + Ary args = new Ary<>(Node.class); + args.add(P.ctrl()); args.add(P.mem()); + for( Node arg : ctorArgs ) args.add(arg.unkeep()); + args.add(alloc); + return P.functions.functionCall(args); + } + + private Ary constructorArgs() { + Ary args = new Ary<>(Node.class); + if( !P.match("(") ) + return args; + P.functions.arguments(args); + P.require(")"); + return args; + } + + private Node allocArray(TypeStruct ts, Node len) { + Field lenFld = ts.field("#" ); + Field bodyFld = ts.field("[]"); + + ConFldOffNode base = Parser.off(ts, "[]"); + int scale = ts.aryScale(); + Node size = P.peep(new AddNode(base,P.peep(new ShlNode(null,len,P.con(scale))))); + + // Build a NewNode; takes in and puts out all aliases. + NewNode nnn = new NewNode(ts, P.ctrl(), size ).init(); + ProjNode self = new ProjNode(nnn,0,ts.str()).init().keep(); + ProjNode smem = new ProjNode(nnn,1,"#selfMem").init().keep(); + + // Store length. Rest of array is zero'd via CALLOC during CodeGen. + // Length is casted to sanity. + // TODO: Needs runtime check. + Node st = P.peep(new StoreNode(null, "#", 1, TypeInteger.U32, null, smem, self, Parser.off(ts,"#"), len.unkeep(), true)); + + // TODO: Allow add-on "constructor" to init the array elements + + Node prior = P.mem(); + Node esc = P.peep(new EscapeNode(lenFld,self,st,prior)); + P.mem(P.mergeAlias(prior,lenFld._alias,esc)); + prior = P.mem(); + esc = P.peep(new EscapeNode(bodyFld,self,smem,prior)); + P.mem(P.mergeAlias(prior,bodyFld._alias,esc)); + smem.unkeep(); + return self.unkeep(); + } + + Node newString(String s) { + TypeStruct ts = P.types.typeAry(TypeInteger.U8,true); + int lenAlias = ts.field("#" )._alias; + int elemAlias = ts.field("[]")._alias; + TypeConAryB body = TypeConAryB.make(s); + TypeInteger slen = TypeInteger.constant(s.length()); + // Make a TMP, not-null (byte)2, singleton (true) (requires text + // strings are hash-interned), with a TypeStruct having a constant + // array body. + TypeMemPtr str = TypeMemPtr.make((byte)2,TypeStruct.makeAry("[]u8", slen, lenAlias, body, elemAlias, true),true); + assert str.isConstant(); + return P.con(str.makeRO()); + } + + // Build the declaration-side allocation helper. Allocation sites only + // call this function; all layout, initialization and publication choices + // are made here, where the complete struct and constructor are known. + TypeFunPtr makeAllocator(TypeStruct ts, ReturnNode initRet, Field ctorFld) { + TypeFunPtr ctor = ctorFld==null ? null : (TypeFunPtr)ctorFld._t; + int nargs = ctor==null ? 0 : ctor.nargs()-2; // Hide self and selfMem + Type[] atypes = new Type[nargs]; + for( int i = 0; i").intern(); + + int oldUID = P._code.UID(); + FunNode fun = (FunNode)new FunNode(P.loc(),sig,name,P._ref,null,P._ref._start).peephole(); + P._code.link(fun); + Node rpc = new ParmNode("$rpc",0,TypeRPC.BOT,fun,ConstantNode.seed(TypeRPC.BOT).peephole()).peephole(); + Node pub = new ParmNode(ScopeNode.MEM0,1,TypeMem.BOT,fun, + new ProjNode(P._ref._start,1,ScopeNode.MEM0).peephole()).peephole(); + Node[] parms = new Node[nargs]; + for( int i = 0; i P.statements.parseStatement(); // if( pred ) stmts; + case ":" -> P.expressions.parseAssignment(); // pred ? asgn; + case "&&" -> P.expressions.parseLogical(); // pred && expr + case "||" -> pred; // pred || expr_is_ignored + default -> throw TODO(); + }; + lhs.keep(); + P._scope.removeGuards(ifT); + + // See if a one-sided def was made: "if(pred) int x = 1;" and throw. + // See if any forward-refs were made, and copy them to the other side: + // "pred ? n*fact(n-1) : 1" + fScope.balanceIf(P._scope); + + ScopeNode tScope = P._scope; + + // Parse the false side + P._scope = fScope; // Restore scope, then parse else block if any + ifF.unkeep(); // fScope already owns the false control + // Up-cast predicate, even if not else clause, because predicate can + // remain true if the true clause exits: `if( !ptr ) return 0; return ptr.fld;` + P._scope.addGuards(ifF,pred,true); + // Parse false-side flavor + boolean doRHS = false; // RHS is optional for if/else and trinary + Node rhs = switch( fside ) { + case "else" -> (doRHS = P.match(fside)) ? P.statements.parseStatement() : P.con(lhs._type.makeZero()); + case ":" -> (doRHS = P.match(fside)) ? P.expressions.parseAssignment() : P.con(lhs._type.makeZero()); + case "&&" -> P.con(lhs._type.makeZero()); // pred && expr_is_ignored + case "||" -> P.expressions.parseLogical(); // pred || expr + default -> throw TODO(); + }; + rhs.keep(); + P._scope.removeGuards(ifF); + // The RHS of `||` is parsed on the false side, so retain its updated + // control, memory and locals just as an explicit else arm does. + if( doRHS || fside.equals("||") ) + fScope = P._scope; + pred.unkeep(); + + // Check the trinary widening int/flt + if( !fside.equals("else") ) { + rhs = P.conversions.widenInt( rhs.unkeep(), lhs._type ).keep(); + lhs = P.conversions.widenInt( lhs.unkeep(), rhs._type ).keep(); + } + + P._scope = tScope; + P._xScopes.pop(); // Discard pushed from graph display + // See if a one-sided def was made: "if(pred) int x = 1;" and throw. + // See if any forward-refs were made, and copy them to the other side: + // "pred ? n*fact(n-1) : 1" + tScope.balanceIf(fScope); + + // Merge results + RegionNode r = P.ctrl(tScope.mergeScopes(fScope,P.loc())); + Node ret = P.peep(new PhiNode("",r,lhs.unkeep(),rhs.unkeep())); + // Immediately fail e.g. `arg ? 7 : ptr` + ParseException err; + if( !fside.equals("else") && (err = ret.err()) !=null ) throw err; + ret.keep(); + r.peephole(); + return ret.unkeep(); + } +} diff --git a/src/main/java/com/seaofnodes/simple/parser/Conversions.java b/src/main/java/com/seaofnodes/simple/parser/Conversions.java new file mode 100644 index 00000000..d50e2031 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/parser/Conversions.java @@ -0,0 +1,72 @@ +package com.seaofnodes.simple.parser; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; + +/** Shared declaration, assignment, and return conversions. */ +final class Conversions { + private final Parser P; + + Conversions(Parser P) { this.P = P; } + + // Widen ints to floats; narrow wide int types. + // Early error if types do not match variable. + Node convertExpr( Node expr, Type t ) { + if( !expr._type.accessISA(t) ) + throw P.error("Type "+expr._type.str()+" is not of declared type "+t.str()); + if( t instanceof TypeMemPtr tmp && tmp.isFinal() ) + expr = P.peep(new ReadOnlyNode(expr)); + // A FunPtr carries the semantic edge to its function's Return. Do not + // hide that edge behind a Convert which can fold to a plain constant. + if( expr instanceof FunPtrNode && t instanceof TypeFunPtr ) + return expr; + // Auto-widen array to i64 (cast ptr to raw int bits) + if( t == TypeInteger.BOT && expr._type instanceof TypeMemPtr tmp && tmp._obj.isAry() ) + return P.peep(new AddNode(P.peep(new PtrToIntNode(expr)),Parser.off(tmp._obj,"[]"))); + // Widen ints to floats, narrow wide types + return P.peep(new ConvertNode(t,expr)); + } + + // Inferred `var` declarations describe writable slots, not the exact + // value used to initialize them. Explicitly typed locals retain the + // user's nullability and numeric-width guarantees; `val` retains the + // initializer's precise type. + static Type mutableInferredType(Type t) { + return switch( t ) { + case TypeInteger ti -> TypeInteger.BOT; + case TypeFloat tf -> TypeFloat.F64; + case TypeMemPtr tmp -> tmp.makeVar(); + case TypeFunPtr tfp -> tfp; + case TypeConAry a -> a; + case TypePtr ptr -> TypePtr.PTR; + case TypeScalar ts -> TypeScalar.BOT; + default -> t; + }; + } + + Type constructorFieldType(Type t) { + if( t instanceof TypeMemPtr ptr && ptr._obj.isConAry() ) { + TypeStruct declared = (TypeStruct)Parser.TYPES.get(ptr._obj._name); + TypeStruct shape = P.types.typeAry(declared._fields[1]._t,ptr._obj._fields[1]._final); + return TypeMemPtr.make((byte)2,shape,false).withAccess(ptr._ro); + } + return mutableInferredType(t); + } + + // Seed an inferred return merge with the declared numeric family instead + // of a transient constant/range. Pointer nullability remains part of the + // inferred function result and is combined by the later Phi. + static Type inferredReturnType(Type t) { + return switch( t ) { + case TypeInteger ti -> TypeInteger.BOT; + case TypeFloat tf -> TypeFloat.F64; + default -> t; + }; + } + + Node widenInt( Node expr, Type t ) { + return (expr._type instanceof TypeInteger || expr._type==Type.NIL) && t instanceof TypeFloat + ? P.peep(new ToFloatNode(expr)) : expr; + } + +} diff --git a/src/main/java/com/seaofnodes/simple/parser/Declarations.java b/src/main/java/com/seaofnodes/simple/parser/Declarations.java new file mode 100644 index 00000000..92e978b6 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/parser/Declarations.java @@ -0,0 +1,164 @@ +package com.seaofnodes.simple.parser; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.node.ScopeNode.Kind; +import com.seaofnodes.simple.type.*; + +/** Local/field bindings and native symbol declarations. */ +final class Declarations { + private final Parser P; + + Declarations(Parser P) { this.P = P; } + + /** + * Parse declaration or expression statement + * declStmt = type var['=' exprAsgn][, var['=' exprAsgn]]* ';' | exprAsgn ';' + *

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

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

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

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

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

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

See {@code chapter29/docs/29-grammar.md} for the production-to-method map. + * Evaluation order and scope lifetimes are explicit: loop updates and declared + * constructor bodies are the two deferred source fragments. There is no AST. + */ +package com.seaofnodes.simple.parser; diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java index 980daf0f..6c8a3e8d 100644 --- a/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/src/main/java/com/seaofnodes/simple/type/Type.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.type; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.codegen.GlobalBits; import com.seaofnodes.simple.util.*; import java.util.*; diff --git a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index 4c5ae6ea..4e73e148 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -16,10 +16,10 @@ public class TypeStruct extends Type { /** * `_open` and `_fref` are independent lattice coordinates. * - * `_open` says the structural tail is not known yet. On the low side an - * open struct has infinitely many implicit BOT fields; its dual has an - * implicit TOP tail. A real declaration is therefore open while its body - * is being parsed: + * `_open` says the structural tail is not known yet - more fields may be + * added. On the low side an open struct has infinitely many implicit BOT + * fields; its dual has an implicit TOP tail. A real declaration is open + * while its body is being parsed: * * ```text * struct S { int x; /* more declared fields may follow *\/ } @@ -27,7 +27,8 @@ public class TypeStruct extends Type { * * `_fref` says no actual declaration has contributed to the type. The * parser may still invent fields demanded by uses, leaving a useful open - * structural constraint: + * structural constraint. Here `S` is an unknown struct, which has an + * unknown `x` field: * * ```text * S? p; p.x; // fref S { BOT x; ... } -- cgit v1.2.3