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