initial checkin of SkSL compiler

src/sksl/SkSLParser.cpp

+/*
+ * Copyright 2016 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+ 
+#include "stdio.h"
+#include "SkSLParser.h"
+#include "SkSLToken.h"
+
+#define register
+#ifdef __clang__
+#pragma clang diagnostic push
+#pragma clang diagnostic ignored "-Wunneeded-internal-declaration"
+#endif
+#include "lex.sksl.c"
+#ifdef __clang__
+#pragma clang diagnostic pop
+#endif
+#undef register
+
+#include "ast/SkSLASTBinaryExpression.h"
+#include "ast/SkSLASTBlock.h"
+#include "ast/SkSLASTBoolLiteral.h"
+#include "ast/SkSLASTBreakStatement.h"
+#include "ast/SkSLASTCallSuffix.h"
+#include "ast/SkSLASTContinueStatement.h"
+#include "ast/SkSLASTDiscardStatement.h"
+#include "ast/SkSLASTDoStatement.h"
+#include "ast/SkSLASTExpression.h"
+#include "ast/SkSLASTExpressionStatement.h"
+#include "ast/SkSLASTExtension.h"
+#include "ast/SkSLASTFieldSuffix.h"
+#include "ast/SkSLASTFloatLiteral.h"
+#include "ast/SkSLASTForStatement.h"
+#include "ast/SkSLASTFunction.h"
+#include "ast/SkSLASTIdentifier.h"
+#include "ast/SkSLASTIfStatement.h"
+#include "ast/SkSLASTIndexSuffix.h"
+#include "ast/SkSLASTInterfaceBlock.h"
+#include "ast/SkSLASTIntLiteral.h"
+#include "ast/SkSLASTParameter.h"
+#include "ast/SkSLASTPrefixExpression.h"
+#include "ast/SkSLASTReturnStatement.h"
+#include "ast/SkSLASTStatement.h"
+#include "ast/SkSLASTSuffixExpression.h"
+#include "ast/SkSLASTTernaryExpression.h"
+#include "ast/SkSLASTType.h"
+#include "ast/SkSLASTVarDeclaration.h"
+#include "ast/SkSLASTVarDeclarationStatement.h"
+#include "ast/SkSLASTWhileStatement.h"
+#include "ir/SkSLSymbolTable.h"
+
+namespace SkSL {
+
+Parser::Parser(std::string text, std::shared_ptr<SymbolTable> types, ErrorReporter& errors) 
+: fPushback(Position(-1, -1), Token::INVALID_TOKEN, std::string(""))
+, fTypes(types)
+, fErrors(errors) {
+    fBuffer = sksl_scan_string(text.c_str());
+    yylineno = 1;
+
+    if (false) {
+        // avoid unused warning
+        yyunput(0, nullptr);
+    }
+}
+
+Parser::~Parser() {
+    sksl_delete_buffer(fBuffer);
+}
+
+Token Parser::nextToken() {
+    if (fPushback.fKind != Token::INVALID_TOKEN) {
+        Token result = fPushback;
+        fPushback.fKind = Token::INVALID_TOKEN;
+        fPushback.fText = std::string("");
+        return result;
+    }
+    int token = sksllex();
+    return Token(Position(yylineno, -1), (Token::Kind) token, 
+                 token == Token::END_OF_FILE ? "<end of file>" : std::string(sksltext));
+}
+
+void Parser::pushback(Token t) {
+    fPushback = t;
+}
+
+Token Parser::peek() {
+    fPushback = this->nextToken();
+    return fPushback;
+}
+
+bool Parser::expect(Token::Kind kind, std::string expected, Token* result) {
+    Token next = this->nextToken();
+    if (next.fKind == kind) {
+        if (result != nullptr) {
+            *result = next;
+        }
+        return true;
+    } else {
+        this->error(next.fPosition, "expected " + expected + ", but found '" + 
+                                    next.fText + "'");
+        return false;
+    }
+}
+
+void Parser::error(Position p, std::string msg) {
+    fErrors.error(p, msg);
+}
+
+/* (precision | directive | declaration)* END_OF_FILE */
+std::vector<std::unique_ptr<ASTDeclaration>> Parser::file() {
+    std::vector<std::unique_ptr<ASTDeclaration>> result;
+    for (;;) {
+        switch (this->peek().fKind) {
+            case Token::END_OF_FILE:
+                return result;
+            case Token::PRECISION:
+                this->precision();
+                break;
+            case Token::DIRECTIVE: {
+                std::unique_ptr<ASTDeclaration> decl = this->directive();
+                if (decl != nullptr) {
+                    result.push_back(std::move(decl));
+                }
+                break;
+            }
+            default: {
+                std::unique_ptr<ASTDeclaration> decl = this->declaration();
+                if (decl == nullptr) {
+                    return result;
+                }
+                result.push_back(std::move(decl));
+            }
+        }
+    }
+}
+
+/* PRECISION (LOWP | MEDIUMP | HIGHP) type SEMICOLON */
+void Parser::precision() {
+    if (!this->expect(Token::PRECISION, "'precision'")) {
+        return;
+    }
+    Token p = this->nextToken();
+    switch (p.fKind) {
+        case Token::LOWP: // fall through
+        case Token::MEDIUMP: // fall through
+        case Token::HIGHP:
+            break;
+        default:
+            this->error(p.fPosition, "expected 'lowp', 'mediump', or 'highp', but found '" + 
+                                     p.fText + "'");
+            return;
+    }
+    if (this->type() == nullptr) {
+        return;
+    }
+    this->expect(Token::SEMICOLON, "';'");
+}
+
+/* DIRECTIVE(#version) INT_LITERAL | DIRECTIVE(#extension) IDENTIFIER COLON IDENTIFIER */
+std::unique_ptr<ASTDeclaration> Parser::directive() {
+    Token start;
+    if (!this->expect(Token::DIRECTIVE, "a directive", &start)) {
+        return nullptr;
+    }
+    if (start.fText == "#version") {
+        this->expect(Token::INT_LITERAL, "a version number");
+        return nullptr;
+    } else if (start.fText == "#extension") {
+        Token name;
+        if (!this->expect(Token::IDENTIFIER, "an identifier", &name)) {
+            return nullptr;
+        }
+        if (!this->expect(Token::COLON, "':'")) {
+            return nullptr;
+        }
+        // FIXME: need to start paying attention to this token
+        if (!this->expect(Token::IDENTIFIER, "an identifier")) {
+            return nullptr;
+        }
+        return std::unique_ptr<ASTDeclaration>(new ASTExtension(start.fPosition, name.fText));
+    } else {
+        this->error(start.fPosition, "unsupport directive '" + start.fText + "'");
+        return nullptr;
+    }
+}
+
+/* modifiers (type IDENTIFIER ((LPAREN parameter (COMMA parameter)* RPAREN  (block | SEMICOLON)) | 
+   SEMICOLON) | interfaceBlock) */
+std::unique_ptr<ASTDeclaration> Parser::declaration() {
+    ASTModifiers modifiers = this->modifiers();
+    Token lookahead = this->peek();
+    if (lookahead.fKind == Token::IDENTIFIER && !this->isType(lookahead.fText)) {
+        // we have an identifier that's not a type, could be the start of an interface block
+        return this->interfaceBlock(modifiers);
+    }
+    std::unique_ptr<ASTType> type(this->type());
+    if (!type) {
+        return nullptr;
+    }
+    if (type->fKind == ASTType::kStruct_Kind && peek().fKind == Token::SEMICOLON) {
+        this->nextToken();
+        std::vector<std::string> names;
+        std::vector<std::vector<std::unique_ptr<ASTExpression>>> sizes;
+        std::vector<std::unique_ptr<ASTExpression>> values;
+        return std::unique_ptr<ASTVarDeclaration>(new ASTVarDeclaration(std::move(modifiers), 
+                                                                        std::move(type), 
+                                                                        names, 
+                                                                        std::move(sizes), 
+                                                                        std::move(values)));
+    }
+    Token name;
+    if (!this->expect(Token::IDENTIFIER, "an identifier", &name)) {
+        return nullptr;
+    }
+    if (!modifiers.fBits && this->peek().fKind == Token::LPAREN) {
+        this->nextToken();
+        std::vector<std::unique_ptr<ASTParameter>> parameters;
+        while (this->peek().fKind != Token::RPAREN) {
+            if (parameters.size() > 0) {
+                if (!this->expect(Token::COMMA, "','")) {
+                    return nullptr;
+                }
+            }
+            std::unique_ptr<ASTParameter> parameter = this->parameter();
+            if (!parameter) {
+                return nullptr;
+            }
+            parameters.push_back(std::move(parameter));
+        }
+        this->nextToken();
+        std::unique_ptr<ASTBlock> body;
+        if (this->peek().fKind == Token::SEMICOLON) {
+            this->nextToken();
+        } else {
+            body = this->block();
+            if (!body) {
+                return nullptr;
+            }
+        }
+        return std::unique_ptr<ASTDeclaration>(new ASTFunction(name.fPosition, std::move(type), 
+                                                             name.fText, std::move(parameters), 
+                                                             std::move(body)));
+    } else {
+        return this->varDeclarationEnd(modifiers, std::move(type), name.fText);
+    }
+}
+
+/* STRUCT IDENTIFIER LBRACE varDeclaration* RBRACE */
+std::unique_ptr<ASTType> Parser::structDeclaration() {
+    if (!this->expect(Token::STRUCT, "'struct'")) {
+        return nullptr;
+    }
+    Token name;
+    if (!this->expect(Token::IDENTIFIER, "an identifier", &name)) {
+        return nullptr;
+    }
+    if (!this->expect(Token::LBRACE, "'{'")) {
+        return nullptr;
+    }
+    std::vector<Type::Field> fields;
+    while (this->peek().fKind != Token::RBRACE) {
+        std::unique_ptr<ASTVarDeclaration> decl = this->varDeclaration();
+        if (decl == nullptr) {
+            return nullptr;
+        }
+        for (size_t i = 0; i < decl->fNames.size(); i++) {
+            std::shared_ptr<Type> type = std::static_pointer_cast<Type>(
+                                                                    (*fTypes) [decl->fType->fName]);
+            for (int j = (int) decl->fSizes[i].size() - 1; j >= 0; j--) {
+                if (decl->fSizes[i][j]->fKind == ASTExpression::kInt_Kind) {
+                    this->error(decl->fPosition, "array size in struct field must be a constant");
+                }
+                uint64_t columns = ((ASTIntLiteral&) *decl->fSizes[i][j]).fValue;
+                std::string name = type->name() + "[" + to_string(columns) + "]";
+                type = std::shared_ptr<Type>(new Type(name, Type::kArray_Kind, type, 
+                                             (int) columns));
+            }
+            fields.push_back(Type::Field(decl->fModifiers, decl->fNames[i], type));
+            if (decl->fValues[i] != nullptr) {
+                this->error(decl->fPosition, "initializers are not permitted on struct fields");
+            }
+        }
+    }
+    if (!this->expect(Token::RBRACE, "'}'")) {
+        return nullptr;
+    }
+    std::shared_ptr<Type> type(new Type(name.fText, fields));
+    (*fTypes).add(type->fName, type);
+    return std::unique_ptr<ASTType>(new ASTType(name.fPosition, type->fName, 
+                                                ASTType::kStruct_Kind));
+}
+
+/* modifiers type IDENTIFIER (LBRACKET INT_LITERAL RBRACKET)? */
+std::unique_ptr<ASTParameter> Parser::parameter() {
+    ASTModifiers modifiers = this->modifiers();
+    std::unique_ptr<ASTType> type = this->type();
+    if (!type) {
+        return nullptr;
+    }
+    Token name;
+    if (!this->expect(Token::IDENTIFIER, "an identifier", &name)) {
+        return nullptr;
+    }
+    std::vector<int> sizes;
+    while (this->peek().fKind == Token::LBRACKET) {
+        this->nextToken();
+        Token sizeToken;
+        if (!this->expect(Token::INT_LITERAL, "a non-negative integer", &sizeToken)) {
+            return nullptr;
+        }
+        sizes.push_back(SkSL::stoi(sizeToken.fText));
+        if (!this->expect(Token::RBRACKET, "']'")) {
+            return nullptr;
+        }
+    }
+    return std::unique_ptr<ASTParameter>(new ASTParameter(name.fPosition, modifiers, 
+                                                          std::move(type), name.fText, sizes));
+}
+
+static int read_layout_int(Parser* parser) {
+    if (!parser->expect(Token::EQ, "'='")) {
+        return -1;
+    }
+    Token resultToken;
+    if (parser->expect(Token::INT_LITERAL, "a non-negative integer", &resultToken)) {
+        return SkSL::stoi(resultToken.fText);
+    }
+    return -1;
+}
+
+/* LAYOUT LPAREN IDENTIFIER EQ INT_LITERAL (COMMA IDENTIFIER EQ INT_LITERAL)* 
+   RPAREN */
+ASTLayout Parser::layout() {
+    int location = -1;
+    int binding = -1;
+    int index = -1;
+    int set = -1;
+    int builtin = -1;
+    if (this->peek().fKind == Token::LAYOUT) {
+        this->nextToken();
+        if (!this->expect(Token::LPAREN, "'('")) {
+            return ASTLayout(location, binding, index, set, builtin);
+        }
+        for (;;) {
+            Token t = this->nextToken();
+            if (t.fText == "location") {
+                location = read_layout_int(this);
+            } else if (t.fText == "binding") {
+                binding = read_layout_int(this);
+            } else if (t.fText == "index") {
+                index = read_layout_int(this);
+            } else if (t.fText == "set") {
+                set = read_layout_int(this);
+            } else if (t.fText == "builtin") {
+                builtin = read_layout_int(this);
+            } else {
+                this->error(t.fPosition, ("'" + t.fText + 
+                                          "' is not a valid layout qualifier").c_str());
+            }
+            if (this->peek().fKind == Token::RPAREN) {
+                this->nextToken();
+                break;
+            }
+            if (!this->expect(Token::COMMA, "','")) {
+                break;
+            }
+        }
+    }
+    return ASTLayout(location, binding, index, set, builtin);
+}
+
+/* layout? (UNIFORM | CONST | IN | OUT | INOUT | LOWP | 
+   MEDIUMP | HIGHP)* */
+ASTModifiers Parser::modifiers() {
+    ASTLayout layout = this->layout();
+    int bits = 0;
+    for (;;) {
+        // TODO: handle duplicate / incompatible bits
+        switch (peek().fKind) {
+            case Token::UNIFORM:
+                this->nextToken();
+                bits |= ASTModifiers::kUniform_Bit;
+                break;
+            case Token::CONST:
+                this->nextToken();
+                bits |= ASTModifiers::kConst_Bit;
+                break;
+            case Token::IN:
+                this->nextToken();
+                bits |= ASTModifiers::kIn_Bit;
+                break;
+            case Token::OUT:
+                this->nextToken();
+                bits |= ASTModifiers::kOut_Bit;
+                break;
+            case Token::INOUT:
+                this->nextToken();
+                bits |= ASTModifiers::kIn_Bit;
+                bits |= ASTModifiers::kOut_Bit;
+                break;
+            case Token::LOWP:
+                this->nextToken();
+                bits |= ASTModifiers::kLowp_Bit;
+                break;
+            case Token::MEDIUMP:
+                this->nextToken();
+                bits |= ASTModifiers::kMediump_Bit;
+                break;
+            case Token::HIGHP:
+                this->nextToken();
+                bits |= ASTModifiers::kHighp_Bit;
+                break;
+            default:
+                return ASTModifiers(layout, bits);
+        }
+    }
+}
+
+/* ifStatement | forStatement | doStatement | whileStatement | block | expression */
+std::unique_ptr<ASTStatement> Parser::statement() {
+    Token start = this->peek();
+    switch (start.fKind) {
+        case Token::IF:
+            return this->ifStatement();
+        case Token::FOR:
+            return this->forStatement();
+        case Token::DO:
+            return this->doStatement();
+        case Token::WHILE:
+            return this->whileStatement();
+        case Token::RETURN:
+            return this->returnStatement();
+        case Token::BREAK:
+            return this->breakStatement();
+        case Token::CONTINUE:
+            return this->continueStatement();
+        case Token::DISCARD:
+            return this->discardStatement();
+        case Token::LBRACE:
+            return this->block();
+        case Token::SEMICOLON:
+            this->nextToken(); 
+            return std::unique_ptr<ASTStatement>(new ASTBlock(start.fPosition, 
+                                                std::vector<std::unique_ptr<ASTStatement>>()));
+        case Token::CONST:   // fall through
+        case Token::HIGHP:   // fall through
+        case Token::MEDIUMP: // fall through
+        case Token::LOWP:
+            return std::unique_ptr<ASTStatement>(new ASTVarDeclarationStatement(
+                                                                           this->varDeclaration()));
+        case Token::IDENTIFIER:
+            if (this->isType(start.fText)) {
+                return std::unique_ptr<ASTStatement>(new ASTVarDeclarationStatement(
+                                                                           this->varDeclaration()));
+            }
+            // fall through
+        default:
+            return this->expressionStatement();
+    }    
+}
+
+/* IDENTIFIER(type) | structDeclaration */
+std::unique_ptr<ASTType> Parser::type() {
+    if (this->peek().fKind == Token::STRUCT) {
+        return this->structDeclaration();
+    }
+    Token type;
+    if (!this->expect(Token::IDENTIFIER, "a type", &type)) {
+        return nullptr;
+    }
+    if (!this->isType(type.fText)) {
+        this->error(type.fPosition, ("no type named '" + type.fText + "'").c_str());
+        return nullptr;
+    }
+    return std::unique_ptr<ASTType>(new ASTType(type.fPosition, type.fText, 
+                                                ASTType::kIdentifier_Kind));
+}
+
+/* IDENTIFIER LBRACE varDeclaration* RBRACE */
+std::unique_ptr<ASTDeclaration> Parser::interfaceBlock(ASTModifiers mods) {
+    Token name;
+    if (!this->expect(Token::IDENTIFIER, "an identifier", &name)) {
+        return nullptr;
+    }
+    if (peek().fKind != Token::LBRACE) {
+        // we only get into interfaceBlock if we found a top-level identifier which was not a type.
+        // 99% of the time, the user was not actually intending to create an interface block, so 
+        // it's better to report it as an unknown type
+        this->error(name.fPosition, "no type named '" + name.fText + "'");
+    }
+    this->nextToken();
+    std::vector<std::unique_ptr<ASTVarDeclaration>> decls; 
+    while (this->peek().fKind != Token::RBRACE) {
+        std::unique_ptr<ASTVarDeclaration> decl = this->varDeclaration();
+        if (decl == nullptr) {
+            return nullptr;
+        }
+        decls.push_back(std::move(decl));
+    }
+    this->nextToken();
+    std::string valueName;
+    if (this->peek().fKind == Token::IDENTIFIER) {
+        valueName = this->nextToken().fText;
+    }
+    this->expect(Token::SEMICOLON, "';'");
+    return std::unique_ptr<ASTDeclaration>(new ASTInterfaceBlock(name.fPosition, mods, 
+                                                                 name.fText, valueName,
+                                                                 std::move(decls)));
+}
+
+/* (LBRACKET expression? RBRACKET)* (EQ expression)? (COMMA IDENTIFER 
+   (LBRACKET expression? RBRACKET)* (EQ expression)?)* SEMICOLON */
+std::unique_ptr<ASTVarDeclaration> Parser::varDeclarationEnd(ASTModifiers mods,
+                                                             std::unique_ptr<ASTType> type,
+                                                             std::string name) {
+    std::vector<std::string> names;
+    std::vector<std::vector<std::unique_ptr<ASTExpression>>> sizes;
+    names.push_back(name);
+    std::vector<std::unique_ptr<ASTExpression>> currentVarSizes;
+    while (this->peek().fKind == Token::LBRACKET) {
+        this->nextToken();
+        if (this->peek().fKind == Token::RBRACKET) {
+            this->nextToken();
+            currentVarSizes.push_back(nullptr);
+        }
+        else {
+            std::unique_ptr<ASTExpression> size(this->expression());
+            if (!size) {
+                return nullptr;
+            }
+            currentVarSizes.push_back(std::move(size));
+            if (!this->expect(Token::RBRACKET, "']'")) {
+                return nullptr;
+            }
+        }
+    }
+    sizes.push_back(std::move(currentVarSizes));
+    std::vector<std::unique_ptr<ASTExpression>> values;
+    if (this->peek().fKind == Token::EQ) {
+        this->nextToken();
+        std::unique_ptr<ASTExpression> value(this->expression());
+        if (!value) {
+            return nullptr;
+        }
+        values.push_back(std::move(value));
+    } else {
+        values.push_back(nullptr);
+    }
+    while (this->peek().fKind == Token::COMMA) {
+        this->nextToken();
+        Token name;
+        if (!this->expect(Token::IDENTIFIER, "an identifier", &name)) {
+            return nullptr;
+        }
+        names.push_back(name.fText);
+        currentVarSizes.clear();
+        while (this->peek().fKind == Token::LBRACKET) {
+            this->nextToken();
+            if (this->peek().fKind == Token::RBRACKET) {
+                this->nextToken();
+                currentVarSizes.push_back(nullptr);
+            }
+            else {
+                std::unique_ptr<ASTExpression> size(this->expression());
+                if (!size) {
+                    return nullptr;
+                }
+                currentVarSizes.push_back(std::move(size));
+                if (!this->expect(Token::RBRACKET, "']'")) {
+                    return nullptr;
+                }
+            }
+        }
+        sizes.push_back(std::move(currentVarSizes));
+        if (this->peek().fKind == Token::EQ) {
+            this->nextToken();
+            std::unique_ptr<ASTExpression> value(this->expression());
+            if (!value) {
+                return nullptr;
+            }
+            values.push_back(std::move(value));
+        } else {
+            values.push_back(nullptr);
+        }
+    }
+    if (!this->expect(Token::SEMICOLON, "';'")) {
+        return nullptr;
+    }
+    return std::unique_ptr<ASTVarDeclaration>(new ASTVarDeclaration(std::move(mods), 
+                                                                    std::move(type), 
+                                                                    names, 
+                                                                    std::move(sizes), 
+                                                                    std::move(values)));
+}
+
+/* modifiers type IDENTIFIER (EQ expression)? (COMMA IDENTIFER (EQ expression)?)* SEMICOLON */
+std::unique_ptr<ASTVarDeclaration> Parser::varDeclaration() {
+    ASTModifiers modifiers = this->modifiers();
+    std::unique_ptr<ASTType> type(this->type());
+    if (!type) {
+        return nullptr;
+    }
+    Token name;
+    if (!this->expect(Token::IDENTIFIER, "an identifier", &name)) {
+        return nullptr;
+    }
+    return this->varDeclarationEnd(std::move(modifiers), std::move(type), name.fText);
+}
+
+/* IF LPAREN expression RPAREN statement (ELSE statement)? */
+std::unique_ptr<ASTIfStatement> Parser::ifStatement() {
+    Token start;
+    if (!this->expect(Token::IF, "'if'", &start)) {
+        return nullptr;
+    }
+    if (!this->expect(Token::LPAREN, "'('")) {
+        return nullptr;
+    }
+    std::unique_ptr<ASTExpression> test(this->expression());
+    if (test == nullptr) {
+        return nullptr;
+    }
+    if (!this->expect(Token::RPAREN, "')'")) {
+        return nullptr;
+    }
+    std::unique_ptr<ASTStatement> ifTrue(this->statement());
+    if (ifTrue == nullptr) {
+        return nullptr;
+    }
+    std::unique_ptr<ASTStatement> ifFalse;
+    if (this->peek().fKind == Token::ELSE) {
+        this->nextToken();
+        ifFalse = this->statement();
+        if (!ifFalse) {
+            return nullptr;
+        }
+    }
+    return std::unique_ptr<ASTIfStatement>(new ASTIfStatement(start.fPosition, std::move(test), 
+                                                              std::move(ifTrue), 
+                                                              std::move(ifFalse)));
+}
+
+/* DO statement WHILE LPAREN expression RPAREN SEMICOLON */
+std::unique_ptr<ASTDoStatement> Parser::doStatement() {
+    Token start;
+    if (!this->expect(Token::DO, "'do'", &start)) {
+        return nullptr;
+    }
+    std::unique_ptr<ASTStatement> statement(this->statement());
+    if (statement == nullptr) {
+        return nullptr;
+    }
+    if (!this->expect(Token::WHILE, "'while'")) {
+        return nullptr;
+    }
+    if (!this->expect(Token::LPAREN, "'('")) {
+        return nullptr;
+    }
+    std::unique_ptr<ASTExpression> test(this->expression());
+    if (test == nullptr) {
+        return nullptr;
+    }
+    if (!this->expect(Token::RPAREN, "')'")) {
+        return nullptr;
+    }
+    if (!this->expect(Token::SEMICOLON, "';'")) {
+        return nullptr;
+    }
+    return std::unique_ptr<ASTDoStatement>(new ASTDoStatement(start.fPosition, 
+                                                              std::move(test), 
+                                                              std::move(statement)));
+}
+
+/* WHILE LPAREN expression RPAREN STATEMENT */
+std::unique_ptr<ASTWhileStatement> Parser::whileStatement() {
+    Token start;
+    if (!this->expect(Token::WHILE, "'while'", &start)) {
+        return nullptr;
+    }
+    if (!this->expect(Token::LPAREN, "'('")) {
+        return nullptr;
+    }
+    std::unique_ptr<ASTExpression> test(this->expression());
+    if (test == nullptr) {
+        return nullptr;
+    }
+    if (!this->expect(Token::RPAREN, "')'")) {
+        return nullptr;
+    }
+    std::unique_ptr<ASTStatement> statement(this->statement());
+    if (statement == nullptr) {
+        return nullptr;
+    }
+    return std::unique_ptr<ASTWhileStatement>(new ASTWhileStatement(start.fPosition, 
+                                                                    std::move(test), 
+                                                                    std::move(statement)));
+}
+
+/* RETURN expression? SEMICOLON */
+std::unique_ptr<ASTReturnStatement> Parser::returnStatement() {
+    Token start;
+    if (!this->expect(Token::RETURN, "'return'", &start)) {
+        return nullptr;
+    }
+    std::unique_ptr<ASTExpression> expression;
+    if (this->peek().fKind != Token::SEMICOLON) {
+        expression = this->expression();
+        if (!expression) {
+            return nullptr;
+        }
+    }
+    if (!this->expect(Token::SEMICOLON, "';'")) {
+        return nullptr;
+    }
+    return std::unique_ptr<ASTReturnStatement>(new ASTReturnStatement(start.fPosition, 
+                                                                      std::move(expression)));
+}
+
+/* BREAK SEMICOLON */
+std::unique_ptr<ASTBreakStatement> Parser::breakStatement() {
+    Token start;
+    if (!this->expect(Token::BREAK, "'break'", &start)) {
+        return nullptr;
+    }
+    if (!this->expect(Token::SEMICOLON, "';'")) {
+        return nullptr;
+    }
+    return std::unique_ptr<ASTBreakStatement>(new ASTBreakStatement(start.fPosition));
+}
+
+/* CONTINUE SEMICOLON */
+std::unique_ptr<ASTContinueStatement> Parser::continueStatement() {
+    Token start;
+    if (!this->expect(Token::CONTINUE, "'continue'", &start)) {
+        return nullptr;
+    }
+    if (!this->expect(Token::SEMICOLON, "';'")) {
+        return nullptr;
+    }
+    return std::unique_ptr<ASTContinueStatement>(new ASTContinueStatement(start.fPosition));
+}
+
+/* DISCARD SEMICOLON */
+std::unique_ptr<ASTDiscardStatement> Parser::discardStatement() {
+    Token start;
+    if (!this->expect(Token::DISCARD, "'continue'", &start)) {
+        return nullptr;
+    }
+    if (!this->expect(Token::SEMICOLON, "';'")) {
+        return nullptr;
+    }
+    return std::unique_ptr<ASTDiscardStatement>(new ASTDiscardStatement(start.fPosition));
+}
+
+bool Parser::isType(std::string name) {
+    return (*fTypes)[name] != nullptr;
+}
+
+/* FOR LPAREN (declaration | expression)? SEMICOLON expression? SEMICOLON expression? RPAREN 
+   STATEMENT */
+std::unique_ptr<ASTForStatement> Parser::forStatement() {
+    Token start;
+    if (!this->expect(Token::FOR, "'for'", &start)) {
+        return nullptr;
+    }
+    if (!this->expect(Token::LPAREN, "'('")) {
+        return nullptr;
+    }
+    std::unique_ptr<ASTStatement> initializer;
+    Token nextToken = this->peek();
+    switch (nextToken.fKind) {
+        case Token::SEMICOLON: 
+            break;
+        case Token::CONST:
+            initializer = std::unique_ptr<ASTStatement>(new ASTVarDeclarationStatement(
+                                                                           this->varDeclaration()));
+            break;
+        case Token::IDENTIFIER: 
+            if (this->isType(nextToken.fText)) {
+                initializer = std::unique_ptr<ASTStatement>(new ASTVarDeclarationStatement(
+                                                                           this->varDeclaration()));
+                break;
+            }
+            // fall through
+        default:
+            initializer = this->expressionStatement();
+    }
+    std::unique_ptr<ASTExpression> test;
+    if (this->peek().fKind != Token::SEMICOLON) {
+        test = this->expression();
+        if (!test) {
+            return nullptr;
+        }
+    }
+    if (!this->expect(Token::SEMICOLON, "';'")) {
+        return nullptr;
+    }
+    std::unique_ptr<ASTExpression> next;
+    if (this->peek().fKind != Token::SEMICOLON) {
+        next = this->expression();
+        if (!next) {
+            return nullptr;
+        }
+    }
+    if (!this->expect(Token::RPAREN, "')'")) {
+        return nullptr;
+    }
+    std::unique_ptr<ASTStatement> statement(this->statement());
+    if (statement == nullptr) {
+        return nullptr;
+    }
+    return std::unique_ptr<ASTForStatement>(new ASTForStatement(start.fPosition, 
+                                                                std::move(initializer),
+                                                                std::move(test), std::move(next),
+                                                                std::move(statement)));
+}
+
+/* LBRACE statement* RBRACE */
+std::unique_ptr<ASTBlock> Parser::block() {
+    Token start;
+    if (!this->expect(Token::LBRACE, "'{'", &start)) {
+        return nullptr;
+    }
+    std::vector<std::unique_ptr<ASTStatement>> statements;
+    for (;;) {
+        switch (this->peek().fKind) {
+            case Token::RBRACE: 
+                this->nextToken();
+                return std::unique_ptr<ASTBlock>(new ASTBlock(start.fPosition, 
+                                                              std::move(statements)));
+            case Token::END_OF_FILE: 
+                this->error(this->peek().fPosition, "expected '}', but found end of file");
+                return nullptr;
+            default: {
+                std::unique_ptr<ASTStatement> statement = this->statement();
+                if (statement == nullptr) {
+                    return nullptr;
+                }
+                statements.push_back(std::move(statement));
+            }
+        }
+    }
+}
+
+/* expression SEMICOLON */
+std::unique_ptr<ASTExpressionStatement> Parser::expressionStatement() {
+    std::unique_ptr<ASTExpression> expr = this->expression();
+    if (expr) {
+        if (this->expect(Token::SEMICOLON, "';'")) {
+            ASTExpressionStatement* result = new ASTExpressionStatement(std::move(expr));
+            return std::unique_ptr<ASTExpressionStatement>(result);
+        }
+    }
+    return nullptr;
+}
+
+/* assignmentExpression */
+std::unique_ptr<ASTExpression> Parser::expression() {
+    return this->assignmentExpression();
+}
+
+/* ternaryExpression ((EQEQ | STAREQ | SLASHEQ | PERCENTEQ | PLUSEQ | MINUSEQ | SHLEQ | SHREQ |
+   BITWISEANDEQ | BITWISEXOREQ | BITWISEOREQ | LOGICALANDEQ | LOGICALXOREQ | LOGICALOREQ)
+   assignmentExpression)*
+ */
+std::unique_ptr<ASTExpression> Parser::assignmentExpression() {
+    std::unique_ptr<ASTExpression> result = this->ternaryExpression();
+    if (!result) {
+        return nullptr;
+    }
+    for (;;) {
+        switch (this->peek().fKind) {
+            case Token::EQ:           // fall through
+            case Token::STAREQ:       // fall through
+            case Token::SLASHEQ:      // fall through
+            case Token::PERCENTEQ:    // fall through
+            case Token::PLUSEQ:       // fall through
+            case Token::MINUSEQ:      // fall through
+            case Token::SHLEQ:        // fall through
+            case Token::SHREQ:        // fall through
+            case Token::BITWISEANDEQ: // fall through
+            case Token::BITWISEXOREQ: // fall through
+            case Token::BITWISEOREQ:  // fall through
+            case Token::LOGICALANDEQ: // fall through
+            case Token::LOGICALXOREQ: // fall through
+            case Token::LOGICALOREQ: {
+                Token t = this->nextToken();
+                std::unique_ptr<ASTExpression> right = this->assignmentExpression();
+                if (right == nullptr) {
+                    return nullptr;
+                }
+                result = std::unique_ptr<ASTExpression>(new ASTBinaryExpression(std::move(result), 
+                                                                                t, 
+                                                                                std::move(right)));
+            }
+            default:
+                return result;
+        }
+    }
+}
+
+/* logicalOrExpression ('?' expression ':' assignmentExpression)? */
+std::unique_ptr<ASTExpression> Parser::ternaryExpression() {
+    std::unique_ptr<ASTExpression> result = this->logicalOrExpression();
+    if (result == nullptr) {
+        return nullptr;
+    }
+    if (this->peek().fKind == Token::QUESTION) {
+        Token question = this->nextToken();
+        std::unique_ptr<ASTExpression> trueExpr = this->expression();
+        if (trueExpr == nullptr) {
+            return nullptr;
+        }
+        if (this->expect(Token::COLON, "':'")) {
+            std::unique_ptr<ASTExpression> falseExpr = this->assignmentExpression();
+            return std::unique_ptr<ASTExpression>(new ASTTernaryExpression(std::move(result), 
+                                                                           std::move(trueExpr), 
+                                                                           std::move(falseExpr)));
+        }
+        return nullptr;
+    }
+    return result;
+}
+
+/* logicalXorExpression (LOGICALOR logicalXorExpression)* */
+std::unique_ptr<ASTExpression> Parser::logicalOrExpression() {
+    std::unique_ptr<ASTExpression> result = this->logicalXorExpression();
+    if (result == nullptr) {
+        return nullptr;
+    }
+    while (this->peek().fKind == Token::LOGICALOR) {
+        Token t = this->nextToken();
+        std::unique_ptr<ASTExpression> right = this->logicalXorExpression();
+        if (right == nullptr) {
+            return nullptr;
+        }
+        result.reset(new ASTBinaryExpression(std::move(result), t, std::move(right)));
+    }
+    return result;
+}
+
+/* logicalAndExpression (LOGICALXOR logicalAndExpression)* */
+std::unique_ptr<ASTExpression> Parser::logicalXorExpression() {
+    std::unique_ptr<ASTExpression> result = this->logicalAndExpression();
+    if (result == nullptr) {
+        return nullptr;
+    }
+    while (this->peek().fKind == Token::LOGICALXOR) {
+        Token t = this->nextToken();
+        std::unique_ptr<ASTExpression> right = this->logicalAndExpression();
+        if (right == nullptr) {
+            return nullptr;
+        }
+        result.reset(new ASTBinaryExpression(std::move(result), t, std::move(right)));
+    }
+    return result;
+}
+
+/* bitwiseXorExpression (LOGICALAND bitwiseXorExpression)* */
+std::unique_ptr<ASTExpression> Parser::logicalAndExpression() {
+    std::unique_ptr<ASTExpression> result = this->bitwiseOrExpression();
+    if (result == nullptr) {
+        return nullptr;
+    }
+    while (this->peek().fKind == Token::LOGICALAND) {
+        Token t = this->nextToken();
+        std::unique_ptr<ASTExpression> right = this->bitwiseXorExpression();
+        if (right == nullptr) {
+            return nullptr;
+        }
+        result.reset(new ASTBinaryExpression(std::move(result), t, std::move(right)));
+    }
+    return result;
+}
+
+/* bitwiseXorExpression (BITWISEOR bitwiseXorExpression)* */
+std::unique_ptr<ASTExpression> Parser::bitwiseOrExpression() {
+    std::unique_ptr<ASTExpression> result = this->bitwiseXorExpression();
+    if (result == nullptr) {
+        return nullptr;
+    }
+    while (this->peek().fKind == Token::BITWISEOR) {
+        Token t = this->nextToken();
+        std::unique_ptr<ASTExpression> right = this->bitwiseXorExpression();
+        if (right == nullptr) {
+            return nullptr;
+        }
+        result.reset(new ASTBinaryExpression(std::move(result), t, std::move(right)));
+    }
+    return result;
+}
+
+/* bitwiseAndExpression (BITWISEXOR bitwiseAndExpression)* */
+std::unique_ptr<ASTExpression> Parser::bitwiseXorExpression() {
+    std::unique_ptr<ASTExpression> result = this->bitwiseAndExpression();
+    if (result == nullptr) {
+        return nullptr;
+    }
+    while (this->peek().fKind == Token::BITWISEXOR) {
+        Token t = this->nextToken();
+        std::unique_ptr<ASTExpression> right = this->bitwiseAndExpression();
+        if (right == nullptr) {
+            return nullptr;
+        }
+        result.reset(new ASTBinaryExpression(std::move(result), t, std::move(right)));
+    }
+    return result;
+}
+
+/* equalityExpression (BITWISEAND equalityExpression)* */
+std::unique_ptr<ASTExpression> Parser::bitwiseAndExpression() {
+    std::unique_ptr<ASTExpression> result = this->equalityExpression();
+    if (result == nullptr) {
+        return nullptr;
+    }
+    while (this->peek().fKind == Token::BITWISEAND) {
+        Token t = this->nextToken();
+        std::unique_ptr<ASTExpression> right = this->equalityExpression();
+        if (right == nullptr) {
+            return nullptr;
+        }
+        result.reset(new ASTBinaryExpression(std::move(result), t, std::move(right)));
+    }
+    return result;
+}
+
+/* relationalExpression ((EQEQ | NEQ) relationalExpression)* */
+std::unique_ptr<ASTExpression> Parser::equalityExpression() {
+    std::unique_ptr<ASTExpression> result = this->relationalExpression();
+    if (result == nullptr) {
+        return nullptr;
+    }
+    for (;;) {
+        switch (this->peek().fKind) {
+            case Token::EQEQ:   // fall through
+            case Token::NEQ: {
+                Token t = this->nextToken();
+                std::unique_ptr<ASTExpression> right = this->relationalExpression();
+                if (right == nullptr) {
+                    return nullptr;
+                }
+                result.reset(new ASTBinaryExpression(std::move(result), t, std::move(right)));
+                break;
+            }
+            default:
+                return result;
+        }
+    }
+}
+
+/* shiftExpression ((LT | GT | LTEQ | GTEQ) shiftExpression)* */
+std::unique_ptr<ASTExpression> Parser::relationalExpression() {
+    std::unique_ptr<ASTExpression> result = this->shiftExpression();
+    if (result == nullptr) {
+        return nullptr;
+    }
+    for (;;) {
+        switch (this->peek().fKind) {
+            case Token::LT:   // fall through
+            case Token::GT:   // fall through
+            case Token::LTEQ: // fall through
+            case Token::GTEQ: {
+                Token t = this->nextToken();
+                std::unique_ptr<ASTExpression> right = this->shiftExpression();
+                if (right == nullptr) {
+                    return nullptr;
+                }
+                result.reset(new ASTBinaryExpression(std::move(result), t, std::move(right)));
+                break;
+            }
+            default:
+                return result;
+        }
+    }
+}
+
+/* additiveExpression ((SHL | SHR) additiveExpression)* */
+std::unique_ptr<ASTExpression> Parser::shiftExpression() {
+    std::unique_ptr<ASTExpression> result = this->additiveExpression();
+    if (result == nullptr) {
+        return nullptr;
+    }
+    for (;;) {
+        switch (this->peek().fKind) {
+            case Token::SHL: // fall through
+            case Token::SHR: {
+                Token t = this->nextToken();
+                std::unique_ptr<ASTExpression> right = this->additiveExpression();
+                if (right == nullptr) {
+                    return nullptr;
+                }
+                result.reset(new ASTBinaryExpression(std::move(result), t, std::move(right)));
+                break;
+            }
+            default:
+                return result;
+        }
+    }
+}
+
+/* multiplicativeExpression ((PLUS | MINUS) multiplicativeExpression)* */
+std::unique_ptr<ASTExpression> Parser::additiveExpression() {
+    std::unique_ptr<ASTExpression> result = this->multiplicativeExpression();
+    if (result == nullptr) {
+        return nullptr;
+    }
+    for (;;) {
+        switch (this->peek().fKind) {
+            case Token::PLUS: // fall through
+            case Token::MINUS: {
+                Token t = this->nextToken();
+                std::unique_ptr<ASTExpression> right = this->multiplicativeExpression();
+                if (right == nullptr) {
+                    return nullptr;
+                }
+                result.reset(new ASTBinaryExpression(std::move(result), t, std::move(right)));
+                break;
+            }
+            default:
+                return result;
+        }
+    }
+}
+
+/* unaryExpression ((STAR | SLASH | PERCENT) unaryExpression)* */
+std::unique_ptr<ASTExpression> Parser::multiplicativeExpression() {
+    std::unique_ptr<ASTExpression> result = this->unaryExpression();
+    if (result == nullptr) {
+        return nullptr;
+    }
+    for (;;) {
+        switch (this->peek().fKind) {
+            case Token::STAR: // fall through
+            case Token::SLASH: // fall through
+            case Token::PERCENT: {
+                Token t = this->nextToken();
+                std::unique_ptr<ASTExpression> right = this->unaryExpression();
+                if (right == nullptr) {
+                    return nullptr;
+                }
+                result.reset(new ASTBinaryExpression(std::move(result), t, std::move(right)));
+                break;
+            }
+            default:
+                return result;
+        }
+    }
+}
+
+/* postfixExpression | (PLUS | MINUS | NOT | PLUSPLUS | MINUSMINUS) unaryExpression */
+std::unique_ptr<ASTExpression> Parser::unaryExpression() {
+    switch (this->peek().fKind) {
+        case Token::PLUS:     // fall through
+        case Token::MINUS:    // fall through
+        case Token::NOT:      // fall through
+        case Token::PLUSPLUS: // fall through
+        case Token::MINUSMINUS: {
+            Token t = this->nextToken();
+            std::unique_ptr<ASTExpression> expr = this->unaryExpression();
+            if (expr == nullptr) {
+                return nullptr;
+            }
+            return std::unique_ptr<ASTExpression>(new ASTPrefixExpression(t, std::move(expr)));
+        }
+        default:
+            return this->postfixExpression();
+    }
+}
+
+/* term suffix* */
+std::unique_ptr<ASTExpression> Parser::postfixExpression() {
+    std::unique_ptr<ASTExpression> result = this->term();
+    if (result == nullptr) {
+        return nullptr;
+    }
+    for (;;) {
+        switch (this->peek().fKind) {
+            case Token::LBRACKET: // fall through
+            case Token::DOT:      // fall through
+            case Token::LPAREN:   // fall through
+            case Token::PLUSPLUS: // fall through
+            case Token::MINUSMINUS: {
+                std::unique_ptr<ASTSuffix> s = this->suffix();
+                if (s == nullptr) {
+                    return nullptr;
+                }
+                result.reset(new ASTSuffixExpression(std::move(result), std::move(s)));
+                break;
+            }
+            default:
+                return result;
+        }
+    }
+}
+
+/* LBRACKET expression RBRACKET | DOT IDENTIFIER | LPAREN parameters RPAREN | 
+   PLUSPLUS | MINUSMINUS */
+std::unique_ptr<ASTSuffix> Parser::suffix() {
+    Token next = this->nextToken();
+    switch (next.fKind) {
+        case Token::LBRACKET: {
+            std::unique_ptr<ASTExpression> e = this->expression();
+            if (e == nullptr) {
+                return nullptr;
+            }
+            this->expect(Token::RBRACKET, "']' to complete array access expression");
+            return std::unique_ptr<ASTSuffix>(new ASTIndexSuffix(std::move(e)));
+        }
+        case Token::DOT: {
+            Position pos = this->peek().fPosition;
+            std::string text;
+            if (this->identifier(&text)) {
+                return std::unique_ptr<ASTSuffix>(new ASTFieldSuffix(pos, text));
+            }
+            return nullptr;
+        }
+        case Token::LPAREN: {
+            std::vector<std::unique_ptr<ASTExpression>> parameters;
+            if (this->peek().fKind != Token::RPAREN) {
+                for (;;) {
+                    std::unique_ptr<ASTExpression> expr = this->expression();
+                    if (expr == nullptr) {
+                        return nullptr;
+                    }
+                    parameters.push_back(std::move(expr));
+                    if (this->peek().fKind != Token::COMMA) {
+                        break;
+                    }
+                    this->nextToken();
+                }
+            }
+            this->expect(Token::RPAREN, "')' to complete function parameters");
+            return std::unique_ptr<ASTSuffix>(new ASTCallSuffix(next.fPosition, 
+                                                                std::move(parameters)));
+        }
+        case Token::PLUSPLUS:
+            return std::unique_ptr<ASTSuffix>(new ASTSuffix(next.fPosition, 
+                                                            ASTSuffix::kPostIncrement_Kind));
+        case Token::MINUSMINUS:
+            return std::unique_ptr<ASTSuffix>(new ASTSuffix(next.fPosition,
+                                                            ASTSuffix::kPostDecrement_Kind));
+        default: {
+            this->error(next.fPosition,  "expected expression suffix, but found '" + next.fText + 
+                                         "'\n");
+            return nullptr;
+        }
+    }
+}
+
+/* IDENTIFIER | intLiteral | floatLiteral | boolLiteral | '(' expression ')' */
+std::unique_ptr<ASTExpression> Parser::term() {
+    std::unique_ptr<ASTExpression> result;
+    Token t = this->peek();
+    switch (t.fKind) {
+        case Token::IDENTIFIER: {
+            std::string text;
+            if (this->identifier(&text)) {
+                result.reset(new ASTIdentifier(t.fPosition, text));
+            }
+            break;
+        }
+        case Token::INT_LITERAL: {
+            int64_t i;
+            if (this->intLiteral(&i)) {
+                result.reset(new ASTIntLiteral(t.fPosition, i));
+            }
+            break;
+        }
+        case Token::FLOAT_LITERAL: {
+            double f;
+            if (this->floatLiteral(&f)) {
+                result.reset(new ASTFloatLiteral(t.fPosition, f));
+            }
+            break;
+        }
+        case Token::TRUE_LITERAL: // fall through
+        case Token::FALSE_LITERAL: {
+            bool b;
+            if (this->boolLiteral(&b)) {
+                result.reset(new ASTBoolLiteral(t.fPosition, b));
+            }
+            break;
+        }
+        case Token::LPAREN: {
+            this->nextToken();
+            result = this->expression();
+            if (result) {
+                this->expect(Token::RPAREN, "')' to complete expression");
+            }
+            break;
+        }
+        default:
+            this->nextToken();
+            this->error(t.fPosition,  "expected expression, but found '" + t.fText + "'\n");
+            result = nullptr;
+    }
+    return result;
+}
+
+/* INT_LITERAL */
+bool Parser::intLiteral(int64_t* dest) {
+    Token t;
+    if (this->expect(Token::INT_LITERAL, "integer literal", &t)) {
+        *dest = SkSL::stol(t.fText);
+        return true;
+    }
+    return false;
+}
+
+/* FLOAT_LITERAL */
+bool Parser::floatLiteral(double* dest) {
+    Token t;
+    if (this->expect(Token::FLOAT_LITERAL, "float literal", &t)) {
+        *dest = SkSL::stod(t.fText);
+        return true;
+    }
+    return false;
+}
+
+/* TRUE_LITERAL | FALSE_LITERAL */
+bool Parser::boolLiteral(bool* dest) {
+    Token t = this->nextToken();
+    switch (t.fKind) {
+        case Token::TRUE_LITERAL:
+            *dest = true;
+            return true;
+        case Token::FALSE_LITERAL:
+            *dest = false;
+            return true;
+        default:
+            this->error(t.fPosition, "expected 'true' or 'false', but found '" + t.fText + "'\n");
+            return false;
+    }
+}
+
+/* IDENTIFIER */
+bool Parser::identifier(std::string* dest) {
+    Token t;
+    if (this->expect(Token::IDENTIFIER, "identifier", &t)) {
+        *dest = t.fText; 
+        return true;
+    }
+    return false;
+}
+
+} // namespace