]> git.tdb.fi Git - libs/gl.git/blob - source/programparser.cpp
Recognize various nonlinear flow control statement
[libs/gl.git] / source / programparser.cpp
1 #include <msp/strings/format.h>
2 #include <msp/strings/regex.h>
3 #include "programparser.h"
4
5 using namespace std;
6
7 namespace Msp {
8 namespace GL {
9
10 using namespace ProgramSyntax;
11
12 ProgramParser::Operator ProgramParser::operators[] =
13 {
14         { "[", 2, BINARY, LEFT_TO_RIGHT },
15         { "(", 2, BINARY, LEFT_TO_RIGHT },
16         { ".", 2, BINARY, LEFT_TO_RIGHT },
17         { "++", 2, POSTFIX, LEFT_TO_RIGHT },
18         { "--", 2, POSTFIX, LEFT_TO_RIGHT },
19         { "++", 3, PREFIX, RIGHT_TO_LEFT },
20         { "--", 3, PREFIX, RIGHT_TO_LEFT },
21         { "+", 3, PREFIX, RIGHT_TO_LEFT },
22         { "-", 3, PREFIX, RIGHT_TO_LEFT },
23         { "~", 3, PREFIX, RIGHT_TO_LEFT },
24         { "!", 3, PREFIX, RIGHT_TO_LEFT },
25         { "*", 4, BINARY, LEFT_TO_RIGHT },
26         { "/", 4, BINARY, LEFT_TO_RIGHT },
27         { "%", 4, BINARY, LEFT_TO_RIGHT },
28         { "+", 5, BINARY, LEFT_TO_RIGHT },
29         { "-", 5, BINARY, LEFT_TO_RIGHT },
30         { "<<", 6, BINARY, LEFT_TO_RIGHT },
31         { ">>", 6, BINARY, LEFT_TO_RIGHT },
32         { "<", 7, BINARY, LEFT_TO_RIGHT },
33         { ">", 7, BINARY, LEFT_TO_RIGHT },
34         { "<=", 7, BINARY, LEFT_TO_RIGHT },
35         { ">=", 7, BINARY, LEFT_TO_RIGHT },
36         { "==", 8, BINARY, LEFT_TO_RIGHT },
37         { "!=", 8, BINARY, LEFT_TO_RIGHT },
38         { "&", 9, BINARY, LEFT_TO_RIGHT },
39         { "^", 10, BINARY, LEFT_TO_RIGHT },
40         { "|", 11, BINARY, LEFT_TO_RIGHT },
41         { "&&", 12, BINARY, LEFT_TO_RIGHT },
42         { "^^", 13, BINARY, LEFT_TO_RIGHT },
43         { "||", 14, BINARY, LEFT_TO_RIGHT },
44         { "?", 15, BINARY, RIGHT_TO_LEFT },
45         { ":", 15, BINARY, RIGHT_TO_LEFT },
46         { "=", 16, BINARY, RIGHT_TO_LEFT },
47         { "+=", 16, BINARY, RIGHT_TO_LEFT },
48         { "-=", 16, BINARY, RIGHT_TO_LEFT },
49         { "*=", 16, BINARY, RIGHT_TO_LEFT },
50         { "/=", 16, BINARY, RIGHT_TO_LEFT },
51         { "%=", 16, BINARY, RIGHT_TO_LEFT },
52         { "<<=", 16, BINARY, RIGHT_TO_LEFT },
53         { ">>=", 16, BINARY, RIGHT_TO_LEFT },
54         { "&=", 16, BINARY, RIGHT_TO_LEFT },
55         { "^=", 16, BINARY, RIGHT_TO_LEFT },
56         { "|=", 16, BINARY, RIGHT_TO_LEFT },
57         { ",", 17, BINARY, LEFT_TO_RIGHT },
58         { { 0 }, 18, NO_OPERATOR, LEFT_TO_RIGHT }
59 };
60
61 ProgramParser::ProgramParser():
62         module(0)
63 { }
64
65 ProgramParser::~ProgramParser()
66 {
67         delete module;
68 }
69
70 Module &ProgramParser::parse(const string &s)
71 {
72         source = s;
73         parse_source();
74         return *module;
75 }
76
77 Module &ProgramParser::parse(IO::Base &io)
78 {
79         source = string();
80         while(!io.eof())
81         {
82                 char buffer[4096];
83                 unsigned len = io.read(buffer, sizeof(buffer));
84                 source.append(buffer, len);
85         }
86         parse_source();
87         return *module;
88 }
89
90 void ProgramParser::parse_source()
91 {
92         delete module;
93         module = new Module;
94         cur_stage = &module->shared;
95         iter = source.begin();
96         while(1)
97         {
98                 while(RefPtr<Node> statement = parse_global_declaration())
99                         cur_stage->content.body.push_back(statement);
100
101                 parse_token();
102                 string token = parse_token();
103                 if(token.empty())
104                         break;
105                 else if(token=="vertex")
106                         module->stages.push_back(VERTEX);
107                 else if(token=="geometry")
108                         module->stages.push_back(GEOMETRY);
109                 else if(token=="fragment")
110                         module->stages.push_back(FRAGMENT);
111                 else
112                         throw runtime_error(format("Parse error at '%s': expected stage identifier", token));
113
114                 if(cur_stage->type!=SHARED)
115                         module->stages.back().previous = cur_stage;
116                 cur_stage = &module->stages.back();
117
118                 for(; (iter!=source.end() && *iter!='\n'); ++iter) ;
119         }
120 }
121
122 const string &ProgramParser::peek_token(unsigned index)
123 {
124         while(next_tokens.size()<=index)
125                 next_tokens.push_back(parse_token_());
126         return next_tokens[index];
127 }
128
129 string ProgramParser::parse_token()
130 {
131         if(!next_tokens.empty())
132         {
133                 string token = next_tokens.front();
134                 next_tokens.pop_front();
135                 return token;
136         }
137
138         return parse_token_();
139 }
140
141 string ProgramParser::parse_token_()
142 {
143         if(!skip_comment_and_whitespace())
144                 return string();
145
146         if(isalpha(*iter) || *iter=='_')
147                 return parse_identifier();
148         else if(isdigit(*iter))
149                 return parse_number();
150         else
151                 return parse_other();
152 }
153
154 string ProgramParser::parse_identifier()
155 {
156         string ident;
157         while(iter!=source.end())
158         {
159                 if(isalnum(*iter) || *iter=='_')
160                         ident += *iter++;
161                 else
162                         break;
163         }
164
165         return ident;
166 }
167
168 string ProgramParser::parse_number()
169 {
170         bool accept_sign = false;
171         string number;
172         while(iter!=source.end())
173         {
174                 if(isdigit(*iter) || *iter=='.')
175                         number += *iter++;
176                 else if(*iter=='e' || *iter=='E')
177                 {
178                         number += *iter++;
179                         accept_sign = true;
180                 }
181                 else if(accept_sign && (*iter=='+' || *iter=='-'))
182                         number += *iter++;
183                 else
184                         break;
185         }
186
187         return number;
188 }
189
190 string ProgramParser::parse_other()
191 {
192         if(iter==source.end())
193                 return string();
194
195         string token(1, *iter++);
196         for(unsigned i=1; (i<3 && iter!=source.end()); ++i)
197         {
198                 bool matched = false;
199                 for(const Operator *j=operators; (!matched && j->type); ++j)
200                 {
201                         matched = (j->token[i]==*iter);
202                         for(unsigned k=0; (matched && k<i && j->token[k]); ++k)
203                                 matched = (j->token[k]==token[k]);
204                 }
205
206                 if(!matched)
207                         break;
208
209                 token += *iter++;
210         }
211
212         return token;
213 }
214
215 bool ProgramParser::skip_comment_and_whitespace()
216 {
217         unsigned comment = 0;
218         unsigned slashes = 0;
219         while(iter!=source.end())
220         {
221                 if(comment==0)
222                 {
223                         if(*iter=='/')
224                                 comment = 1;
225                         else if(!isspace(*iter))
226                                 break;
227                 }
228                 else if(comment==1)
229                 {
230                         if(*iter=='/')
231                         {
232                                 comment = 2;
233                                 slashes = 2;
234                         }
235                         else if(*iter=='*')
236                                 comment = 3;
237                         else
238                         {
239                                 comment = 0;
240                                 --iter;
241                                 break;
242                         }
243                 }
244                 else if(comment==2)
245                 {
246                         if(*iter=='\n')
247                                 comment = 0;
248                         else if(*iter=='/')
249                                 ++slashes;
250                         else if(!isspace(*iter) && slashes>=6)
251                                 return false;
252                 }
253                 else if(comment==3 && *iter=='*')
254                         comment = 4;
255                 else if(comment==4)
256                 {
257                         if(*iter=='/')
258                                 comment = 0;
259                         else
260                                 comment = 3;
261                 }
262
263                 ++iter;
264         }
265
266         return iter!=source.end();
267 }
268
269 void ProgramParser::expect(const string &token)
270 {
271         string parsed = parse_token();
272         if(parsed!=token)
273                 throw runtime_error(format("Parse error at '%s': expected '%s'", parsed, token));
274 }
275
276 string ProgramParser::expect_type()
277 {
278         string token = parse_token();
279         if(!is_type(token))
280                 throw runtime_error(format("Parse error at '%s': expected a type", token));
281         return token;
282 }
283
284 string ProgramParser::expect_identifier()
285 {
286         string token = parse_token();
287         if(!is_identifier(token))
288                 throw runtime_error(format("Parse error at '%s': expected an identifier", token));
289         return token;
290 }
291
292 bool ProgramParser::check(const string &token)
293 {
294         bool result = (peek_token()==token);
295         if(result)
296                 parse_token();
297         return result;
298 }
299
300 bool ProgramParser::is_interface_qualifier(const string &token)
301 {
302         return (token=="uniform" || token=="in" || token=="out");
303 }
304
305 bool ProgramParser::is_sampling_qualifier(const string &token)
306 {
307         return token=="centroid";
308 }
309
310 bool ProgramParser::is_qualifier(const string &token)
311 {
312         return (token=="const" || is_interface_qualifier(token) || is_sampling_qualifier(token));
313 }
314
315 bool ProgramParser::is_builtin_type(const string &token)
316 {
317         static Regex re("^(void|float|int|bool|[ib]?vec[234]|mat[234](x[234])?|sampler((1D|2D)(Array)?(Shadow)?|Cube(Shadow)?|3D))$");
318         return re.match(token);
319 }
320
321 bool ProgramParser::is_type(const string &token)
322 {
323         return is_builtin_type(token) || declared_types.count(token);
324 }
325
326 bool ProgramParser::is_identifier(const string &token)
327 {
328         static Regex re("^[a-zA-Z_][a-zA-Z0-9_]*$");
329         return re.match(token);
330 }
331
332 RefPtr<Node> ProgramParser::parse_global_declaration()
333 {
334         string token = peek_token();
335         if(token=="import")
336                 return parse_import();
337         else if(token=="layout")
338         {
339                 RefPtr<Layout> layout = parse_layout();
340                 token = peek_token();
341                 if(is_interface_qualifier(token) && peek_token(1)==";")
342                 {
343                         RefPtr<InterfaceLayout> iface_lo = new InterfaceLayout;
344                         iface_lo->layout.qualifiers = layout->qualifiers;
345                         iface_lo->interface = parse_token();
346                         expect(";");
347                         return iface_lo;
348                 }
349                 else
350                 {
351                         RefPtr<VariableDeclaration> var = parse_variable_declaration();
352                         var->layout = layout;
353                         return var;
354                 }
355         }
356         else if(token=="struct")
357                 return parse_struct_declaration();
358         else if(is_sampling_qualifier(token) || token=="const")
359                 return parse_variable_declaration();
360         else if(is_interface_qualifier(token))
361         {
362                 if(is_type(peek_token(1)))
363                         return parse_variable_declaration();
364                 else
365                         return parse_interface_block();
366         }
367         else if(is_type(token))
368         {
369                 if(peek_token(2)=="(")
370                         return parse_function_declaration();
371                 else
372                         return parse_variable_declaration();
373         }
374         else if(token.empty())
375                 return 0;
376         else
377                 throw runtime_error(format("Syntax error at '%s': expected a global declaration", token));
378 }
379
380 RefPtr<Node> ProgramParser::parse_statement()
381 {
382         string token = peek_token();
383         if(token=="if")
384                 return parse_conditional();
385         else if(token=="for")
386                 return parse_iteration();
387         else if(token=="passthrough")
388                 return parse_passthrough();
389         else if(token=="return")
390                 return parse_return();
391         else if(token=="break" || token=="continue" || token=="discard")
392         {
393                 RefPtr<Jump> jump = new Jump;
394                 jump->keyword = parse_token();
395                 expect(";");
396
397                 return jump;
398         }
399         else if(is_qualifier(token) || is_type(token))
400                 return parse_variable_declaration();
401         else if(!token.empty())
402         {
403                 RefPtr<ExpressionStatement> expr = new ExpressionStatement;
404                 expr->expression = parse_expression();
405                 expect(";");
406
407                 return expr;
408         }
409         else
410                 throw runtime_error(format("Syntax error at '%s': expected a statement", token));
411 }
412
413 RefPtr<Import> ProgramParser::parse_import()
414 {
415         if(cur_stage->type!=SHARED)
416                 throw runtime_error("Imports are only allowed in the shared section");
417
418         expect("import");
419         RefPtr<Import> import = new Import;
420         import->module = parse_token();
421         expect(";");
422         return import;
423 }
424
425 RefPtr<Layout> ProgramParser::parse_layout()
426 {
427         expect("layout");
428         expect("(");
429         RefPtr<Layout> layout = new Layout;
430         while(1)
431         {
432                 string token = parse_token();
433                 if(token==")")
434                         throw runtime_error(format("Parse error at '%s': expected layout qualifier id", token));
435
436                 layout->qualifiers.push_back(Layout::Qualifier());
437                 Layout::Qualifier &qual = layout->qualifiers.back();
438                 qual.identifier = token;
439
440                 if(check("="))
441                         qual.value = parse_token();
442
443                 if(peek_token()==")")
444                         break;
445
446                 expect(",");
447         }
448         expect(")");
449
450         return layout;
451 }
452
453 void ProgramParser::parse_block(Block &block, bool require_braces)
454 {
455         bool have_braces = (require_braces || peek_token()=="{");
456         if(have_braces)
457                 expect("{");
458
459         if(have_braces)
460         {
461                 while(peek_token()!="}")
462                         block.body.push_back(parse_statement());
463         }
464         else
465                 block.body.push_back(parse_statement());
466
467         block.use_braces = (require_braces || block.body.size()!=1);
468
469         if(have_braces)
470                 expect("}");
471 }
472
473 RefPtr<Expression> ProgramParser::parse_expression(unsigned precedence)
474 {
475         RefPtr<Expression> left;
476         VariableReference *left_var = 0;
477         while(1)
478         {
479                 string token = peek_token();
480
481                 const Operator *oper = 0;
482                 for(Operator *i=operators; (!oper && i->type); ++i)
483                         if(token==i->token && (!left || i->type!=PREFIX) && (left || i->type!=POSTFIX))
484                                 oper = i;
485
486                 if(token==";" || token==")" || token=="]" || token=="," || (oper && precedence && oper->precedence>=precedence))
487                 {
488                         if(left)
489                                 return left;
490                         else
491                                 throw runtime_error(format("Parse error at '%s': expected an expression", token));
492                 }
493                 else if(left)
494                 {
495                         if(token=="(")
496                         {
497                                 if(!left_var)
498                                         throw runtime_error(format("Parse error at '%s': function name must be an identifier", token));
499                                 left = parse_function_call(*left_var);
500                         }
501                         else if(token==".")
502                         {
503                                 RefPtr<MemberAccess> memacc = new MemberAccess;
504                                 memacc->left = left;
505                                 parse_token();
506                                 memacc->member = expect_identifier();
507                                 left = memacc;
508                         }
509                         else if(oper && oper->type==POSTFIX)
510                         {
511                                 RefPtr<UnaryExpression> unary = new UnaryExpression;
512                                 unary->oper = parse_token();
513                                 unary->prefix = false;
514                                 unary->expression = left;
515                                 left = unary;
516                         }
517                         else if(oper && oper->type==BINARY)
518                                 left = parse_binary(left, oper);
519                         else
520                                 throw runtime_error(format("Parse error at '%s': expected an operator", token));
521                         left_var = 0;
522                 }
523                 else
524                 {
525                         if(token=="(")
526                         {
527                                 parse_token();
528                                 RefPtr<ParenthesizedExpression> parexpr = new ParenthesizedExpression;
529                                 parexpr->expression = parse_expression();
530                                 expect(")");
531                                 left = parexpr;
532                         }
533                         else if(isdigit(token[0]) || token=="true" || token=="false")
534                         {
535                                 RefPtr<Literal> literal = new Literal;
536                                 literal->token = parse_token();
537                                 left = literal;
538                         }
539                         else if(is_identifier(token))
540                         {
541                                 RefPtr<VariableReference> var = new VariableReference;
542                                 var->name = expect_identifier();
543                                 left = var;
544                                 left_var = var.get();
545                         }
546                         else if(oper && oper->type==PREFIX)
547                         {
548                                 RefPtr<UnaryExpression> unary = new UnaryExpression;
549                                 unary->oper = parse_token();
550                                 unary->prefix = true;
551                                 unary->expression = parse_expression(oper->precedence);
552                                 left = unary;
553                         }
554                         else
555                                 throw runtime_error(format("Parse error at '%s': expected an expression", token));
556                 }
557         }
558 }
559
560 RefPtr<BinaryExpression> ProgramParser::parse_binary(const RefPtr<Expression> &left, const Operator *oper)
561 {
562         RefPtr<BinaryExpression> binary = (oper->precedence==16 ? new Assignment : new BinaryExpression);
563         binary->left = left;
564         binary->oper = parse_token();
565         if(binary->oper=="[")
566         {
567                 binary->right = parse_expression();
568                 expect("]");
569                 binary->after = "]";
570         }
571         else
572                 binary->right = parse_expression(oper->precedence+(oper->assoc==RIGHT_TO_LEFT));
573         return binary;
574 }
575
576 RefPtr<FunctionCall> ProgramParser::parse_function_call(const VariableReference &var)
577 {
578         RefPtr<FunctionCall> call = new FunctionCall;
579         call->name = var.name;
580         call->constructor = is_type(call->name);
581         expect("(");
582         while(peek_token()!=")")
583         {
584                 if(!call->arguments.empty())
585                         expect(",");
586                 call->arguments.push_back(parse_expression());
587         }
588         expect(")");
589         return call;
590 }
591
592 RefPtr<StructDeclaration> ProgramParser::parse_struct_declaration()
593 {
594         expect("struct");
595         RefPtr<StructDeclaration> strct = new StructDeclaration;
596
597         strct->name = expect_identifier();
598         parse_block(strct->members, true);
599         expect(";");
600
601         declared_types.insert(strct->name);
602         return strct;
603 }
604
605 RefPtr<VariableDeclaration> ProgramParser::parse_variable_declaration()
606 {
607         RefPtr<VariableDeclaration> var = new VariableDeclaration;
608
609         string token = peek_token();
610         if(is_sampling_qualifier(token))
611         {
612                 var->sampling = parse_token();
613                 token = peek_token();
614                 if(!is_interface_qualifier(token))
615                         throw runtime_error(format("Parse error at '%s': expected an interface qualifier", token));
616         }
617
618         if(is_interface_qualifier(token))
619                 var->interface = parse_token();
620         else if(token=="const")
621         {
622                 var->constant = true;
623                 parse_token();
624         }
625
626         var->type = expect_type();
627         var->name = expect_identifier();
628
629         if(check("["))
630         {
631                 var->array = true;
632                 if(!check("]"))
633                 {
634                         var->array_size = parse_expression();
635                         expect("]");
636                 }
637         }
638
639         if(check("="))
640                 var->init_expression = parse_expression();
641
642         expect(";");
643         return var;
644 }
645
646 RefPtr<FunctionDeclaration> ProgramParser::parse_function_declaration()
647 {
648         RefPtr<FunctionDeclaration> func = new FunctionDeclaration;
649
650         func->return_type = expect_type();
651         func->name = expect_identifier();
652         expect("(");
653         while(peek_token()!=")")
654         {
655                 if(!func->parameters.empty())
656                         expect(",");
657
658                 RefPtr<VariableDeclaration> var = new VariableDeclaration;
659                 var->type = expect_type();
660                 var->name = expect_identifier();
661                 func->parameters.push_back(var);
662         }
663         expect(")");
664
665         string token = peek_token();
666         if(token=="{")
667         {
668                 func->definition = func.get();
669                 parse_block(func->body, true);
670         }
671         else if(token==";")
672                 parse_token();
673         else
674                 throw runtime_error(format("Parse error at '%s': expected '{' or ';'", token));
675
676         return func;
677 }
678
679 RefPtr<InterfaceBlock> ProgramParser::parse_interface_block()
680 {
681         RefPtr<InterfaceBlock> iface = new InterfaceBlock;
682
683         iface->interface = parse_token();
684         if(!is_interface_qualifier(iface->interface))
685                 throw runtime_error(format("Parse error at '%s': expected an interface qualifier", iface->interface));
686
687         iface->name = expect_identifier();
688         parse_block(iface->members, true);
689         if(!check(";"))
690         {
691                 iface->instance_name = expect_identifier();
692                 if(check("["))
693                 {
694                         iface->array = true;
695                         expect("]");
696                 }
697                 expect(";");
698         }
699
700         return iface;
701 }
702
703 RefPtr<Conditional> ProgramParser::parse_conditional()
704 {
705         expect("if");
706         expect("(");
707         RefPtr<Conditional> cond = new Conditional;
708         cond->condition = parse_expression();
709         expect(")");
710
711         parse_block(cond->body, false);
712
713         string token = peek_token();
714         if(token=="else")
715         {
716                 parse_token();
717                 parse_block(cond->else_body, false);
718         }
719
720         return cond;
721 }
722
723 RefPtr<Iteration> ProgramParser::parse_iteration()
724 {
725         expect("for");
726         expect("(");
727         RefPtr<Iteration> loop = new Iteration;
728         string token = peek_token();
729         if(is_type(token))
730                 loop->init_statement = parse_statement();
731         else
732         {
733                 RefPtr<ExpressionStatement> expr = new ExpressionStatement;
734                 expr->expression = parse_expression();
735                 expect(";");
736                 loop->init_statement = expr;
737         }
738         loop->condition = parse_expression();
739         expect(";");
740         loop->loop_expression = parse_expression();
741         expect(")");
742
743         parse_block(loop->body, false);
744
745         return loop;
746 }
747
748 RefPtr<Passthrough> ProgramParser::parse_passthrough()
749 {
750         expect("passthrough");
751         RefPtr<Passthrough> pass = new Passthrough;
752         if(cur_stage->type==GEOMETRY)
753         {
754                 expect("[");
755                 pass->subscript = parse_expression();
756                 expect("]");
757         }
758         expect(";");
759         return pass;
760 }
761
762 RefPtr<Return> ProgramParser::parse_return()
763 {
764         expect("return");
765         RefPtr<Return> ret = new Return;
766         if(peek_token()!=";")
767                 ret->expression = parse_expression();
768         expect(";");
769         return ret;
770 }
771
772 } // namespace GL
773 } // namespace Msp