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