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(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                 //IO::print("%d '%c'\n", comment, *iter);
 222                 if(comment==0)
 223                 {
 224                         if(*iter=='/')
 225                                 comment = 1;
 226                         else if(!isspace(*iter))
 227                                 break;
 228                 }
 229                 else if(comment==1)
 230                 {
 231                         if(*iter=='/')
 232                         {
 233                                 comment = 2;
 234                                 slashes = 2;
 235                         }
 236                         else if(*iter=='*')
 237                                 comment = 3;
 238                         else
 239                         {
 240                                 comment = 0;
 241                                 --iter;
 242                                 break;
 243                         }
 244                 }
 245                 else if(comment==2)
 246                 {
 247                         if(*iter=='\n')
 248                                 comment = 0;
 249                         else if(*iter=='/')
 250                                 ++slashes;
 251                         else if(!isspace(*iter) && slashes>=6)
 252                                 return false;
 253                 }
 254                 else if(comment==3 && *iter=='*')
 255                         comment = 4;
 256                 else if(comment==4)
 257                 {
 258                         if(*iter=='/')
 259                                 comment = 0;
 260                         else
 261                                 comment = 3;
 262                 }
 263
 264                 ++iter;
 265         }
 266
 267         return iter!=source.end();
 268 }
 269
 270 void ProgramParser::expect(const string &token)
 271 {
 272         string parsed = parse_token();
 273         if(parsed!=token)
 274                 throw runtime_error(format("Parse error at '%s': expected '%s'", parsed, token));
 275 }
 276
 277 string ProgramParser::expect_type()
 278 {
 279         string token = parse_token();
 280         if(!is_type(token))
 281                 throw runtime_error(format("Parse error at '%s': expected a type", token));
 282         return token;
 283 }
 284
 285 string ProgramParser::expect_identifier()
 286 {
 287         string token = parse_token();
 288         if(!is_identifier(token))
 289                 throw runtime_error(format("Parse error at '%s': expected an identifier", token));
 290         return token;
 291 }
 292
 293 bool ProgramParser::check(const string &token)
 294 {
 295         bool result = (peek_token()==token);
 296         if(result)
 297                 parse_token();
 298         return result;
 299 }
 300
 301 bool ProgramParser::is_interface_qualifier(const string &token)
 302 {
 303         return (token=="uniform" || token=="in" || token=="out");
 304 }
 305
 306 bool ProgramParser::is_sampling_qualifier(const string &token)
 307 {
 308         return token=="centroid";
 309 }
 310
 311 bool ProgramParser::is_qualifier(const string &token)
 312 {
 313         return (token=="const" || is_interface_qualifier(token) || is_sampling_qualifier(token));
 314 }
 315
 316 bool ProgramParser::is_builtin_type(const string &token)
 317 {
 318         static Regex re("^(void|float|int|bool|[ib]?vec[234]|mat[234](x[234])?|sampler((1D|2D)(Array)?(Shadow)?|Cube(Shadow)?|3D))$");
 319         return re.match(token);
 320 }
 321
 322 bool ProgramParser::is_type(const string &token)
 323 {
 324         return is_builtin_type(token) || declared_types.count(token);
 325 }
 326
 327 bool ProgramParser::is_identifier(const string &token)
 328 {
 329         static Regex re("^[a-zA-Z_][a-zA-Z0-9_]*$");
 330         return re.match(token);
 331 }
 332
 333 Node *ProgramParser::parse_global_declaration()
 334 {
 335         string token = peek_token();
 336         if(token=="layout")
 337                 return parse_layout();
 338         else if(token=="struct")
 339                 return parse_struct_declaration();
 340         else if(is_sampling_qualifier(token) || token=="const")
 341                 return parse_variable_declaration();
 342         else if(is_interface_qualifier(token))
 343         {
 344                 if(is_type(peek_token(1)))
 345                         return parse_variable_declaration();
 346                 else
 347                         return parse_interface_block();
 348         }
 349         else if(is_type(token))
 350         {
 351                 if(peek_token(2)=="(")
 352                         return parse_function_declaration();
 353                 else
 354                         return parse_variable_declaration();
 355         }
 356         else if(token.empty())
 357                 return 0;
 358         else
 359                 throw runtime_error(format("Syntax error at '%s': expected a global declaration", token));
 360 }
 361
 362 Node *ProgramParser::parse_statement()
 363 {
 364         string token = peek_token();
 365         if(token=="if")
 366                 return parse_conditional();
 367         else if(token=="for")
 368                 return parse_iteration();
 369         else if(token=="passthrough")
 370                 return parse_passthrough();
 371         else if(token=="return")
 372                 return parse_return();
 373         else if(is_qualifier(token) || is_type(token))
 374                 return parse_variable_declaration();
 375         else if(!token.empty())
 376         {
 377                 RefPtr<ExpressionStatement> expr = new ExpressionStatement;
 378                 expr->expression = parse_expression();
 379                 expect(";");
 380
 381                 return expr.release();
 382         }
 383         else
 384                 throw runtime_error(format("Syntax error at '%s': expected a statement", token));
 385 }
 386
 387 Layout *ProgramParser::parse_layout()
 388 {
 389         expect("layout");
 390         expect("(");
 391         RefPtr<Layout> layout = new Layout;
 392         while(1)
 393         {
 394                 string token = parse_token();
 395                 if(token==")")
 396                         throw runtime_error(format("Parse error at '%s': expected layout qualifier id", token));
 397
 398                 layout->qualifiers.push_back(Layout::Qualifier());
 399                 Layout::Qualifier &qual = layout->qualifiers.back();
 400                 qual.identifier = token;
 401
 402                 if(check("="))
 403                         qual.value = parse_token();
 404
 405                 if(peek_token()==")")
 406                         break;
 407
 408                 expect(",");
 409         }
 410         expect(")");
 411         layout->interface = parse_token();
 412         expect(";");
 413
 414         return layout.release();
 415 }
 416
 417 void ProgramParser::parse_block(Block &block, bool require_braces)
 418 {
 419         bool have_braces = (require_braces || peek_token()=="{");
 420         if(have_braces)
 421                 expect("{");
 422
 423         if(have_braces)
 424         {
 425                 while(peek_token()!="}")
 426                         block.body.push_back(parse_statement());
 427         }
 428         else
 429                 block.body.push_back(parse_statement());
 430
 431         block.use_braces = (require_braces || block.body.size()!=1);
 432
 433         if(have_braces)
 434                 expect("}");
 435 }
 436
 437 Expression *ProgramParser::parse_expression(unsigned precedence)
 438 {
 439         RefPtr<Expression> left;
 440         VariableReference *left_var = 0;
 441         while(1)
 442         {
 443                 string token = peek_token();
 444
 445                 const Operator *oper = 0;
 446                 for(Operator *i=operators; (!oper && i->type); ++i)
 447                         if(token==i->token && (!left || i->type!=PREFIX) && (left || i->type!=POSTFIX))
 448                                 oper = i;
 449
 450                 if(token==";" || token==")" || token=="]" || token=="," || (oper && precedence && oper->precedence>=precedence))
 451                 {
 452                         if(left)
 453                                 return left.release();
 454                         else
 455                                 throw runtime_error(format("Parse error at '%s': expected an expression", token));
 456                 }
 457                 else if(left)
 458                 {
 459                         if(token=="(")
 460                         {
 461                                 if(!left_var)
 462                                         throw runtime_error(format("Parse error at '%s': function name must be an identifier", token));
 463                                 left = parse_function_call(left_var);
 464                         }
 465                         else if(token==".")
 466                         {
 467                                 RefPtr<MemberAccess> memacc = new MemberAccess;
 468                                 memacc->left = left.release();
 469                                 parse_token();
 470                                 memacc->member = expect_identifier();
 471                                 left = memacc;
 472                         }
 473                         else if(oper && oper->type==POSTFIX)
 474                         {
 475                                 RefPtr<UnaryExpression> unary = new UnaryExpression;
 476                                 unary->oper = parse_token();
 477                                 unary->prefix = false;
 478                                 unary->expression = left.release();
 479                                 left = unary;
 480                         }
 481                         else if(oper && oper->type==BINARY)
 482                                 left = parse_binary(left.release(), oper);
 483                         else
 484                                 throw runtime_error(format("Parse error at '%s': expected an operator", token));
 485                         left_var = 0;
 486                 }
 487                 else
 488                 {
 489                         if(token=="(")
 490                         {
 491                                 parse_token();
 492                                 RefPtr<ParenthesizedExpression> parexpr = new ParenthesizedExpression;
 493                                 parexpr->expression = parse_expression();
 494                                 expect(")");
 495                                 left = parexpr;
 496                         }
 497                         else if(is_identifier(token))
 498                         {
 499                                 RefPtr<VariableReference> var = new VariableReference;
 500                                 var->name = expect_identifier();
 501                                 left = var;
 502                                 left_var = var.get();
 503                         }
 504                         else if(oper && oper->type==PREFIX)
 505                         {
 506                                 RefPtr<UnaryExpression> unary = new UnaryExpression;
 507                                 unary->oper = parse_token();
 508                                 unary->prefix = true;
 509                                 unary->expression = parse_expression(oper->precedence);
 510                                 left = unary;
 511                         }
 512                         else if(isdigit(token[0]))
 513                         {
 514                                 RefPtr<Literal> literal = new Literal;
 515                                 literal->token = parse_token();
 516                                 left = literal;
 517                         }
 518                         else
 519                                 throw runtime_error(format("Parse error at '%s': expected an expression", token));
 520                 }
 521         }
 522 }
 523
 524 BinaryExpression *ProgramParser::parse_binary(Expression *left, const Operator *oper)
 525 {
 526         RefPtr<BinaryExpression> binary = new BinaryExpression;
 527         binary->left = left;
 528         binary->oper = parse_token();
 529         if(binary->oper=="[")
 530         {
 531                 binary->right = parse_expression();
 532                 expect("]");
 533                 binary->after = "]";
 534         }
 535         else
 536                 binary->right = parse_expression(oper->precedence+(oper->assoc==RIGHT_TO_LEFT));
 537         binary->assignment = (oper->precedence==16);
 538         return binary.release();
 539 }
 540
 541 FunctionCall *ProgramParser::parse_function_call(VariableReference *var)
 542 {
 543         RefPtr<FunctionCall> call = new FunctionCall;
 544         call->name = var->name;
 545         call->constructor = is_type(call->name);
 546         expect("(");
 547         while(peek_token()!=")")
 548         {
 549                 if(!call->arguments.empty())
 550                         expect(",");
 551                 call->arguments.push_back(parse_expression());
 552         }
 553         expect(")");
 554         return call.release();
 555 }
 556
 557 StructDeclaration *ProgramParser::parse_struct_declaration()
 558 {
 559         expect("struct");
 560         RefPtr<StructDeclaration> strct = new StructDeclaration;
 561
 562         strct->name = expect_identifier();
 563         parse_block(strct->members, true);
 564         expect(";");
 565
 566         declared_types.insert(strct->name);
 567         return strct.release();
 568 }
 569
 570 VariableDeclaration *ProgramParser::parse_variable_declaration()
 571 {
 572         RefPtr<VariableDeclaration> var = new VariableDeclaration;
 573
 574         string token = peek_token();
 575         if(is_sampling_qualifier(token))
 576         {
 577                 var->sampling = parse_token();
 578                 token = peek_token();
 579                 if(!is_interface_qualifier(token))
 580                         throw runtime_error(format("Parse error at '%s': expected an interface qualifier", token));
 581         }
 582
 583         if(is_interface_qualifier(token))
 584                 var->interface = parse_token();
 585         else if(token=="const")
 586         {
 587                 var->constant = true;
 588                 parse_token();
 589         }
 590
 591         var->type = expect_type();
 592         var->name = expect_identifier();
 593
 594         if(check("["))
 595         {
 596                 var->array = true;
 597                 if(!check("]"))
 598                 {
 599                         var->array_size = parse_expression();
 600                         expect("]");
 601                 }
 602         }
 603
 604         if(check("="))
 605                 var->init_expression = parse_expression();
 606
 607         expect(";");
 608         return var.release();
 609 }
 610
 611 FunctionDeclaration *ProgramParser::parse_function_declaration()
 612 {
 613         RefPtr<FunctionDeclaration> func = new FunctionDeclaration;
 614
 615         func->return_type = expect_type();
 616         func->name = expect_identifier();
 617         parse_function_parameter_list(*func);
 618
 619         string token = peek_token();
 620         if(token=="{")
 621         {
 622                 func->definition = true;
 623                 parse_block(func->body, true);
 624         }
 625         else if(token==";")
 626                 parse_token();
 627         else
 628                 throw runtime_error(format("Parse error at '%s': expected '{' or ';'", token));
 629
 630         return func.release();
 631 }
 632
 633 void ProgramParser::parse_function_parameter_list(FunctionDeclaration &func)
 634 {
 635         expect("(");
 636         while(peek_token()!=")")
 637         {
 638                 if(!func.parameters.empty())
 639                         expect(",");
 640
 641                 RefPtr<VariableDeclaration> var = new VariableDeclaration;
 642                 var->type = expect_type();
 643                 var->name = expect_identifier();
 644                 func.parameters.push_back(var.release());
 645         }
 646         expect(")");
 647 }
 648
 649 InterfaceBlock *ProgramParser::parse_interface_block()
 650 {
 651         RefPtr<InterfaceBlock> iface = new InterfaceBlock;
 652
 653         iface->interface = parse_token();
 654         if(!is_interface_qualifier(iface->interface))
 655                 throw runtime_error(format("Parse error at '%s': expected an interface qualifier", iface->interface));
 656
 657         iface->name = expect_identifier();
 658         parse_block(iface->members, true);
 659         expect(";");
 660
 661         return iface.release();
 662 }
 663
 664 Conditional *ProgramParser::parse_conditional()
 665 {
 666         expect("if");
 667         expect("(");
 668         RefPtr<Conditional> cond = new Conditional;
 669         cond->condition = parse_expression();
 670         expect(")");
 671
 672         parse_block(cond->body, false);
 673
 674         string token = peek_token();
 675         if(token=="else")
 676         {
 677                 parse_token();
 678                 parse_block(cond->else_body, false);
 679         }
 680
 681         return cond.release();
 682 }
 683
 684 Iteration *ProgramParser::parse_iteration()
 685 {
 686         expect("for");
 687         expect("(");
 688         RefPtr<Iteration> loop = new Iteration;
 689         string token = peek_token();
 690         if(is_type(token))
 691                 loop->init_statement = parse_statement();
 692         else
 693         {
 694                 RefPtr<ExpressionStatement> expr = new ExpressionStatement;
 695                 expr->expression = parse_expression();
 696                 expect(";");
 697                 loop->init_statement = expr.release();
 698         }
 699         loop->condition = parse_expression();
 700         expect(";");
 701         loop->loop_expression = parse_expression();
 702         expect(")");
 703
 704         parse_block(loop->body, false);
 705
 706         return loop.release();
 707 }
 708
 709 Passthrough *ProgramParser::parse_passthrough()
 710 {
 711         expect("passthrough");
 712         RefPtr<Passthrough> pass = new Passthrough;
 713         if(cur_stage->type==GEOMETRY)
 714         {
 715                 expect("[");
 716                 pass->subscript = parse_expression();
 717                 expect("]");
 718         }
 719         expect(";");
 720         return pass.release();
 721 }
 722
 723 Return *ProgramParser::parse_return()
 724 {
 725         expect("return");
 726         RefPtr<Return> ret = new Return;
 727         ret->expression = parse_expression();
 728         expect(";");
 729         return ret.release();
 730 }
 731
 732 } // namespace GL
 733 } // namespace Msp