* Copyright (C) 2017 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
"use strict";
function parse(program, origin, originKind, lineNumberOffset, text)
{
let lexer = new Lexer(origin, originKind, lineNumberOffset, text);
function genericConsume(callback, explanation)
{
let token = lexer.next();
if (!token)
lexer.fail("Unexpected end of file");
if (!callback(token))
lexer.fail("Unexpected token: " + token.text + "; expected: " + explanation);
return token;
}
function consume(...texts)
{
return genericConsume(token => texts.includes(token.text), texts);
}
function consumeKind(kind)
{
return genericConsume(token => token.kind == kind, kind);
}
function assertNext(...texts)
{
lexer.push(consume(...texts));
}
function genericTest(callback)
{
let token = lexer.peek();
if (token && callback(token))
return token;
return null;
}
function test(...texts)
{
return genericTest(token => texts.includes(token.text));
}
function testKind(kind)
{
return genericTest(token => token.kind == kind);
}
function tryConsume(...texts)
{
let result = test(...texts);
if (result)
lexer.next();
return result;
}
function tryConsumeKind(kind)
{
let result = testKind(kind);
if (result)
lexer.next();
return result;
}
function parseProtocolRef()
{
let protocolToken = consumeKind("identifier");
return new ProtocolRef(protocolToken, protocolToken.text);
}
function consumeEndOfTypeArgs()
{
let rightShift = tryConsume(">>");
if (rightShift)
lexer.push(new LexerToken(lexer, rightShift, rightShift.index, rightShift.kind, ">"));
else
consume(">");
}
function parseTypeParameters()
{
if (!test("<"))
return [];
let result = [];
consume("<");
while (!test(">")) {
let constexpr = lexer.backtrackingScope(() => {
let type = parseType();
let name = consumeKind("identifier");
assertNext(",", ">", ">>");
return new ConstexprTypeParameter(type.origin, name.text, type);
});
if (constexpr)
result.push(constexpr);
else {
let name = consumeKind("identifier");
let protocol = tryConsume(":") ? parseProtocolRef() : null;
result.push(new TypeVariable(name, name.text, protocol));
}
if (!tryConsume(","))
break;
}
consumeEndOfTypeArgs();
return result;
}
function parseTerm()
{
let token;
if (token = tryConsume("null"))
return new NullLiteral(token);
if (token = tryConsumeKind("identifier"))
return new VariableRef(token, token.text);
if (token = tryConsumeKind("intLiteral")) {
let intVersion = (+token.text) | 0;
if ("" + intVersion !== token.text)
lexer.fail("Integer literal is not an integer: " + token.text);
return new IntLiteral(token, intVersion);
}
if (token = tryConsumeKind("uintLiteral")) {
let uintVersion = token.text.substr(0, token.text.length - 1) >>> 0;
if (uintVersion + "u" !== token.text)
lexer.fail("Integer literal is not 32-bit unsigned integer: " + token.text);
return new UintLiteral(token, uintVersion);
}
if ((token = tryConsumeKind("intHexLiteral"))
|| (token = tryConsumeKind("uintHexLiteral"))) {
let hexString = token.text.substr(2);
if (token.kind == "uintHexLiteral")
hexString = hexString.substr(0, hexString.length - 1);
if (!hexString.length)
throw new Error("Bad hex literal: " + token);
let intVersion = parseInt(hexString, 16);
if (token.kind == "intHexLiteral")
intVersion = intVersion | 0;
else
intVersion = intVersion >>> 0;
if (intVersion.toString(16) !== hexString)
lexer.fail("Hex integer literal is not an integer: " + token.text);
if (token.kind == "intHexLiteral")
return new IntLiteral(token, intVersion);
return new UintLiteral(token, intVersion >>> 0);
}
if (token = tryConsumeKind("doubleLiteral"))
return new DoubleLiteral(token, +token.text);
if (token = tryConsumeKind("floatLiteral")) {
let text = token.text;
let d = token.text.endsWith("d");
let f = token.text.endsWith("f");
if (d && f)
throw new Error("Literal cannot be both a double literal and a float literal.");
if (d || f)
text = text.substring(0, text.length - 1);
let value = parseFloat(text);
if (d)
return new DoubleLiteral(token, value);
return new FloatLiteral(token, Math.fround(value));
}
if (token = tryConsume("true", "false"))
return new BoolLiteral(token, token.text == "true");
consume("(");
let result = parseExpression();
consume(")");
return result;
}
function parseConstexpr()
{
let token;
if (token = tryConsume("-"))
return new CallExpression(token, "operator" + token.text, [], [parseTerm()]);
let left = parseTerm();
if (token = tryConsume("."))
left = new DotExpression(token, left, consumeKind("identifier").text);
return left;
}
function parseTypeArguments()
{
if (!test("<"))
return [];
let result = [];
consume("<");
while (!test(">")) {
let typeOrVariableRef = lexer.backtrackingScope(() => {
let result = consumeKind("identifier");
assertNext(",", ">", ">>");
return new TypeOrVariableRef(result, result.text);
});
if (typeOrVariableRef)
result.push(typeOrVariableRef);
else {
let constexpr = lexer.backtrackingScope(() => {
let result = parseConstexpr();
assertNext(",", ">", ">>");
return result;
});
if (constexpr)
result.push(constexpr);
else
result.push(parseType());
}
if (!tryConsume(","))
break;
}
consumeEndOfTypeArgs();
return result;
}
function parseType()
{
let token;
let addressSpace;
let addressSpaceConsumed = false;
if (token = tryConsume(...addressSpaces))
addressSpace = token.text;
let name = consumeKind("identifier");
let typeArguments = parseTypeArguments();
let type = new TypeRef(name, name.text, typeArguments);
function getAddressSpace()
{
addressSpaceConsumed = true;
if (addressSpace)
return addressSpace;
return consume(...addressSpaces).text;
}
while (token = tryConsume("*", "[")) {
if (token.text == "*") {
type = new PtrType(token, getAddressSpace(), type);
continue;
}
if (tryConsume("]")) {
type = new ArrayRefType(token, getAddressSpace(), type);
continue;
}
type = new ArrayType(token, type, parseConstexpr());
consume("]");
}
if (addressSpace && !addressSpaceConsumed)
lexer.fail("Address space specified for type that does not need address space");
return type;
}
function parseTypeDef()
{
let origin = consume("typedef");
let name = consumeKind("identifier").text;
let typeParameters = parseTypeParameters();
consume("=");
let type = parseType();
consume(";");
return new TypeDef(origin, name, typeParameters, type);
}
function genericParseLeft(texts, nextParser, constructor)
{
let left = nextParser();
let token;
while (token = tryConsume(...texts))
left = constructor(token, left, nextParser());
return left;
}
function parseLeftOperatorCall(texts, nextParser)
{
return genericParseLeft(
texts, nextParser,
(token, left, right) =>
new CallExpression(token, "operator" + token.text, [], [left, right]));
}
function parseCallExpression()
{
let name = consumeKind("identifier");
let typeArguments = parseTypeArguments();
consume("(");
let argumentList = [];
while (!test(")")) {
let argument = parsePossibleAssignment();
argumentList.push(argument);
if (!tryConsume(","))
break;
}
consume(")");
let result = new CallExpression(name, name.text, typeArguments, argumentList);
return result;
}
function isCallExpression()
{
return lexer.testScope(() => {
consumeKind("identifier");
parseTypeArguments();
consume("(");
});
}
function emitIncrement(token, old, extraArg)
{
let args = [old];
if (extraArg)
args.push(extraArg);
let name = "operator" + token.text;
if (/=$/.test(name))
name = RegExp.leftContext;
if (name == "operator")
throw new Error("Invalid name: " + name);
return new CallExpression(token, name, [], args);
}
function finishParsingPostIncrement(token, left)
{
let readModifyWrite = new ReadModifyWriteExpression(token, left);
readModifyWrite.newValueExp = emitIncrement(token, readModifyWrite.oldValueRef());
readModifyWrite.resultExp = readModifyWrite.oldValueRef();
return readModifyWrite;
}
function parseSuffixOperator(left, acceptableOperators)
{
let token;
while (token = tryConsume(...acceptableOperators)) {
switch (token.text) {
case "++":
case "--":
return finishParsingPostIncrement(token, left);
case ".":
case "->":
if (token.text == "->")
left = new DereferenceExpression(token, left);
left = new DotExpression(token, left, consumeKind("identifier").text);
break;
case "[": {
let index = parseExpression();
consume("]");
left = new IndexExpression(token, left, index);
break;
}
default:
throw new Error("Bad token: " + token);
}
}
return left;
}
function parsePossibleSuffix()
{
let acceptableOperators = ["++", "--", ".", "->", "["];
let limitedOperators = [".", "->", "["];
let left;
if (isCallExpression()) {
left = parseCallExpression();
acceptableOperators = limitedOperators;
} else
left = parseTerm();
return parseSuffixOperator(left, acceptableOperators);
}
function finishParsingPreIncrement(token, left, extraArg)
{
let readModifyWrite = new ReadModifyWriteExpression(token, left);
readModifyWrite.newValueExp = emitIncrement(token, readModifyWrite.oldValueRef(), extraArg);
readModifyWrite.resultExp = readModifyWrite.newValueRef();
return readModifyWrite;
}
function parsePreIncrement()
{
let token = consume("++", "--");
let left = parsePossiblePrefix();
return finishParsingPreIncrement(token, left);
}
function parsePossiblePrefix()
{
let token;
if (test("++", "--"))
return parsePreIncrement();
if (token = tryConsume("+", "-", "~"))
return new CallExpression(token, "operator" + token.text, [], [parsePossiblePrefix()]);
if (token = tryConsume("*"))
return new DereferenceExpression(token, parsePossiblePrefix());
if (token = tryConsume("&"))
return new MakePtrExpression(token, parsePossiblePrefix());
if (token = tryConsume("@"))
return new MakeArrayRefExpression(token, parsePossiblePrefix());
if (token = tryConsume("!")) {
let remainder = parsePossiblePrefix();
return new LogicalNot(token, new CallExpression(remainder.origin, "bool", [], [remainder]));
}
return parsePossibleSuffix();
}
function parsePossibleProduct()
{
return parseLeftOperatorCall(["*", "/", "%"], parsePossiblePrefix);
}
function parsePossibleSum()
{
return parseLeftOperatorCall(["+", "-"], parsePossibleProduct);
}
function parsePossibleShift()
{
return parseLeftOperatorCall(["<<", ">>"], parsePossibleSum);
}
function parsePossibleRelationalInequality()
{
return parseLeftOperatorCall(["<", ">", "<=", ">="], parsePossibleShift);
}
function parsePossibleRelationalEquality()
{
return genericParseLeft(
["==", "!="], parsePossibleRelationalInequality,
(token, left, right) => {
let result = new CallExpression(token, "operator==", [], [left, right]);
if (token.text == "!=")
result = new LogicalNot(token, result);
return result;
});
}
function parsePossibleBitwiseAnd()
{
return parseLeftOperatorCall(["&"], parsePossibleRelationalEquality);
}
function parsePossibleBitwiseXor()
{
return parseLeftOperatorCall(["^"], parsePossibleBitwiseAnd);
}
function parsePossibleBitwiseOr()
{
return parseLeftOperatorCall(["|"], parsePossibleBitwiseXor);
}
function parseLeftLogicalExpression(texts, nextParser)
{
return genericParseLeft(
texts, nextParser,
(token, left, right) => new LogicalExpression(token, token.text, new CallExpression(left.origin, "bool", [], [left]), new CallExpression(right.origin, "bool", [], [right])));
}
function parsePossibleLogicalAnd()
{
return parseLeftLogicalExpression(["&&"], parsePossibleBitwiseOr);
}
function parsePossibleLogicalOr()
{
return parseLeftLogicalExpression(["||"], parsePossibleLogicalAnd);
}
function parsePossibleTernaryConditional()
{
let predicate = parsePossibleLogicalOr();
let operator = tryConsume("?");
if (!operator)
return predicate;
return new TernaryExpression(operator, predicate, parsePossibleAssignment(), parsePossibleAssignment());
}
function parsePossibleAssignment(mode)
{
let lhs = parsePossibleTernaryConditional();
let operator = tryConsume("=", "+=", "-=", "*=", "/=", "%=", "^=", "|=", "&=");
if (!operator) {
if (mode == "required")
lexer.fail("Expected assignment");
return lhs;
}
if (operator.text == "=")
return new Assignment(operator, lhs, parsePossibleAssignment());
return finishParsingPreIncrement(operator, lhs, parsePossibleAssignment());
}
function parseAssignment()
{
return parsePossibleAssignment("required");
}
function parsePostIncrement()
{
let left = parseSuffixOperator(parseTerm(), ".", "->", "[");
let token = consume("++", "--");
return finishParsingPostIncrement(token, left);
}
function parseEffectfulExpression()
{
if (isCallExpression())
return parseCallExpression();
let preIncrement = lexer.backtrackingScope(parsePreIncrement);
if (preIncrement)
return preIncrement;
let postIncrement = lexer.backtrackingScope(parsePostIncrement);
if (postIncrement)
return postIncrement;
return parseAssignment();
}
function genericParseCommaExpression(finalExpressionParser)
{
let list = [];
let origin = lexer.peek();
if (!origin)
lexer.fail("Unexpected end of file");
for (;;) {
let effectfulExpression = lexer.backtrackingScope(() => {
parseEffectfulExpression();
consume(",");
});
if (!effectfulExpression) {
let final = finalExpressionParser();
list.push(final);
break;
}
list.push(effectfulExpression);
}
if (!list.length)
throw new Error("Length should never be zero");
if (list.length == 1)
return list[0];
return new CommaExpression(origin, list);
}
function parseCommaExpression()
{
return genericParseCommaExpression(parsePossibleAssignment);
}
function parseExpression()
{
return parseCommaExpression();
}
function parseEffectfulStatement()
{
let result = genericParseCommaExpression(parseEffectfulExpression);
consume(";");
return result;
}
function parseReturn()
{
let origin = consume("return");
if (tryConsume(";"))
return new Return(origin, null);
let expression = parseExpression();
consume(";");
return new Return(origin, expression);
}
function parseBreak()
{
let origin = consume("break");
consume(";");
return new Break(origin);
}
function parseContinue()
{
let origin = consume("continue");
consume(";");
return new Continue(origin);
}
function parseIfStatement()
{
let origin = consume("if");
consume("(");
let conditional = parseExpression();
consume(")");
let body = parseStatement();
let elseBody;
if (tryConsume("else"))
elseBody = parseStatement();
return new IfStatement(origin, new CallExpression(conditional.origin, "bool", [], [conditional]), body, elseBody);
}
function parseWhile()
{
let origin = consume("while");
consume("(");
let conditional = parseExpression();
consume(")");
let body = parseStatement();
return new WhileLoop(origin, new CallExpression(conditional.origin, "bool", [], [conditional]), body);
}
function parseFor()
{
let origin = consume("for");
consume("(");
let initialization;
if (tryConsume(";"))
initialization = undefined;
else {
initialization = lexer.backtrackingScope(parseVariableDecls);
if (!initialization)
initialization = parseEffectfulStatement();
}
let condition = tryConsume(";");
if (condition)
condition = undefined;
else {
condition = parseExpression();
consume(";");
condition = new CallExpression(condition.origin, "bool", [], [condition]);
}
let increment;
if (tryConsume(")"))
increment = undefined;
else {
increment = parseExpression();
consume(")");
}
let body = parseStatement();
return new ForLoop(origin, initialization, condition, increment, body);
}
function parseDo()
{
let origin = consume("do");
let body = parseStatement();
consume("while");
consume("(");
let conditional = parseExpression();
consume(")");
return new DoWhileLoop(origin, body, new CallExpression(conditional.origin, "bool", [], [conditional]));
}
function parseVariableDecls()
{
let type = parseType();
let list = [];
do {
let name = consumeKind("identifier");
let initializer = tryConsume("=") ? parseExpression() : null;
list.push(new VariableDecl(name, name.text, type, initializer));
} while (consume(",", ";").text == ",");
return new CommaExpression(type.origin, list);
}
function parseSwitchCase()
{
let token = consume("default", "case");
let value;
if (token.text == "case")
value = parseConstexpr();
consume(":");
let body = parseBlockBody("}", "default", "case");
return new SwitchCase(token, value, body);
}
function parseSwitchStatement()
{
let origin = consume("switch");
consume("(");
let value = parseExpression();
consume(")");
consume("{");
let result = new SwitchStatement(origin, value);
while (!tryConsume("}"))
result.add(parseSwitchCase());
return result;
}
function parseStatement()
{
let token = lexer.peek();
if (token.text == ";") {
lexer.next();
return null;
}
if (token.text == "return")
return parseReturn();
if (token.text == "break")
return parseBreak();
if (token.text == "continue")
return parseContinue();
if (token.text == "while")
return parseWhile();
if (token.text == "do")
return parseDo();
if (token.text == "for")
return parseFor();
if (token.text == "if")
return parseIfStatement();
if (token.text == "switch")
return parseSwitchStatement();
if (token.text == "trap") {
let origin = consume("trap");
consume(";");
return new TrapStatement(origin);
}
if (token.text == "{")
return parseBlock();
let variableDecl = lexer.backtrackingScope(parseVariableDecls);
if (variableDecl)
return variableDecl;
return parseEffectfulStatement();
}
function parseBlockBody(...terminators)
{
let block = new Block(origin);
while (!test(...terminators)) {
let statement = parseStatement();
if (statement)
block.add(statement);
}
return block;
}
function parseBlock()
{
let origin = consume("{");
let block = parseBlockBody("}");
consume("}");
return block;
}
function parseParameter()
{
let type = parseType();
let name = tryConsumeKind("identifier");
return new FuncParameter(type.origin, name ? name.text : null, type);
}
function parseParameters()
{
consume("(");
let parameters = [];
while (!test(")")) {
parameters.push(parseParameter());
if (!tryConsume(","))
break;
}
consume(")");
return parameters;
}
function parseFuncName()
{
if (tryConsume("operator")) {
let token = consume("+", "-", "*", "/", "%", "^", "&", "|", "<", ">", "<=", ">=", "==", "++", "--", ".", "~", "<<", ">>", "[");
if (token.text == "&") {
if (tryConsume("[")) {
consume("]");
return "operator&[]";
}
if (tryConsume("."))
return "operator&." + consumeKind("identifier").text;
return "operator&";
}
if (token.text == ".") {
let result = "operator." + consumeKind("identifier").text;
if (tryConsume("="))
result += "=";
return result;
}
if (token.text == "[") {
consume("]");
let result = "operator[]";
if (tryConsume("="))
result += "=";
return result;
}
return "operator" + token.text;
}
return consumeKind("identifier").text;
}
function parseFuncDecl()
{
let origin;
let returnType;
let name;
let typeParameters;
let isCast;
let shaderType;
let operatorToken = tryConsume("operator");
if (operatorToken) {
origin = operatorToken;
typeParameters = parseTypeParameters();
returnType = parseType();
name = "operator cast";
isCast = true;
} else {
shaderType = tryConsume("vertex", "fragment");
returnType = parseType();
if (shaderType) {
origin = shaderType;
shaderType = shaderType.text;
} else
origin = returnType.origin;
name = parseFuncName();
typeParameters = parseTypeParameters();
isCast = false;
}
let parameters = parseParameters();
return new Func(origin, name, returnType, typeParameters, parameters, isCast, shaderType);
}
function parseProtocolFuncDecl()
{
let func = parseFuncDecl();
return new ProtocolFuncDecl(func.origin, func.name, func.returnType, func.typeParameters, func.parameters, func.isCast, func.shaderType);
}
function parseFuncDef()
{
let func = parseFuncDecl();
let body = parseBlock();
return new FuncDef(func.origin, func.name, func.returnType, func.typeParameters, func.parameters, body, func.isCast, func.shaderType);
}
function parseProtocolDecl()
{
let origin = consume("protocol");
let name = consumeKind("identifier").text;
let result = new ProtocolDecl(origin, name);
if (tryConsume(":")) {
while (!test("{")) {
result.addExtends(parseProtocolRef());
if (!tryConsume(","))
break;
}
}
consume("{");
while (!tryConsume("}")) {
result.add(parseProtocolFuncDecl());
consume(";");
}
return result;
}
function parseField()
{
let type = parseType();
let name = consumeKind("identifier");
consume(";");
return new Field(name, name.text, type);
}
function parseStructType()
{
let origin = consume("struct");
let name = consumeKind("identifier").text;
let typeParameters = parseTypeParameters();
let result = new StructType(origin, name, typeParameters);
consume("{");
while (!tryConsume("}"))
result.add(parseField());
return result;
}
function parseNativeFunc()
{
let func = parseFuncDecl();
consume(";");
return new NativeFunc(func.origin, func.name, func.returnType, func.typeParameters, func.parameters, func.isCast, func.shaderType);
}
function parseNative()
{
let origin = consume("native");
if (tryConsume("typedef")) {
let name = consumeKind("identifier");
let parameters = parseTypeParameters();
consume(";");
return new NativeType(origin, name.text, parameters);
}
return parseNativeFunc();
}
function parseRestrictedFuncDef()
{
consume("restricted");
let result;
if (tryConsume("native"))
result = parseNativeFunc();
else
result = parseFuncDef();
result.isRestricted = true;
return result;
}
function parseEnumMember()
{
let name = consumeKind("identifier");
let value = null;
if (tryConsume("="))
value = parseConstexpr();
return new EnumMember(name, name.text, value);
}
function parseEnumType()
{
consume("enum");
let name = consumeKind("identifier");
let baseType;
if (tryConsume(":"))
baseType = parseType();
else
baseType = new TypeRef(name, "int", []);
consume("{");
let result = new EnumType(name, name.text, baseType);
while (!test("}")) {
result.add(parseEnumMember());
if (!tryConsume(","))
break;
}
consume("}");
return result;
}
for (;;) {
let token = lexer.peek();
if (!token)
return;
if (token.text == ";")
lexer.next();
else if (token.text == "typedef")
program.add(parseTypeDef());
else if (originKind == "native" && token.text == "native")
program.add(parseNative());
else if (originKind == "native" && token.text == "restricted")
program.add(parseRestrictedFuncDef());
else if (token.text == "struct")
program.add(parseStructType());
else if (token.text == "enum")
program.add(parseEnumType());
else if (token.text == "protocol")
program.add(parseProtocolDecl());
else
program.add(parseFuncDef());
}
}
