[WHSL] Need grammar to specify kernel group size
[WebKit-https.git] / Tools / WebGPUShadingLanguageRI / Parse.js
1 /*
2  * Copyright (C) 2018 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25 "use strict";
26
27 function parse(program, origin, originKind, lineNumberOffset, text)
28 {
29     let lexer = new Lexer(origin, originKind, lineNumberOffset, text);
30
31     // The hardest part of dealing with C-like languages is parsing variable declaration statements.
32     // Let's consider if this happens in WSL. Here are the valid statements in WSL that being with an
33     // identifier, if we assume that any expression can be a standalone statement.
34     //
35     //     x;
36     //     x <binop> y;
37     //     x < y;
38     //     x < y > z;
39     //     x = y;
40     //     x.f = y;
41     //     \exp = y;
42     //     x[42] = y;
43     //     x();
44     //     x<y>();
45     //     x y;
46     //     x<y> z;
47     //     device x[] y;
48     //     x[42] y;
49     //     device x^ y;
50     //     thread x^^ y;
51     //     x^thread^thread y;
52     //     x^device^thread y;
53     //
54     // This has two problem areas:
55     //
56     //     - x<y>z can parse two different ways (as (x < y) > z or x<y> z).
57     //     - x[42] could become either an assignment or a variable declaration.
58     //     - x<y> could become either an assignment or a variable declaration.
59     //
60     // We solve the first problem by forbidding expressions as statements. The lack of function
61     // pointers means that we can still allow function call statements - unlike in C, those cannot
62     // have arbitrary expressions as the callee. The remaining two problems are solved by
63     // backtracking. In all other respects, this is a simple recursive descent parser.
64
65     function fail(error)
66     {
67         return new WSyntaxError(lexer.originString, error);
68     }
69
70     function backtrackingScope(callback)
71     {
72         let state = lexer.state;
73         let maybeError = callback();
74         if (maybeError instanceof WSyntaxError) {
75             lexer.state = state;
76             return null;
77         } else
78             return maybeError;
79     }
80
81     function testScope(callback)
82     {
83         let state = lexer.state;
84         let maybeError = callback();
85         lexer.state = state;
86         return !(maybeError instanceof WSyntaxError);
87     }
88
89     function genericConsume(callback, explanation)
90     {
91         let token = lexer.next();
92         if (!token)
93             return fail("Unexpected end of file");
94         if (!callback(token))
95             return fail("Unexpected token: " + token.text + "; expected: " + explanation);
96         return token;
97     }
98
99     function consume(...texts)
100     {
101         return genericConsume(token => texts.includes(token.text), texts);
102     }
103
104     function consumeKind(kind)
105     {
106         return genericConsume(token => token.kind == kind, kind);
107     }
108
109     function assertNext(...texts)
110     {
111         let maybeError = consume(...texts);
112         if (maybeError instanceof WSyntaxError)
113             return maybeError;
114         lexer.push(maybeError);
115     }
116
117     function genericTest(callback)
118     {
119         let token = lexer.peek();
120         if (token && callback(token))
121             return token;
122         return null;
123     }
124
125     function test(...texts)
126     {
127         return genericTest(token => texts.includes(token.text));
128     }
129
130     function testKind(kind)
131     {
132         return genericTest(token => token.kind == kind);
133     }
134
135     function tryConsume(...texts)
136     {
137         let result = test(...texts);
138         if (result)
139             lexer.next();
140         return result;
141     }
142
143     function tryConsumeKind(kind)
144     {
145         let result = testKind(kind);
146         if (result)
147             lexer.next();
148         return result;
149     }
150
151     function consumeEndOfTypeArgs()
152     {
153         let rightShift = tryConsume(">>");
154         if (rightShift)
155             lexer.push(new LexerToken(lexer, rightShift, rightShift.index, rightShift.kind, ">"));
156         else {
157             let maybeError = consume(">");
158             if (maybeError instanceof WSyntaxError)
159                 return maybeError;
160         }
161     }
162
163     function parseTerm()
164     {
165         let token;
166         if (token = tryConsume("null"))
167             return new NullLiteral(token);
168         if (token = tryConsumeKind("identifier"))
169             return new VariableRef(token, token.text);
170         if (token = tryConsumeKind("intLiteral")) {
171             let intVersion = (+token.text) | 0;
172             if ("" + intVersion !== token.text)
173                 return fail("Integer literal is not an integer: " + token.text);
174             return new IntLiteral(token, intVersion);
175         }
176         if (token = tryConsumeKind("uintLiteral")) {
177             let uintVersion = token.text.substr(0, token.text.length - 1) >>> 0;
178             if (uintVersion + "u" !== token.text)
179                 return fail("Integer literal is not 32-bit unsigned integer: " + token.text);
180             return new UintLiteral(token, uintVersion);
181         }
182         if ((token = tryConsumeKind("intHexLiteral"))
183             || (token = tryConsumeKind("uintHexLiteral"))) {
184             let hexString = token.text.substr(2);
185             if (token.kind == "uintHexLiteral")
186                 hexString = hexString.substr(0, hexString.length - 1);
187             if (!hexString.length)
188                 throw new Error("Bad hex literal: " + token);
189             let intVersion = parseInt(hexString, 16);
190             if (token.kind == "intHexLiteral")
191                 intVersion = intVersion | 0;
192             else
193                 intVersion = intVersion >>> 0;
194             if (intVersion.toString(16) !== hexString)
195                 return fail("Hex integer literal is not an integer: " + token.text);
196             if (token.kind == "intHexLiteral")
197                 return new IntLiteral(token, intVersion);
198             return new UintLiteral(token, intVersion >>> 0);
199         }
200         if (token = tryConsumeKind("floatLiteral")) {
201             let text = token.text;
202             let f = token.text.endsWith("f");
203             if (f)
204                 text = text.substring(0, text.length - 1);
205             let value = parseFloat(text);
206             return new FloatLiteral(token, Math.fround(value));
207         }
208         if (token = tryConsume("true", "false"))
209             return new BoolLiteral(token, token.text == "true");
210         // FIXME: Need support for other literals too.
211         let maybeError = consume("(");
212         if (maybeError instanceof WSyntaxError)
213             return maybeError;
214         let result = parseExpression();
215         if (result instanceof WSyntaxError)
216             return result;
217         maybeError = consume(")");
218         if (maybeError instanceof WSyntaxError)
219             return maybeError;
220         return result;
221     }
222
223     function parseConstexpr()
224     {
225         let token;
226         if (token = tryConsume("-")) {
227             let term = parseTerm();
228             if (term instanceof WSyntaxError)
229                 return term;
230             return new CallExpression(token, "operator" + token.text, [term]);
231         }
232         let left = parseTerm();
233         if (left instanceof WSyntaxError)
234             return left;
235         if (token = tryConsume(".")) {
236             let maybeError = consumeKind("identifier")
237             if (maybeError instanceof WSyntaxError)
238                 return maybeError;
239             left = new DotExpression(token, left, maybeError.text);
240         }
241         return left;
242     }
243
244     function parseTypeArguments()
245     {
246         if (!test("<"))
247             return [];
248
249         let result = [];
250         let maybeError = consume("<");
251         if (maybeError instanceof WSyntaxError)
252             return maybeError;
253         while (!test(">")) {
254             // It's possible for a constexpr or type can syntactically overlap in the single
255             // identifier case. Let's consider the possibilities:
256             //
257             //     T          could be type or constexpr
258             //     T[]        only type
259             //     T[42]      only type (constexpr cannot do indexing)
260             //     42         only constexpr
261             //
262             // In the future we'll allow constexprs to do more things, and then we'll still have
263             // the problem that something of the form T[1][2][3]... can either be a type or a
264             // constexpr, and we can figure out in the checker which it is.
265             let typeRef = backtrackingScope(() => {
266                 let result = consumeKind("identifier");
267                 if (result instanceof WSyntaxError)
268                     return result;
269                 let maybeError = assertNext(",", ">", ">>");
270                 if (maybeError instanceof WSyntaxError)
271                     return maybeError;
272                 return new TypeRef(result, result.text);
273             });
274             if (typeRef)
275                 result.push(typeRef);
276             else {
277                 let constexpr = backtrackingScope(() => {
278                     let result = parseConstexpr();
279                     if (result instanceof WSyntaxError)
280                         return result;
281                     let maybeError = assertNext(",", ">", ">>");
282                     if (maybeError instanceof WSyntaxError)
283                         return maybeError;
284                     return result;
285                 });
286                 if (constexpr)
287                     result.push(constexpr);
288                 else {
289                     let type = parseType();
290                     if (type instanceof WSyntaxError)
291                         return type;
292                     result.push(type);
293                 }
294             }
295             if (!tryConsume(","))
296                 break;
297         }
298         maybeError = consumeEndOfTypeArgs();
299         if (maybeError instanceof WSyntaxError)
300             return maybeError;
301         return result;
302     }
303
304     function parseType()
305     {
306         let token;
307         let addressSpace;
308         let addressSpaceConsumed = false;
309         if (token = tryConsume(...addressSpaces))
310             addressSpace = token.text;
311
312         let name = consumeKind("identifier");
313         if (name instanceof WSyntaxError)
314             return name;
315         let typeArguments = parseTypeArguments();
316         if (typeArguments instanceof WSyntaxError)
317             return typeArguments;
318         let type = new TypeRef(name, name.text, typeArguments);
319
320         function getAddressSpace()
321         {
322             addressSpaceConsumed = true;
323             if (addressSpace)
324                 return addressSpace;
325             let consumedAddressSpace = consume(...addressSpaces);
326             if (consumedAddressSpace instanceof WSyntaxError)
327                 return consumedAddressSpace;
328             return consumedAddressSpace.text;
329         }
330
331         const typeConstructorStack = [ ];
332
333         for (let token; token = tryConsume("*", "[");) {
334             if (token.text == "*") {
335                 // Likewise, the address space must be parsed before parsing continues.
336                 const addressSpace = getAddressSpace();
337                 if (addressSpace instanceof WSyntaxError)
338                     return addressSpace;
339                 typeConstructorStack.unshift(type => new PtrType(token, addressSpace, type));
340                 continue;
341             }
342
343             if (tryConsume("]")) {
344                 const addressSpace = getAddressSpace();
345                 if (addressSpace instanceof WSyntaxError)
346                     return addressSpace;
347                 typeConstructorStack.unshift(type => new ArrayRefType(token, addressSpace, type));
348                 continue;
349             }
350
351             const lengthExpr = parseConstexpr();
352             if (lengthExpr instanceof WSyntaxError)
353                 return lengthExpr;
354             typeConstructorStack.unshift(type => new ArrayType(token, type, lengthExpr));
355             let maybeError = consume("]");
356             if (maybeError instanceof WSyntaxError)
357                 return maybeError;
358         }
359
360         for (let constructor of typeConstructorStack)
361             type = constructor(type);
362
363         if (addressSpace && !addressSpaceConsumed)
364             return fail("Address space specified for type that does not need address space");
365
366         return type;
367     }
368
369     function parseTypeDef()
370     {
371         let origin = consume("typedef");
372         if (origin instanceof WSyntaxError)
373             return origin;
374         let maybeError = consumeKind("identifier");
375         if (maybeError instanceof WSyntaxError)
376             return maybeError;
377         let name = maybeError.text;
378         maybeError = consume("=");
379         if (maybeError instanceof WSyntaxError)
380             return maybeError;
381         let type = parseType();
382         if (type instanceof WSyntaxError)
383             return type;
384         maybeError = consume(";");
385         if (maybeError instanceof WSyntaxError)
386             return maybeError;
387         return new TypeDef(origin, name, type);
388     }
389
390     function genericParseLeft(texts, nextParser, constructor)
391     {
392         let left = nextParser();
393         if (left instanceof WSyntaxError)
394             return left;
395         let token;
396         while (token = tryConsume(...texts))
397             left = constructor(token, left, nextParser());
398         return left;
399     }
400
401     function parseLeftOperatorCall(texts, nextParser)
402     {
403         return genericParseLeft(
404             texts, nextParser,
405             (token, left, right) =>
406                 new CallExpression(token, "operator" + token.text, [left, right]));
407     }
408
409     function parseCallExpression()
410     {
411         let parseArguments = function(origin, callName) {
412             let argumentList = [];
413             while (!test(")")) {
414                 let argument = parsePossibleAssignment();
415                 if (argument instanceof WSyntaxError)
416                     return argument;
417                 argumentList.push(argument);
418                 if (!tryConsume(","))
419                     break;
420             }
421             let maybeError = consume(")");
422             if (maybeError instanceof WSyntaxError)
423                 return maybeError;
424             return new CallExpression(origin, callName, argumentList);
425         }
426
427         let name = backtrackingScope(() => {
428             let name = consumeKind("identifier");
429             if (name instanceof WSyntaxError)
430                 return name;
431             let maybeError = consume("(");
432             if (maybeError instanceof WSyntaxError)
433                 return maybeError;
434             return name;
435         });
436
437         if (name) {
438             let result = parseArguments(name, name.text);
439             return result;
440         } else {
441             let returnType = parseType();
442             if (returnType instanceof WSyntaxError)
443                 return returnType;
444             let maybeError = consume("(");
445             if (maybeError instanceof WSyntaxError)
446                 return maybeError;
447             let result = parseArguments(returnType.origin, "operator cast");
448             result.setCastData(returnType);
449             return result;
450         }
451     }
452
453     function isCallExpression()
454     {
455         return testScope(() => {
456                 let maybeError = consumeKind("identifier");
457                 if (maybeError instanceof WSyntaxError)
458                     return maybeError;
459                 maybeError = consume("(");
460                 if (maybeError instanceof WSyntaxError)
461                     return maybeError;
462             }) || testScope(() => {
463                 let type = parseType();
464                 if (type instanceof WSyntaxError)
465                     return type;
466                 let maybeError = consume("(");
467                 if (maybeError instanceof WSyntaxError)
468                     return maybeError;
469             });
470     }
471
472     function emitIncrement(token, old, extraArg)
473     {
474         let args = [old];
475         if (extraArg)
476             args.push(extraArg);
477
478         let name = "operator" + token.text;
479         if (/=$/.test(name))
480             name = RegExp.leftContext;
481
482         if (name == "operator")
483             throw new Error("Invalid name: " + name);
484
485         return new CallExpression(token, name, args);
486     }
487
488     function finishParsingPostIncrement(token, left)
489     {
490         let readModifyWrite = new ReadModifyWriteExpression(token, left);
491         readModifyWrite.newValueExp = emitIncrement(token, readModifyWrite.oldValueRef());
492         readModifyWrite.resultExp = readModifyWrite.oldValueRef();
493         return readModifyWrite;
494     }
495
496     function parseSuffixOperator(left, acceptableOperators)
497     {
498         let token;
499         while (token = tryConsume(...acceptableOperators)) {
500             switch (token.text) {
501             case "++":
502             case "--":
503                 return finishParsingPostIncrement(token, left);
504             case ".":
505             case "->":
506                 if (token.text == "->")
507                     left = new DereferenceExpression(token, left);
508                 let maybeError = consumeKind("identifier");
509                 if (maybeError instanceof WSyntaxError)
510                     return maybeError;
511                 left = new DotExpression(token, left, maybeError.text);
512                 break;
513             case "[": {
514                 let index = parseExpression();
515                 if (index instanceof WSyntaxError)
516                     return index;
517                 let maybeError = consume("]");
518                 if (maybeError instanceof WSyntaxError)
519                     return maybeError;
520                 left = new IndexExpression(token, left, index);
521                 break;
522             }
523             default:
524                 throw new Error("Bad token: " + token);
525             }
526         }
527         return left;
528     }
529
530     function parsePossibleSuffix()
531     {
532         let acceptableOperators = ["++", "--", ".", "->", "["];
533         let limitedOperators = [".", "->", "["];
534         let left;
535         if (isCallExpression()) {
536             left = parseCallExpression();
537             if (left instanceof WSyntaxError)
538                 return left;
539             acceptableOperators = limitedOperators;
540         } else {
541             left = parseTerm();
542             if (left instanceof WSyntaxError)
543                 return left;
544         }
545
546         return parseSuffixOperator(left, acceptableOperators);
547     }
548
549     function finishParsingPreIncrement(token, left, extraArg)
550     {
551         let readModifyWrite = new ReadModifyWriteExpression(token, left);
552         readModifyWrite.newValueExp = emitIncrement(token, readModifyWrite.oldValueRef(), extraArg);
553         readModifyWrite.resultExp = readModifyWrite.newValueRef();
554         return readModifyWrite;
555     }
556
557     function parsePreIncrement()
558     {
559         let token = consume("++", "--");
560         if (token instanceof WSyntaxError)
561             return token;
562         let left = parsePossiblePrefix();
563         if (left instanceof WSyntaxError)
564             return left;
565         return finishParsingPreIncrement(token, left);
566     }
567
568     function parsePossiblePrefix()
569     {
570         let token;
571         if (test("++", "--"))
572             return parsePreIncrement();
573         if (token = tryConsume("+", "-", "~")) {
574             let possiblePrefix = parsePossiblePrefix();
575             if (possiblePrefix instanceof WSyntaxError)
576                 return WSyntaxError;
577             return new CallExpression(token, "operator" + token.text, [possiblePrefix]);
578         } if (token = tryConsume("*")) {
579             let possiblePrefix = parsePossiblePrefix();
580             if (possiblePrefix instanceof WSyntaxError)
581                 return WSyntaxError;
582             return new DereferenceExpression(token, possiblePrefix);
583         } if (token = tryConsume("&")) {
584             let possiblePrefix = parsePossiblePrefix();
585             if (possiblePrefix instanceof WSyntaxError)
586                 return WSyntaxError;
587             return new MakePtrExpression(token, possiblePrefix);
588         } if (token = tryConsume("@")) {
589             let possiblePrefix = parsePossiblePrefix();
590             if (possiblePrefix instanceof WSyntaxError)
591                 return WSyntaxError;
592             return new MakeArrayRefExpression(token, possiblePrefix);
593         } if (token = tryConsume("!")) {
594             let remainder = parsePossiblePrefix();
595             if (remainder instanceof WSyntaxError)
596                 return remainder;
597             return new LogicalNot(token, new CallExpression(remainder.origin, "bool", [remainder]));
598         }
599         return parsePossibleSuffix();
600     }
601
602     function parsePossibleProduct()
603     {
604         return parseLeftOperatorCall(["*", "/", "%"], parsePossiblePrefix);
605     }
606
607     function parsePossibleSum()
608     {
609         return parseLeftOperatorCall(["+", "-"], parsePossibleProduct);
610     }
611
612     function parsePossibleShift()
613     {
614         return parseLeftOperatorCall(["<<", ">>"], parsePossibleSum);
615     }
616
617     function parsePossibleRelationalInequality()
618     {
619         return parseLeftOperatorCall(["<", ">", "<=", ">="], parsePossibleShift);
620     }
621
622     function parsePossibleRelationalEquality()
623     {
624         return genericParseLeft(
625             ["==", "!="], parsePossibleRelationalInequality,
626             (token, left, right) => {
627                 let result = new CallExpression(token, "operator==", [left, right]);
628                 if (token.text == "!=")
629                     result = new LogicalNot(token, result);
630                 return result;
631             });
632     }
633
634     function parsePossibleBitwiseAnd()
635     {
636         return parseLeftOperatorCall(["&"], parsePossibleRelationalEquality);
637     }
638
639     function parsePossibleBitwiseXor()
640     {
641         return parseLeftOperatorCall(["^"], parsePossibleBitwiseAnd);
642     }
643
644     function parsePossibleBitwiseOr()
645     {
646         return parseLeftOperatorCall(["|"], parsePossibleBitwiseXor);
647     }
648
649     function parseLeftLogicalExpression(texts, nextParser)
650     {
651         return genericParseLeft(
652             texts, nextParser,
653             (token, left, right) => new LogicalExpression(token, token.text, new CallExpression(left.origin, "bool", [left]), new CallExpression(right.origin, "bool", [right])));
654     }
655
656     function parsePossibleLogicalAnd()
657     {
658         return parseLeftLogicalExpression(["&&"], parsePossibleBitwiseOr);
659     }
660
661     function parsePossibleLogicalOr()
662     {
663         return parseLeftLogicalExpression(["||"], parsePossibleLogicalAnd);
664     }
665
666     function parsePossibleTernaryConditional()
667     {
668         let predicate = parsePossibleLogicalOr();
669         if (predicate instanceof WSyntaxError)
670             return predicate;
671         let operator = tryConsume("?");
672         if (!operator)
673             return predicate;
674         let bodyExpression = parsePossibleAssignment();
675         if (bodyExpression instanceof WSyntaxError)
676             return bodyExpression;
677         let maybeError = consume(":");
678         if (maybeError instanceof WSyntaxError)
679             return maybeError;
680         let elseExpression = parsePossibleAssignment();
681         if (elseExpression instanceof WSyntaxError)
682             return elseExpression;
683         return new TernaryExpression(operator, predicate, bodyExpression, elseExpression);
684     }
685
686     function parsePossibleAssignment(mode)
687     {
688         let lhs = parsePossibleTernaryConditional();
689         if (lhs instanceof WSyntaxError)
690             return lhs;
691         let operator = tryConsume("=", "+=", "-=", "*=", "/=", "%=", "^=", "|=", "&=");
692         if (!operator) {
693             if (mode == "required")
694                 return fail("Expected assignment: " + lexer._text.substring(lexer._index));
695             return lhs;
696         }
697         if (operator.text == "=") {
698             let innerAssignment = parsePossibleAssignment();
699             if (innerAssignment instanceof WSyntaxError)
700                 return innerAssignment;
701             return new Assignment(operator, lhs, innerAssignment);
702         }
703         let innerAssignment = parsePossibleAssignment();
704         if (innerAssignment instanceof WSyntaxError)
705             return innerAssignment;
706         return finishParsingPreIncrement(operator, lhs, innerAssignment);
707     }
708
709     function parseAssignment()
710     {
711         return parsePossibleAssignment("required");
712     }
713
714     function parsePostIncrement()
715     {
716         let term = parseTerm();
717         if (term instanceof WSyntaxError)
718             return term;
719         let left = parseSuffixOperator(term, ".", "->", "[");
720         if (left instanceof WSyntaxError)
721             return left;
722         let token = consume("++", "--");
723         if (token instanceof WSyntaxError)
724             return token;
725         return finishParsingPostIncrement(token, left);
726     }
727
728     function parseEffectfulExpression()
729     {
730         if (isCallExpression())
731             return parseCallExpression();
732         let preIncrement = backtrackingScope(parsePreIncrement);
733         if (preIncrement)
734             return preIncrement;
735         let postIncrement = backtrackingScope(parsePostIncrement);
736         if (postIncrement)
737             return postIncrement;
738         return parseAssignment();
739     }
740
741     function genericParseCommaExpression(finalExpressionParser)
742     {
743         let list = [];
744         let origin = lexer.peek();
745         if (!origin)
746             return fail("Unexpected end of file");
747         for (;;) {
748             let effectfulExpression = backtrackingScope(() => {
749                 let effectfulExpression = parseEffectfulExpression();
750                 if (effectfulExpression instanceof WSyntaxError)
751                     return effectfulExpression;
752                 let maybeError = consume(",");
753                 if (maybeError instanceof WSyntaxError)
754                     return maybeError;
755                 return effectfulExpression;
756             });
757             if (!effectfulExpression) {
758                 let final = finalExpressionParser();
759                 list.push(final);
760                 break;
761             }
762             list.push(effectfulExpression);
763         }
764         if (!list.length)
765             throw new Error("Length should never be zero");
766         if (list.length == 1)
767             return list[0];
768         return new CommaExpression(origin, list);
769     }
770
771     function parseCommaExpression()
772     {
773         return genericParseCommaExpression(parsePossibleAssignment);
774     }
775
776     function parseExpression()
777     {
778         return parseCommaExpression();
779     }
780
781     function parseEffectfulStatement()
782     {
783         let result = genericParseCommaExpression(parseEffectfulExpression);
784         if (result instanceof WSyntaxError)
785             return result;
786         let maybeError = consume(";");
787         if (maybeError instanceof WSyntaxError)
788             return maybeError;
789         return result;
790     }
791
792     function parseReturn()
793     {
794         let origin = consume("return");
795         if (origin instanceof WSyntaxError)
796             return origin;
797         if (tryConsume(";"))
798             return new Return(origin, null);
799         let expression = parseExpression();
800         if (expression instanceof WSyntaxError)
801             return expression;
802         let maybeError = consume(";");
803         if (maybeError instanceof WSyntaxError)
804             return maybeError;
805         return new Return(origin, expression);
806     }
807
808     function parseBreak()
809     {
810         let origin = consume("break");
811         if (origin instanceof WSyntaxError)
812             return origin;
813         let maybeError = consume(";");
814         if (maybeError instanceof WSyntaxError)
815             return maybeError;
816         return new Break(origin);
817     }
818
819     function parseContinue()
820     {
821         let origin = consume("continue");
822         if (origin instanceof WSyntaxError)
823             return origin;
824         let maybeError = consume(";");
825         if (maybeError instanceof WSyntaxError)
826             return maybeError;
827         return new Continue(origin);
828     }
829
830     function parseIfStatement()
831     {
832         let origin = consume("if");
833         if (origin instanceof WSyntaxError)
834             return origin;
835         let maybeError = consume("(");
836         if (maybeError instanceof WSyntaxError)
837             return maybeError;
838         let conditional = parseExpression();
839         if (conditional instanceof WSyntaxError)
840             return conditional;
841         maybeError = consume(")");
842         if (maybeError instanceof WSyntaxError)
843             return maybeError;
844         let body = parseStatement();
845         if (body instanceof WSyntaxError)
846             return body;
847         let elseBody;
848         if (tryConsume("else")) {
849             elseBody = parseStatement();
850             if (elseBody instanceof WSyntaxError)
851                 return elseBody;
852         }
853         return new IfStatement(origin, new CallExpression(conditional.origin, "bool", [conditional]), body, elseBody);
854     }
855
856     function parseWhile()
857     {
858         let origin = consume("while");
859         if (origin instanceof WSyntaxError)
860             return origin;
861         let maybeError = consume("(");
862         if (maybeError instanceof WSyntaxError)
863             return maybeError;
864         let conditional = parseExpression();
865         if (conditional instanceof WSyntaxError)
866             return conditional;
867         maybeError = consume(")");
868         if (maybeError instanceof WSyntaxError)
869             return maybeError;
870         let body = parseStatement();
871         if (body instanceof WSyntaxError)
872             return body;
873         return new WhileLoop(origin, new CallExpression(conditional.origin, "bool", [conditional]), body);
874     }
875
876     function parseFor()
877     {
878         let origin = consume("for");
879         if (origin instanceof WSyntaxError)
880             return origin;
881         let maybeError = consume("(");
882         if (maybeError instanceof WSyntaxError)
883             return maybeError;
884         let initialization;
885         if (tryConsume(";"))
886             initialization = undefined;
887         else {
888             initialization = backtrackingScope(parseVariableDecls);
889             if (!initialization) {
890                 initialization = parseEffectfulStatement();
891                 if (initialization instanceof WSyntaxError)
892                     return initialization;
893             }
894         }
895         let condition = tryConsume(";");
896         if (condition)
897             condition = undefined;
898         else {
899             condition = parseExpression();
900             if (condition instanceof WSyntaxError)
901                 return condition;
902             maybeError = consume(";");
903             if (maybeError instanceof WSyntaxError)
904                 return maybeError;
905             condition = new CallExpression(condition.origin, "bool", [condition]);
906         }
907         let increment;
908         if (tryConsume(")"))
909             increment = undefined;
910         else {
911             increment = parseExpression();
912             if (increment instanceof WSyntaxError)
913                 return increment;
914             maybeError = consume(")");
915             if (maybeError instanceof WSyntaxError)
916                 return maybeError;
917         }
918         let body = parseStatement();
919         if (body instanceof WSyntaxError)
920             return body;
921         return new ForLoop(origin, initialization, condition, increment, body);
922     }
923
924     function parseDo()
925     {
926         let origin = consume("do");
927         if (origin instanceof WSyntaxError)
928             return origin;
929         let body = parseStatement();
930         if (body instanceof WSyntaxError)
931             return body;
932         let maybeError = consume("while");
933         if (maybeError instanceof WSyntaxError)
934             return maybeError;
935         maybeError = consume("(");
936         if (maybeError instanceof WSyntaxError)
937             return maybeError;
938         let conditional = parseExpression();
939         if (conditional instanceof WSyntaxError)
940             return conditional;
941         maybeError = consume(")");
942         if (maybeError instanceof WSyntaxError)
943             return maybeError;
944         return new DoWhileLoop(origin, body, new CallExpression(conditional.origin, "bool", [conditional]));
945     }
946
947     function parseVariableDecls()
948     {
949         let type = parseType();
950         if (type instanceof WSyntaxError)
951             return type;
952         let list = [];
953         do {
954             let name = consumeKind("identifier");
955             if (name instanceof WSyntaxError)
956                 return name;
957             let initializer = tryConsume("=") ? parseExpression() : null;
958             if (initializer instanceof WSyntaxError)
959                 return initializer;
960             list.push(new VariableDecl(name, name.text, type, initializer));
961             let maybeError = consume(",", ";");
962             if (maybeError instanceof WSyntaxError)
963                 return maybeError;
964             if (maybeError.text != ",")
965                 break;
966         } while (true);
967         return new CommaExpression(type.origin, list);
968     }
969
970     function parseSwitchCase()
971     {
972         let token = consume("default", "case");
973         if (token instanceof WSyntaxError)
974             return token;
975         let value;
976         if (token.text == "case") {
977             value = parseConstexpr();
978             if (value instanceof WSyntaxError)
979                 return value;
980         }
981         let maybeError = consume(":");
982         if (maybeError instanceof WSyntaxError)
983             return maybeError;
984         let body = parseBlockBody("}", "default", "case");
985         if (body instanceof WSyntaxError)
986             return body;
987         return new SwitchCase(token, value, body);
988     }
989
990     function parseSwitchStatement()
991     {
992         let origin = consume("switch");
993         if (origin instanceof WSyntaxError)
994             return origin;
995         let maybeError = consume("(");
996         if (maybeError instanceof WSyntaxError)
997             return maybeError;
998         let value = parseExpression();
999         if (value instanceof WSyntaxError)
1000             return value;
1001         maybeError = consume(")");
1002         if (maybeError instanceof WSyntaxError)
1003             return maybeError;
1004         maybeError = consume("{");
1005         if (maybeError instanceof WSyntaxError)
1006             return maybeError;
1007         let result = new SwitchStatement(origin, value);
1008         while (!tryConsume("}")) {
1009             let switchCase = parseSwitchCase();
1010             if (switchCase instanceof WSyntaxError)
1011                 return switchCase;
1012             result.add(switchCase);
1013         }
1014         return result;
1015     }
1016
1017     function parseStatement()
1018     {
1019         let token = lexer.peek();
1020         if (token.text == ";") {
1021             lexer.next();
1022             return null;
1023         }
1024         if (token.text == "return")
1025             return parseReturn();
1026         if (token.text == "break")
1027             return parseBreak();
1028         if (token.text == "continue")
1029             return parseContinue();
1030         if (token.text == "while")
1031             return parseWhile();
1032         if (token.text == "do")
1033             return parseDo();
1034         if (token.text == "for")
1035             return parseFor();
1036         if (token.text == "if")
1037             return parseIfStatement();
1038         if (token.text == "switch")
1039             return parseSwitchStatement();
1040         if (token.text == "trap") {
1041             let origin = consume("trap");
1042             if (origin instanceof WSyntaxError)
1043                 return origin;
1044             consume(";");
1045             return new TrapStatement(origin);
1046         }
1047         if (token.text == "{")
1048             return parseBlock();
1049         let variableDecl = backtrackingScope(parseVariableDecls);
1050         if (variableDecl)
1051             return variableDecl;
1052         return parseEffectfulStatement();
1053     }
1054
1055     function parseBlockBody(...terminators)
1056     {
1057         let block = new Block(origin);
1058         while (!test(...terminators)) {
1059             let statement = parseStatement();
1060             if (statement instanceof WSyntaxError)
1061                 return statement;
1062             if (statement)
1063                 block.add(statement);
1064         }
1065         return block;
1066     }
1067
1068     function parseBlock()
1069     {
1070         let origin = consume("{");
1071         if (origin instanceof WSyntaxError)
1072             return origin;
1073         let block = parseBlockBody("}");
1074         if (block instanceof WSyntaxError)
1075             return block;
1076         let maybeError = consume("}");
1077         if (maybeError instanceof WSyntaxError)
1078             return maybeError;
1079         return block;
1080     }
1081
1082     function parseParameter()
1083     {
1084         let type = parseType();
1085         if (type instanceof WSyntaxError)
1086             return type;
1087         let name = tryConsumeKind("identifier");
1088         return new FuncParameter(type.origin, name ? name.text : null, type);
1089     }
1090
1091     function parseParameters()
1092     {
1093         let maybeError = consume("(");
1094         if (maybeError instanceof WSyntaxError)
1095             return maybeError;
1096         let parameters = [];
1097         while (!test(")")) {
1098             let parameter = parseParameter();
1099             if (parameter instanceof WSyntaxError)
1100                 return parameter;
1101             parameters.push(parameter);
1102             if (!tryConsume(","))
1103                 break;
1104         }
1105         maybeError = consume(")");
1106         if (maybeError instanceof WSyntaxError)
1107             return maybeError;
1108         return parameters;
1109     }
1110
1111     function parseFuncName()
1112     {
1113         if (tryConsume("operator")) {
1114             let token = consume("+", "-", "*", "/", "%", "^", "&", "|", "<", ">", "<=", ">=", "==", "++", "--", ".", "~", "<<", ">>", "[");
1115             if (token instanceof WSyntaxError)
1116                 return token;
1117             if (token.text == "&") {
1118                 if (tryConsume("[")) {
1119                     let maybeError = consume("]");
1120                     if (maybeError instanceof WSyntaxError)
1121                         return maybeError;
1122                     return "operator&[]";
1123                 }
1124                 if (tryConsume(".")) {
1125                     let maybeError = consumeKind("identifier");
1126                     if (maybeError instanceof WSyntaxError)
1127                         return maybeError;
1128                     return "operator&." + maybeError.text;
1129                 }
1130                 return "operator&";
1131             }
1132             if (token.text == ".") {
1133                 let maybeError = consumeKind("identifier");
1134                 if (maybeError instanceof WSyntaxError)
1135                     return maybeError;
1136                 let result = "operator." + maybeError.text;
1137                 if (tryConsume("="))
1138                     result += "=";
1139                 return result;
1140             }
1141             if (token.text == "[") {
1142                 let maybeError = consume("]");
1143                 if (maybeError instanceof WSyntaxError)
1144                     return maybeError;
1145                 let result = "operator[]";
1146                 if (tryConsume("="))
1147                     result += "=";
1148                 return result;
1149             }
1150             return "operator" + token.text;
1151         }
1152         let maybeError = consumeKind("identifier");
1153         if (maybeError instanceof WSyntaxError)
1154             return maybeError;
1155         return maybeError.text;
1156     }
1157
1158     function parseAttributeBlock()
1159     {
1160         let maybeError = consume("[");
1161         if (maybeError instanceof WSyntaxError)
1162             return maybeError;
1163         maybeError = consume("numthreads");
1164         if (maybeError instanceof WSyntaxError)
1165             return maybeError;
1166         maybeError = consume("(");
1167         if (maybeError instanceof WSyntaxError)
1168             return maybeError;
1169         let xDimension = consumeKind("intLiteral");
1170         if (xDimension instanceof WSyntaxError)
1171             return xDimension;
1172         let xDimensionUintVersion = xDimension.text >>> 0;
1173         if (xDimensionUintVersion.toString() !== xDimension.text)
1174             return fail("Numthreads X attribute is not 32-bit unsigned integer: " + xDimension.text);
1175         maybeError = consume(",");
1176         if (maybeError instanceof WSyntaxError)
1177             return maybeError;
1178         let yDimension = consumeKind("intLiteral");
1179         if (yDimension instanceof WSyntaxError)
1180             return yDimension;
1181         let yDimensionUintVersion = yDimension.text >>> 0;
1182         if (yDimensionUintVersion.toString() !== yDimension.text)
1183             return fail("Numthreads Y attribute is not 32-bit unsigned integer: " + yDimension.text);
1184         maybeError = consume(",");
1185         if (maybeError instanceof WSyntaxError)
1186             return maybeError;
1187         let zDimension = consumeKind("intLiteral");
1188         if (zDimension instanceof WSyntaxError)
1189             return zDimension;
1190         let zDimensionUintVersion = zDimension.text >>> 0;
1191         if (zDimensionUintVersion.toString() !== zDimension.text)
1192             return fail("Numthreads Z attribute is not 32-bit unsigned integer: " + zDimension.text);
1193         maybeError = consume(")");
1194         if (maybeError instanceof WSyntaxError)
1195             return maybeError;
1196         maybeError = consume("]");
1197         if (maybeError instanceof WSyntaxError)
1198             return maybeError;
1199         return [new FuncNumThreadsAttribute(xDimensionUintVersion, yDimensionUintVersion, zDimensionUintVersion)];
1200     }
1201
1202     function parseFuncDecl()
1203     {
1204         let origin;
1205         let returnType;
1206         let name;
1207         let isCast;
1208         let shaderType;
1209         let attributeBlock = null;
1210         let operatorToken = tryConsume("operator");
1211         if (operatorToken) {
1212             origin = operatorToken;
1213             returnType = parseType();
1214             if (returnType instanceof WSyntaxError)
1215                 return returnType;
1216             name = "operator cast";
1217             isCast = true;
1218         } else {
1219             if (test("[")) {
1220                 attributeBlock = parseAttributeBlock();
1221                 if (attributeBlock instanceof WSyntaxError)
1222                     return attributeBlock;
1223                 shaderType = consume("compute");
1224                 if (shaderType instanceof WSyntaxError)
1225                     return shaderType;
1226             } else
1227                 shaderType = tryConsume("vertex", "fragment", "test");
1228             returnType = parseType();
1229             if (returnType instanceof WSyntaxError)
1230                 return returnType;
1231             if (shaderType) {
1232                 origin = shaderType;
1233                 shaderType = shaderType.text;
1234             } else
1235                 origin = returnType.origin;
1236             name = parseFuncName();
1237             if (name instanceof WSyntaxError)
1238                 return name;
1239             isCast = false;
1240         }
1241         let parameters = parseParameters();
1242         if (parameters instanceof WSyntaxError)
1243             return parameters;
1244         return new Func(origin, name, returnType, parameters, isCast, shaderType, attributeBlock);
1245     }
1246
1247     function parseFuncDef()
1248     {
1249         let func = parseFuncDecl();
1250         if (func instanceof WSyntaxError)
1251             return func;
1252         let body = parseBlock();
1253         if (body instanceof WSyntaxError)
1254             return body;
1255         return new FuncDef(func.origin, func.name, func.returnType, func.parameters, body, func.isCast, func.shaderType, func.attributeBlock);
1256     }
1257
1258     function parseField()
1259     {
1260         let type = parseType();
1261         if (type instanceof WSyntaxError)
1262             return type;
1263         let name = consumeKind("identifier");
1264         if (name instanceof WSyntaxError)
1265             return name;
1266         let maybeError = consume(";");
1267         if (maybeError instanceof WSyntaxError)
1268             return maybeError;
1269         return new Field(name, name.text, type);
1270     }
1271
1272     function parseStructType()
1273     {
1274         let origin = consume("struct");
1275         if (origin instanceof WSyntaxError)
1276             return origin;
1277         let name = consumeKind("identifier");
1278         if (name instanceof WSyntaxError)
1279             return name;
1280         let result = new StructType(origin, name.text);
1281         let maybeError = consume("{");
1282         if (maybeError instanceof WSyntaxError)
1283             return maybeError;
1284         while (!tryConsume("}")) {
1285             let field = parseField();
1286             if (field instanceof WSyntaxError)
1287                 return field;
1288             result.add(field);
1289         }
1290         return result;
1291     }
1292
1293     function parseNativeFunc()
1294     {
1295         let func = parseFuncDecl();
1296         if (func instanceof WSyntaxError)
1297             return func;
1298         if (func.attributeBlock)
1299             return fail("Native function must not have attribute block");
1300         let maybeError = consume(";");
1301         if (maybeError instanceof WSyntaxError)
1302             return maybeError;
1303         return new NativeFunc(func.origin, func.name, func.returnType, func.parameters, func.isCast, func.shaderType);
1304     }
1305
1306     function parseNative()
1307     {
1308         let origin = consume("native");
1309         if (origin instanceof WSyntaxError)
1310             return origin;
1311         if (tryConsume("typedef")) {
1312             let name = consumeKind("identifier");
1313             if (name instanceof WSyntaxError)
1314                 return name;
1315             let args = parseTypeArguments();
1316             if (args instanceof WSyntaxError)
1317                 return args;
1318             let maybeError = consume(";");
1319             if (maybeError instanceof WSyntaxError)
1320                 return maybeError;
1321             return NativeType.create(origin, name.text, args);
1322         }
1323         return parseNativeFunc();
1324     }
1325
1326     function parseRestrictedFuncDef()
1327     {
1328         let maybeError = consume("restricted");
1329         if (maybeError instanceof WSyntaxError)
1330             return maybeError;
1331         let result;
1332         if (tryConsume("native")) {
1333             result = parseNativeFunc();
1334             if (result instanceof WSyntaxError)
1335                 return result;
1336         } else {
1337             result = parseFuncDef();
1338             if (result instanceof WSyntaxError)
1339                 return result;
1340         }
1341         result.isRestricted = true;
1342         return result;
1343     }
1344
1345     function parseEnumMember()
1346     {
1347         let name = consumeKind("identifier");
1348         if (name instanceof WSyntaxError)
1349             return name;
1350         let value = null;
1351         if (tryConsume("=")) {
1352             value = parseConstexpr();
1353             if (value instanceof WSyntaxError)
1354                 return value;
1355         }
1356         return new EnumMember(name, name.text, value);
1357     }
1358
1359     function parseEnumType()
1360     {
1361         let maybeError = consume("enum");
1362         if (maybeError instanceof WSyntaxError)
1363             return maybeError;
1364         let name = consumeKind("identifier");
1365         if (name instanceof WSyntaxError)
1366             return name;
1367         let baseType;
1368         if (tryConsume(":")) {
1369             baseType = parseType();
1370             if (baseType instanceof WSyntaxError)
1371                 return baseType;
1372         } else
1373             baseType = new TypeRef(name, "int");
1374         maybeError = consume("{");
1375         if (maybeError instanceof WSyntaxError)
1376             return maybeError;
1377         let result = new EnumType(name, name.text, baseType);
1378         while (!test("}")) {
1379             let enumMember = parseEnumMember();
1380             if (enumMember instanceof WSyntaxError)
1381                 return enumMember;
1382             result.add(enumMember);
1383             if (!tryConsume(","))
1384                 break;
1385         }
1386         maybeError = consume("}");
1387         if (maybeError instanceof WSyntaxError)
1388             return maybeError;
1389         return result;
1390     }
1391
1392     for (;;) {
1393         let token = lexer.peek();
1394         if (!token)
1395             return;
1396         if (token.text == ";")
1397             lexer.next();
1398         else if (token.text == "typedef") {
1399             let typeDef = parseTypeDef();
1400             if (typeDef instanceof WSyntaxError)
1401                 throw typeDef;
1402             program.add(typeDef);
1403         } else if (originKind == "native" && token.text == "native") {
1404             let native = parseNative();
1405             if (native instanceof WSyntaxError)
1406                 throw native;
1407             program.add(native);
1408         } else if (originKind == "native" && token.text == "restricted") {
1409             let restrictedFuncDef = parseRestrictedFuncDef();
1410             if (restrictedFuncDef instanceof WSyntaxError)
1411                 throw restrictedFuncDef;
1412             program.add(restrictedFuncDef);
1413         } else if (token.text == "struct") {
1414             let struct = parseStructType();
1415             if (struct instanceof WSyntaxError)
1416                 throw struct;
1417             program.add(struct);
1418         } else if (token.text == "enum") {
1419             let enumType = parseEnumType();
1420             if (enumType instanceof WSyntaxError)
1421                 throw enumType;
1422             program.add(enumType);
1423         } else {
1424             let funcDef = parseFuncDef();
1425             if (funcDef instanceof WSyntaxError)
1426                 throw funcDef;
1427             program.add(funcDef);
1428         }
1429     }
1430 }
1431