* This is a simple recursive descent parser. All lexical analysis is done here as well. */ public class Parser { public static ConstantNode ZERO; // Very common node, cached here public static ConstantNode NIL; // Very common node, cached here public static XCtrlNode XCTRL; // Very common node, cached here // Compile driver public final CodeGen _code; // The Lexer. Thin wrapper over a byte[] buffer with a cursor. private Lexer _lexer; /** * 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,";");
}
// Widen a reassignable binding without discarding the initializer's
// permissions. Lattice glb includes readonly memory and is too broad here.
private Type inferredType(Type t) {
if( t instanceof TypeMemPtr tmp ) {
if( tmp._obj.isAry() ) {
Type elem = tmp._obj._fields[1]._t;
if( elem instanceof TypeConAry )
elem = ((TypeMemPtr)TYPES.get(tmp._obj._name))._obj._fields[1]._t;
return typeAry(elem,tmp._obj._fields[1]._final).withAccess(tmp._ro).makeNullable();
}
Type base = TYPES.get(tmp._obj._name);
TypeMemPtr ptr = (TypeMemPtr)base;
return ptr.withAccess(tmp._ro).makeNullable();
}
return t.glb(false);
}
// The binding modifier sits immediately before the name. It never
// changes permissions on the referenced object.
private boolean bindingFinal(Type t) {
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; // Fixed field independent of pointee access
boolean initialized = match("=");
Node expr;
if( initialized ) {
expr = isExternDecl() ? externDecl(name,t)
: _scope.inConstructor() && name.equals(shortName(_nestedType))
? constructorFunc() : parseAsgn();
// var/val, then type comes from expression
if( inferType ) {
if( expr._type==Type.NIL )
throw error("a not-null/non-zero expression");
t = expr._type;
if( !xfinal ) t = inferredType(t); // Widen if not final
}
// expr is a constant function
if( t instanceof TypeFunPtr && expr._type instanceof TypeFunPtr tfp && tfp.isConstant() ) {
if( expr instanceof ExternNode ) t = expr._type; // Upgrade declared type to exact function
else if( _code._link(tfp)!=null ) _code.link(tfp).setName(name); // Assign debug name to Simple function
}
} else {
// 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 ) {
// Nullable pointers get a NIL; not-null get a TOP which
// signals that they *must* be initialized in the constructor.
case TypeNil tn -> tn.nullable() ? NIL : con(Type.TOP);
case TypeInteger ti -> xfinal ? con(Type.TOP) : ZERO;
case TypeFloat tf -> con(xfinal ? Type.TOP : TypeFloat.FZERO);
// Bottom signals type inference: they must be initialized in
// the constructor and that's when we'll discover the type.
case Type tt -> { assert tt==Type.BOTTOM; yield con(tt); }
};
// Nullable fields are set in the constructor, but remain shallow final.
// e.g. final pointer to a r/w array
if( t instanceof TypeNil tn && !tn.nullable() && xfinal )
fld_final = true;
}
// Lift expression, based on type
Node lift = liftExpr(expr, t, true);
// Lift type to the declaration. This will report as an error later if
// we cannot lift the type.
// Define a new name
if( !_scope.define(name,t,xfinal || fld_final,lift, loc) )
throw error("Redefining name '" + name + "'", loc);
_scope.lookup(name)._init = initialized;
return lift;
}
/**
* Parse a struct declaration, and return the following statement.
* Structs cannot be redefined, but can be nested.
*
* @return zero
*/
private String _nestedType;
private static String shortName(String name) { return name.substring(name.lastIndexOf('.')+1); }
private Node parseStruct() {
String old = _nestedType;
String name = requireId();
if( old!=null ) name=old+"."+name;
_nestedType=name;
TypeMemPtr ptr = TYPES.get(name) instanceof TypeMemPtr p ? p : TypeMemPtr.make(TypeStruct.open(name));
TYPES.put(name,ptr);
require("{");
TypeFunPtr sig = _code.makeFun(TypeFunPtr.make(false,false,new Type[]{ptr,TypeMem.BOT},TypeMem.BOT));
ReturnNode init = parseFunctionBody(sig,loc(),null,true,"self","#selfMem");
init.fun()._name=name+".
* 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 (_scope.inConstructor() && matchx("new")) return parseConstructorDeclaration();
else if (matchx(";") ) return null; // 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();
}
// In a struct declaration, new names the constructor. Its body still
// parses as a function; in expressions, new allocates and calls it.
private Node parseConstructorDeclaration() {
Lexer loc=loc();
String name=requireId();
String expect=shortName(_nestedType);
if( !name.equals(expect) )
throw error("Constructor name '"+name+"' must match type name '"+expect+"'");
require("=");
Node ctor=constructorFunc();
TypeFunPtr sig=(TypeFunPtr)ctor._type;
Node lift=liftExpr(ctor,sig,true);
if( !_scope.define(name,sig,true,lift,loc) )
throw error("Redefining constructor '"+name+"'");
_scope.lookup(name)._init=true;
return require(lift,";");
}
/**
* 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(),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
Node ifT = new CProjNode(ifNode. keep(), 0, "True" ).peephole().keep();
Node ifF = 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.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 ZERO;
}
private ScopeNode jumpTo(ScopeNode toScope) {
ScopeNode cur = _scope.dup();
ctrl(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 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(_breakScope.ctrl(), null, false);
return 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 Utils.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
Node ifT = new CProjNode(ifNode. keep(), 0, "True" ).peephole().keep();
Node 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 Utils.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 "&&" -> rhs = pred;
case "||" -> rhs = parseLogical();
default -> throw Utils.TODO();
};
rhs.keep();
_scope.removeGuards(ifF);
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;
r.peephole();
return ret;
}
/**
* 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(), ";");
// Force the lazy whole-memory Phi before closing this exit.
if( _privateFun==_fun )
throw error("A constructor cannot return a value");
_fun.addReturn(ctrl(), _scope.mem(), expr);
ctrl(XCTRL); // Kill control
return expr;
}
/** Parse: [name '='] expr
*/
private Node parseAsgn() {
int old = pos();
String name = _lexer.matchId();
int old_pre_equals = pos();
// Just a plain expression, no assignment.
// Distinguish `var==expr` from `var=expr`
if( name==null || KEYWORDS.contains(name) || !matchOpx('=','=') )
{ pos(old); return parseExpression(); }
// Find variable to update
Var def = _scope.lookup(name);
if( def==null )
throw error("Undefined name '" + name + "'");
// If a method var, allow nested blocks and methods, but not fcns or other structs.
// Else safety check for accessing fields out of function scope.
if( instance(def) ) {
pos(old_pre_equals); // setup for `self.name = expr`
Var selfVar = _scope.lookup("self");
Node self = liftExpr(_scope.in(selfVar),selfVar.type(),true);
return parsePostfixName(self,name);
}
// 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+"'");
// Parse assignment expression
checkCaptureWrite(def);
Node expr = parseAsgn();
// Lift expression, based on type
Node lift = liftExpr(expr.keep(), def.type(), true);
// Update
_scope.update(name,lift);
// Return un-lifted expr
return expr.unkeep();
}
// Apply declared access permissions; widen floats and narrow integers.
// Early error if types do not match variable.
private Node liftExpr(Node expr, Type t, boolean isLoad) {
if( t==Type.BOTTOM || t==Type.TOP ) return expr;
// Constructor sentinels record missing initialization, not a value
// needing conversion. Keep them visible to the completion check.
if( expr instanceof ConstantNode && !(expr instanceof FRefNode) &&
(expr._type==Type.TOP || expr._type==Type.BOTTOM) ) return expr;
if( t instanceof TypeMemPtr tmp && tmp.isFinal() )
expr = peep(new ReadOnlyNode(expr));
if( expr instanceof FunPtrNode && t instanceof TypeFunPtr ) return expr;
return peep(new ConvertNode(t,expr));
}
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 ';'
*
* 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 = 0;
while( true ) {
int dir0;
if( false ) ;
else if( match("<=" ) ) dir0 = -1;
else if( match(">=" ) ) dir0 = -2;
else if( match("<" ) ) dir0 = 1;
else if( match(">" ) ) dir0 = 2;
else break;
lhs.keep();
// Check and record direction
if( dir==0 ) {
dir = Math.abs(dir0);
Node rhs = parseShift();
lhs = makeCompBool(dir0,lhs.unkeep(),rhs); // Convert to a bool
} else if( dir == Math.abs(dir0) ) {
// e0 < lhs < ???
Node ifNode = new IfNode(ctrl(), lhs).peephole();
Node ifT = new CProjNode(ifNode. keep(), 0, "True" ).peephole();
Node ifF = new CProjNode(ifNode.unkeep(), 1, "False").peephole();
// False side does nothing
ScopeNode fScope = _scope.dup();
fScope.ctrl(ifF);
// True side executes next part of range
ctrl(ifT);
_scope.addGuards(ifT,lhs,false);
Node rhs = parseShift();
_scope.removeGuards(ifT); // TODO: I think should remain true as long as possible
Node next = makeCompBool(dir0, lhs, rhs).keep();
// Merge result
RegionNode r = ctrl(_scope.mergeScopes(fScope, loc()));
assert next._type.meet(lhs._type).isa( TypeInteger.BOOL );
lhs = peep(new PhiNode("",r,next.unkeep(),lhs.unkeep()));
r.peephole();
} else {
throw error("Mixing relational directions in a chained relational test");
}
}
return lhs;
}
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; // Pre vs post
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 = liftExpr(peep(new AddNode(_scope.in(n),con(delta))),n.type(),true);
_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['++','--'] |
* [static.]* Id
*
* @return a primary {@link Node}, never {@code null}
*/
private Node parsePrimary() {
if( _lexer.isNumber(_lexer.peek()) ) return parseLiteral();
if( _lexer.peek('"') ) return newString(parseString());
if( matchx("true" ) ) return con(1);
if( matchx("false") ) return ZERO;
if( matchx("null" ) ) return NIL;
if( match ("'" ) ) return parseChar();
if( match ("(" ) ) return parsePostfix(require(parseAsgn(), ")"));
if( matchx("new" ) ) return parsePostfix(alloc());
if( match ("{" ) ) return parsePostfix(require(func(),"}"));
// Parse static variable lookup: `type.fld` in the type namespace
// CNC: not a full type parse, just a typename parse
int pos = pos();
Type t = type();
if( t!=null ) {
if( peek('.') )
// A namespace lookup is not a reference declaration.
return parsePostfix(con(TYPES.get(((TypeMemPtr)t)._obj._name)));
//pos(pos); // TODO: not a `type.fld`
//return null;
throw Utils.TODO();
}
// Expect an identifier now
// - if null, make fref, normal var handling
// - if final constant, normal var handling
// - if method var, scan skipping blocks & methods, must hit correct struct no fcns
// - if normal var, scan skipping blocks, allowing last fcn
// - NO fcns nested in methods, NO methods nested in fcns
String id = _lexer.matchId();
if( id == null || KEYWORDS.contains(id) )
throw errorSyntax("an identifier or expression");
Var var = _scope.lookup(id);
if( var==null ) {
// If missing, assume a forward reference
_scope.define(id, FRefNode.FREF_TYPE, true, XCTRL, loc());
var = _scope.lookup(id);
}
// If a method var, allow nested blocks and methods, but not fcns or other structs.
// Else safety check for accessing fields out of function scope.
if( instance(var) ) {
Var selfVar = _scope.lookup("self");
Node self = liftExpr(_scope.in(selfVar),selfVar.type(),true);
return parsePostfixName(self,id);
}
// Load local value
Node oldValue = _scope.in(var);
if( oldValue instanceof ConstantNode && !(oldValue instanceof FRefNode) && oldValue._type==Type.BOTTOM )
throw error("Cannot read uninitialized field '"+id+"'");
Node rvalue = liftExpr(oldValue,var.type(),true);
if( rvalue!=oldValue ) _scope.update(var,rvalue);
if( rvalue instanceof ConstantNode && rvalue._type == Type.BOTTOM )
if( rvalue instanceof FRefNode )
return parsePostfix(rvalue);
else throw error("Cannot read uninitialized field '"+id+"'");
// Check for assign-update, x += e0;
char ch = _lexer.matchOperAssign();
if( ch==0 ) // Normal primary, check for postfix updates
return parsePostfix(rvalue);
// Assign-update direct into Scope
if( var._final )
throw error("Cannot reassign final '"+var._name+"'");
checkCaptureWrite(var);
Node op = opAssign(ch,rvalue, var.type() );
_scope.update(var,op);
return postfix(ch) ? rvalue.unkeep() : op;
}
// true if instance variable lookup (var is in any number of nested blocks,
// then an instance function then inside a struct declaration).
private boolean instance(Var var ) {
// If a method var, allow nested blocks and methods, but not fcns or other structs
Kind kind = _scope.kind(var);
if( kind instanceof Kind.Define ) {
if( var.isFRef() ) return false; // Promote an unresolved lexical name, not self.name.
if( _privateFun==_fun && _privateFun!=null ) return true;
for( int i = _scope.depth()-1; i>=0 && var._idx < _scope._kinds.at(i)._lexSize; i-- ) {
Kind xkind = _scope._kinds.at(i);
if( xkind instanceof Kind.Block ) continue;
if( xkind instanceof Kind.Func ) {
if( _scope._kinds.at(i-1)==kind )
return true; // Instance variable: lookup in a method in a decl
}
throw Utils.TODO();
}
} else {
// If a normal var, allow any nested blocks, and a last fcn -
// but not functions further out (which involves capture).
Node def = _scope.in(var._idx);
if( _captures!=null && _scope.kind(var) instanceof Kind.Func &&
!(var._final && def._type.isConstant()) && !(def instanceof FRefNode) ) {
if( !(def instanceof ParmNode parm && parm.fun()==_fun) ) {
_captures.add(def.keep());
Type type=def._type;
int index=_fun.sig().nargs();
_fun.addParseArg(type);
_scope.update(var,new ParmNode(var._name,index+2,type,_fun,con(type)).init());
}
return false;
}
for( int i = _scope.depth()-1; i>=0 && var._idx < _scope._kinds.at(i)._lexSize; i-- )
if( _scope._kinds.at(i) instanceof Kind.Func &&
!(def instanceof FRefNode) && !(var._final && def._type.isConstant()) )
throw error("Variable '"+var._name+"' is out of function scope and must be a final constant");
}
return false;
}
private void checkCaptureWrite(Var var) {
if( _captures==null ) return;
for( int i=_scope.depth()-1; i>=0 && var._idx<_scope._kinds.at(i)._lexSize; i-- )
if( _scope._kinds.at(i) instanceof Kind.Func )
throw error("Cannot assign captured variable '"+var._name+"' in an initializer");
}
// 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 AndNode(loc(),lhs,rhs);
case '|' -> new OrNode(loc(),lhs,rhs);
case '^' -> new XorNode(loc(),lhs,rhs);
case Lexer.SHL -> new ShlNode(loc(),lhs,rhs);
case Lexer.SAR -> new SarNode(loc(),lhs,rhs);
case Lexer.SHR -> new ShrNode(loc(),lhs,rhs);
default -> throw Utils.TODO();
};
// Convert to float ops, or narrow int types; error if not declared type.
// Also, if postfix LHS is still keep()
return liftExpr(peep(op),t,true);
}
/**
Parse an allocation
*/
private Node alloc() {
Type t = type();
if( t==null ) throw error("Expected a type");
// Parse ary[ length_expr ]
if( match("[") ) {
if( !t.makeZero().isa(t) )
throw error("Cannot allocate a non-nullable, since arrays always zero/null fill");
Node len = parseAsgn();
if( !(len._type instanceof TypeInteger) )
throw error("Cannot allocate an array with length "+len._type);
require("]");
TypeMemPtr tmp = typeAry(t,false);
return newArray(tmp._obj,len);
}
if( !(t instanceof TypeMemPtr tmp) )
throw error("Cannot allocate a "+t.str());
TypeStruct shape=tmp._obj;
TypeFunPtr sig=ALLOCS.get(shape._name);
if( sig==null ) throw error("Unknown struct type '"+shape._name+"'");
if( !peek('{') ) {
// Obvious missing defaults can still be diagnosed here. A user
// constructor or a merge needs the later publication check.
if( shape.field(shortName(shape._name))==null ) {
StructNode defaults=INITS.get(shape._name);
Type initial=INITIALIZERS.get(shape._name).expr()._type;
for( int i=0; i
* expr ['++' | '--' ] // Postfix unary write operator
* expr [ [op]= expr ] // Field reference
* expr ('[' expr ']')* [ [op]= expr ] // Array reference
*
*/
private Node parsePostfixName(Node expr, String name) {
if( privateSelf(expr) ) return parsePrivateField(name);
if( !privateSelf(expr) && mayBeSelf(expr,new java.util.BitSet()) )
throw error("Cannot access self through a merged alias during construction");
if( expr._type==Type.NIL )
throw error("Accessing unknown field '" + name + "' from 'null'");
// Sanity check expr for being a reference
if( !(expr._type instanceof TypeMemPtr ptr) )
return parseUnknownField(expr,name);
// Find the field from the Type. Lookup in the base object field names.
TypeMemPtr ptr2 = (TypeMemPtr)TYPES.get(ptr._obj._name);
if( !ptr._obj.isAry() )
ptr = ptr.makeFrom(ptr2._obj); // The declaration fixes the field shape; retain this view's access.
TypeStruct base = ptr._obj;
int fidx = base.find(name);
if( fidx==-1 && base._open ) return parseUnknownField(expr,name);
if( fidx == -1 )
throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'");
// Get field type and layout offset from base type and field index fidx
Field f = base._fields[fidx]; // Field from field index
Type tf = f._t;
if( tf instanceof TypeFunPtr ctor && ctor.ret() instanceof TypeMem )
throw error("A constructor is only called by new");
if( tf instanceof TypeMemPtr ftmp && ftmp.isFRef() )
tf = ftmp.makeFrom(((TypeMemPtr)(TYPES.get(ftmp._obj._name)))._obj);
if( base.isAry() && tf instanceof TypeConAry con )
tf = con.elem();
expr.keep();
// Field offset; fixed for structs, computed for arrays
Node off = (name.equals("[]") // If field is an array body
// Array index math
? peep(new AddNode(off(base,"[]"),peep(new ShlNode(null,require(parseAsgn(),"]"),con(base.aryScale())))))
// Struct field offsets are hardwired
: off(base,name)).keep();
// Disambiguate "obj.fld==x" boolean test from "obj.fld=x" field assignment
if( matchOpx('=','=') ) {
Node val = parseAsgn().keep();
Node lift = liftExpr( val, tf, false );
store(name,f._alias,tf,expr.unkeep(),off.unkeep(),lift,false,base.isAry() ? ctrl() : null);
return val.unkeep(); // "obj.a = expr" returns the expression while updating memory
}
// Load field
Node load = f._one && INITS.containsKey( base._name )
? INITS.get(base._name).in(base.find(name))
: new LoadNode(loc(),name, f._alias, mem(), expr, off);
// Arrays include control, as a proxy for a safety range check
// Structs don't need this; they only need a NPE check which is
// done via the type system.
if( base.isAry() && !name.equals("#") ) load.setDef(0,ctrl());
load = peep(load);
// Check for assign-update, "ptr.fld += expr" or "ary[idx]++"
char ch = _lexer.matchOperAssign();
if( ch!=0 ) {
Node op = opAssign(ch,load,tf);
store(name,f._alias,tf,expr.unkeep(),off.unkeep(),op,false,base.isAry() ? ctrl() : null);
load = postfix(ch) ? load.unkeep() : op;
// And use the original loaded value as the result
return load;
//throw Utils.TODO(); // NO POSTFIX AFTER STORE, JUST RETURN
} else {
off.unkill();
// Method call: Loaded a function from a named field, AND the base
// field type is final.
if( load._type instanceof TypeFunPtr && name!="[]" &&
_code.externFunc((TypeFunPtr)load._type)==null &&
((TypeMemPtr)TYPES.get(base._name))._obj.field(name)._final &&
// And calling a function
match("(") ) {
return parsePostfix(require(functionCall(load,expr),")"));
}
// Drop expr, keeping load alive
load.keep();
expr.unkill();
load.unkeep();
}
return parsePostfix(load);
}
// Syntax fixes the access even when a forward definition or a loop
// leaves the receiver untyped. Resolve its alias and layout in the graph.
private Node parseUnknownField(Node expr, String name) {
expr.keep();
Node off = new FldOffNode(expr,name).peephole();
if( name.equals("[]") ) {
Node index = require(parseAsgn(),"]");
Node scale = new FldOffNode(expr,"<<").peephole();
off = peep(new AddNode(off,peep(new ShlNode(loc(),index,scale))));
}
off.keep();
if( matchOpx('=','=') ) {
Node value = parseAsgn().keep();
unknownStore(name,expr,off,value);
expr.unkill();
off.unkill();
return value.unkeep();
}
Node load = new LoadNode(loc(),name,1,mem(),expr,off);
load.setDef(0,ctrl());
load = peep(load);
char ch = _lexer.matchOperAssign();
if( ch!=0 ) {
Node op = opAssign(ch,load,Type.BOTTOM).keep();
unknownStore(name,expr,off,op);
// The field width is not known yet. A compound assignment returns
// the stored value after conversion; postfix returns the old load.
// Reading our own Store folds once its alias and width are known.
if( postfix(ch) ) load.unkeep();
else {
load = new LoadNode(loc(),name,1,mem(),expr,off);
load.setDef(0,ctrl());
load = peep(load);
}
load.keep();
op.unkill();
} else if( !name.equals("[]") && match("(") ) {
Node result=functionCall(load,expr,name);
off.unkill();
return parsePostfix(require(result,")"));
} else load.keep();
expr.unkill();
off.unkill();
return parsePostfix(load.unkeep());
}
private void unknownStore(String name, Node ptr, Node off, Node value) {
checkPublication(value);
Node st=new StoreNode(loc(),name,1,Type.BOTTOM,mem(),ptr,off,value,false);
st.setDef(0,ctrl());
mem(st.peephole());
}
// Explicit self.x and an unqualified field name use the same local slot.
// The map also keeps self.x distinct from a parameter/local named x.
private Node parsePrivateField(String name) {
Var v=_fieldVars.get(name);
if( v==null ) throw error("Cannot resolve field '"+name+"'");
if( v.type() instanceof TypeFunPtr ctor && ctor.ret() instanceof TypeMem )
throw error("A constructor is only called by new");
if( matchOpx('=','=') ) {
Node value=parseAsgn().keep();
checkPublication(value);
_scope.update(v,liftExpr(value,v.type(),false));
return value.unkeep();
}
Node value=_scope.in(_scope.update(v,null));
if( value instanceof ConstantNode && (value._type==Type.BOTTOM || value._type==Type.TOP) )
throw error("Cannot read uninitialized field '"+name+"'");
char ch=_lexer.matchOperAssign();
if( ch!=0 ) {
Node op=opAssign(ch,value,v.type());
checkPublication(op);
_scope.update(v,op);
return postfix(ch) ? value.unkeep() : op;
}
if( value._type instanceof TypeFunPtr && match("(") )
return parsePostfix(require(functionCall(value,self()),")"));
return parsePostfix(value);
}
// 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
* ( arg* )
*
*/
private Node functionCall(Node fcn, Node self) {
return functionCall(fcn,self,null);
}
private Node functionCall(Node fcn, Node self, String method) {
if( fcn._type == Type.NIL )
throw error("Calling a null function pointer");
if( !(fcn instanceof FRefNode) && fcn._type!=Type.BOTTOM && fcn._type!=TypeScalar.BOT && !fcn._type.isa(TypeFunPtr.BOT) )
throw error("Expected a function but got "+fcn._type.glb(false).str());
fcn.keep(); // Keep while parsing args
Ary
* integerLiteral: [1-9][0-9]* | [0]
* floatLiteral: [digits].[digits]?[e [digits]]?
*
*/
private ConstantNode parseLiteral() { return con(_lexer.parseNumber()); }
public static Node con( long con ) { return con==0 ? ZERO : con(TypeInteger.constant(con)); }
public static ConstantNode con( Type t ) { return (ConstantNode)new ConstantNode(t).peephole(); }
public static ConFldOffNode off( TypeStruct base, String fname ) { return (ConFldOffNode)(new ConFldOffNode(base._name,fname).peephole()); }
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)),"'");
}
//////////////////////////////////
// Utilities for lexical analysis
// Return true and skip if "syntax" is next in the stream.
private boolean match (String syntax) { return _lexer.match (syntax); }
// Match must be "exact", not be followed by more id letters
private boolean matchx(String syntax) { return _lexer.matchx(syntax); }
private boolean matchOp(char c0 ) { return _lexer.matchOp(c0); }
private boolean matchOpx(char c0, char c1) { return _lexer.matchOpx(c0,c1); }
// Return true and do NOT skip if 'ch' is next
private boolean peek(char ch) { return _lexer.peek(ch); }
private boolean peekIsId() { return _lexer.peekIsId(); }
// ch is +/- 1, means oper++ or oper-- means postfix
private static boolean postfix(char ch) {
return (byte)ch== 1 || (byte)ch== -1;
}
public int pos() { return _lexer._position; }
private int pos(int pos) {
int old = _lexer._position;
_lexer._position = pos;
return old;
}
private Type posT(int pos) { _lexer._position = pos; return null; }
// Source code location
Lexer loc() { return new Lexer(_lexer); }
// Require and return an identifier
private String requireId() {
String id = _lexer.matchId();
if (id != null && !KEYWORDS.contains(id) ) return id.intern();
throw error("Expected an identifier, found '"+id+"'");
}
private 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
private Parser require(String syntax) { require(null, syntax); return this; }
private