* 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
* 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,";");
}
/** 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 hasBang = match("!");
Lexer loc = loc();
String name = requireId();
// Optional initializing expression follows
boolean xfinal = false;
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() ) {
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();
}
// TOP means val and val is always final
xfinal = (t==Type.TOP) ||
expr instanceof ExternNode ||
// BOTTOM is var and var is always not-final
(t!=Type.BOTTOM &&
// no Bang AND
!hasBang &&
// not-null (expecting null to be set to not-null)
expr._type != Type.NIL &&
// Pointers are final by default; int/flt are not-final by default.
(t instanceof TypeNil));
// 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);
}
// Final is deep on ptrs
if( xfinal && t instanceof TypeMemPtr tmp ) {
t = tmp.makeRO();
expr = peep(new ReadOnlyNode(expr));
}
// 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 -> _code.ZERO;
case TypeFloat tf -> con(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( t instanceof TypeNil tn && !tn.nullable() ) {
uninit = true;
if( !hasBang ) 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("
* 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("#showGraph")) return require(showGraph(),";");
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 Node parseConstructorDeclaration() {
TypeStruct self = _scope.constructorSelf();
assert self != null;
String name = requireId();
String expect = initFieldName(self._name);
if( name != expect )
throw error("Constructor name '" + name + "' must match type name '" + expect + "'");
require("=");
Node ctor = constructorFunc(name);
TypeFunPtr sig = (TypeFunPtr)ctor._type;
String clzName = addClzPrefix(self._name);
TypeStruct clz = (TypeStruct)TYPES.get(clzName);
Field old = clz==null ? null : clz.field("
* 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
_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
ctrl(ifF.unkeep()); // Ctrl token is now set to ifFalse projection
// 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
* 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();
}
// rhs is keeped() and becomes lhs
// cmp is NOT keeped() and is the last test
Node ifNode = new IfNode(ctrl(), cmp.unkeep()).peephole();
Node ifT = new CProjNode(ifNode. keep(), 0, "True" ).peephole().keep();
Node ifF = new CProjNode(ifNode.unkeep(), 1, "False").peephole();
// False side does nothing but capture memory & side-effects
ScopeNode fail = _scope.dup();
fail.ctrl(ifF);
// Loop over stacked compares. Each loop moves the old RHS to become
// the new LHS, so e.g. (a < b < c < d) compares (LHS:a < RHS:b) then
// compares (LHS:b < RHS:c) then (LHS:c < RHS:d), etc.
while( dir0 != 0 ) {
if( Math.abs(dir) != Math.abs(dir0) )
throw error("Mixing relational directions in a chained relational test");
// True side parses next arm of test
ctrl(ifT.unkeep());
lhs = rhs; // lhs is keeped() and is old RHS
rhs = parseShift().keep();
cmp = makeCompBool(dir,lhs.unkeep(),rhs); // Convert to a bool
ifNode = new IfNode(ctrl(), cmp).peephole();
ifT = new CProjNode(ifNode. keep(), 0, "True" ).peephole().keep();
ifF = new CProjNode(ifNode.unkeep(), 1, "False").peephole();
// Merge result into the fail case
ctrl(ifF);
fail.mergeScopes(_scope.dup(), loc()).peephole();
// Check next stacked compare
dir0 = parseCompDir();
}
rhs.unkill();
ctrl(ifT.unkeep());
RegionNode r = fail.mergeScopes(_scope, loc()).init();
_scope = fail;
return new PhiNode("", r,_code.ZERO,con(1)).peephole();
}
private int parseCompDir() {
if( match("<=") ) return -1; // Negative for "equals-or-less"
if( match(">=") ) return -2; // 1 for <, 2 for >
if( match("<" ) ) return 1; // Positive for just "less"
if( match(">" ) ) return 2;
return 0;
}
private Node makeCompBool( int dir0, Node lhs, Node rhs ) {
// Convert to a bool
if( Math.abs(dir0)==2 ) // Swap direction
{ Node tmp = lhs; lhs = rhs; rhs = tmp; }
lhs = peep(dir0 < 0 ? new BoolNode.LE(lhs,rhs) : new BoolNode.LT(lhs,rhs));
return peep(lhs);
}
/**
* 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
String name = _lexer.matchId();
if( name!=null ) {
Var n = _scope.lookup(name);
if( n != null && !(n.type() instanceof TypeMemPtr) ) {
if( n._final )
throw error("Cannot reassign final '"+n._name+"'");
Node expr = zsMask(peep(new AddNode(_scope.in(n),con(delta))),n.type());
_scope.update(n,expr);
return expr;
}
}
// 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() {
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
* 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) {
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);
}
private Node defaultSelf() {
int selfx = _scope._kinds.at(_scope.enclosingFuncOrDecl())._lexSize;
return _scope.in(_scope.update(_scope.var(selfx),null));
}
/**
* 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
*
*/
private Node parsePostfixName(Node expr, String name) {
// Keep expr across possible updates
expr.keep();
// Get the best known TypeStruct from a pointer type.
TypeStruct ts = null, ts2;
if( expr._type instanceof TypeMemPtr tmp && (ts2=((TypeStruct)TYPES.get(tmp._obj._name))) != null )
ts = (TypeStruct)tmp._obj.join(ts2);
// A Load's flow type is intentionally not promised during parsing,
// but its declaring field type is still known. Recover that static
// type for chained accesses such as `_grow(1).buf[len++]`; otherwise
// the array Store is parsed as alias #1 and can hide the independent
// side effect of the postfix `len++`.
if( ts==null && expr instanceof LoadNode load ) {
TypeStruct ots = load.off() instanceof ConFldOffNode coff ? coff._ts : null;
if( ots==null && load.ptr()._type instanceof TypeMemPtr owner ) {
Type owner0 = TYPES.get(owner._obj._name);
ots = owner0 instanceof TypeStruct obj ? obj : owner._obj;
}
if( ots != null ) {
Field loaded = ots.field(load._name);
if( loaded != null && loaded._t instanceof TypeMemPtr ltmp ) {
Type loaded0 = TYPES.get(ltmp._obj._name);
ts = loaded0 instanceof TypeStruct obj ? obj : ltmp._obj;
}
}
}
Field fld = ts==null ? null : ts.field(name);
if( fld==null && ts!=null && !startsClzPrefix(ts._name) ) {
Type clz0 = TYPES.get(addClzPrefix(ts._name));
if( clz0 instanceof TypeStruct clz && (fld = latestStruct(clz).field(name)) != null ) {
expr.unkeep();
ts = latestStruct(clz);
expr = con(TypeMemPtr.make((byte)2,ts,true)).keep();
}
}
if( fld==null && ts!=null )
fld = fieldOrOpen(ts,name,false);
if( fld==null && ts!=null && !latestStruct(ts)._open )
throw error("Accessing unknown field '"+name+"' from '*"+ts._name+"'");
// With no field, we will update the bulk memory
int alias = fld==null ? 1 : fld._alias;
Type decl = fld==null ? Type.BOTTOM : fld._t;
// Field offset; fixed for structs, computed for arrays
Node off = (name=="[]"
// Array element math, with unknown base offset and shift amount.
? peep(new AddNode(fldoff(expr,"[]"),peep(new ShlNode(null,require(parseAsgn(),"]"),fldoff(expr,"<<")))))
// Named field offset on an unknown struct type
: fldoff(expr,name)).keep();
// Disambiguate "obj.fld==x" boolean test from "obj.fld=x" field assignment
if( matchOpx('=','=') ) {
// 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();
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 = _lexer.matchOperAssign();
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 );
mem.keep();
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();
load = postfix(ch) ? load.unkeep() : op;
// And use the original loaded value as the result
return load;
}
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 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
* ( arg* )
*
*/
private Node functionCall(Node fcn, Node self) {
if( fcn._type == Type.NIL )
throw error("Calling a null function pointer");
fcn.keep(); // Keep while parsing args
Ary
* 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 ); }
// Field offset for a known type (but unknown offset)
public static ConFldOffNode off( TypeStruct ts, String fname ) {
return (ConFldOffNode)(new ConFldOffNode(ts,fname).peephole());
}
// Field offset for an unknown type
public Node fldoff( Node n, String name ) {
return new FldOffNode(n,name,loc()).peephole();
}
public Node peep( Node n ) {
// Peephole, then improve with lexically scoped guards
return _scope.upcastGuard(n.peephole());
}
// 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